slice.binary_search_by() said "If there are multiple matches, then any one of the matches could be returned." , but the implementation isn't the same thing. Actually, it returns the last one if multiple matches found.

My case is that I have a BinaryHeap of Reverse<Duration> and if two durations are the same pop() will return them in insertion order, my code relies on that being true but nowhere on pop() or the definition of BinaryHeap confirms that, my only relief is in their examples there's a comment that confirms it.

// We can iterate over the items in the heap, although they are returned in
// a random order.
for x in &heap {
println!("{}", x);
}
// If we instead pop these scores, they should come back in order.

My question is can I rely on that pop() will always return the elements in insertion order if they have the same priority? I mostly ask because of the recent incident and because this assumption is only in a comment on the example and not on the docs of the method or type itself.

I don't believe even the comment in the example means insertion order. The point of the comment is that pop() always retrieves the greatest element as specified by Ord; so this says nothing about insertion order.

If you want to rely on insertion order being preserved, maintain an ever-increasing counter, and store (T, u64) in the heap. Since tuples are ordered lexicographically, this will correctly break ties.

If you want to rely on insertion order being preserved, maintain an ever-increasing counter, and store (T, u64) in the heap. Since tuples are ordered lexicographically, this will correctly break ties.

Where do you find the lexicograpically ordered info?

EDIT: Well just as I post this I found it, why does this happens so often?

The sequential nature of the tuple applies to its implementations of various traits. For example, in PartialOrd and Ord , the elements are compared sequentially until the first non-equal set is found.

If you want to rely on insertion order being preserved, maintain an ever-increasing counter, and store (T, u64) in the heap. Since tuples are ordered lexicographically, this will correctly break ties.

Only now after this long I realized that if I want the insertion order to be preserved (T, u64) needs to actually be (T, Reverse<u64>) because of the max-heap nature of the BinaryHeap if u64 is not reversed it will pop() the one inserted last instead of first.

That polkadot incident was because they depended not only on it being deterministic, but also on explicitly unspecified behavior being the same between different versions of rust. This is similar - it will behave deterministically, but in situations where there are multiple valid choices (keys are equal according to Ord), it may choose a different one when you move to a different version of rust.

If this second part of the value (u64 in (T, u64)) is monotonically increasing, this would be the case only after overflow, i.e. after 2^64 elements passing through heap.

Yeah, the accepted solution definitely solves the problem. I just wanted to provide additional context about how to interpret the docs, and what happened with polkadot.