SimplePriorityQueue internally creates a Dictionary<TItem, IList<SimplePriorityQueue<TItem, TPriority>.SimpleNode>> mapping items to queue nodes. But when TItem is a struct that doesn't implement IEquatable<T>, like System.Drawing.PointF or Unity's Vector3, accessing the dictionary is slow, because the default equality comparer does boxing conversions to call inherited methods. (More discussion on Stack Overflow.)
The usual solutions are to implement IEquatable<T> on all structs, which isn't an option for third party types (e.g. Unity deliberately doesn't implement it), or pass a custom IEqualityComparer<T> to the dictionary constructor, which isn't an option here since it's constructed internally. Instead, one must use a wrapper type or switch to FastPriorityQueue.
SimplePriorityQueue should add a constructor that takes an IEqualityComparer<TItem> and passes it to the dictionary, and/or warn users that TItem should only be a value type if it implements IEquatable.
BlueRaja
commented
5 years ago
SimplePriorityQueue internally creates a
Dictionary<TItem, IList<SimplePriorityQueue<TItem, TPriority>.SimpleNode>>mapping items to queue nodes. But whenTItemis a struct that doesn't implementIEquatable<T>, likeSystem.Drawing.PointFor Unity'sVector3, accessing the dictionary is slow, because the default equality comparer does boxing conversions to call inherited methods. (More discussion on Stack Overflow.)The usual solutions are to implement
IEquatable<T>on all structs, which isn't an option for third party types (e.g. Unity deliberately doesn't implement it), or pass a customIEqualityComparer<T>to the dictionary constructor, which isn't an option here since it's constructed internally. Instead, one must use a wrapper type or switch to FastPriorityQueue.SimplePriorityQueue should add a constructor that takes an
IEqualityComparer<TItem>and passes it to the dictionary, and/or warn users thatTItemshould only be a value type if it implementsIEquatable.