1

Does std::priorirty_queue guarantee a specific ordering (regardless of the standard library implementation) when extracting elements in a largest-first order?

Suppose that the comparison function that is provided cannot resolve all ties. For example, we may be storing pairs of integers in the priority queue, and comparing them based on the first value. This way (1,2) and (1,3) compare equal. For a given insertion order with .push(), is a specific extraction order guaranteed when using .pop()? Or is it possible (i.e. consistent with the standard) that some implementations return (1,2) before (1,3) while others return (1,3) first?

Szabolcs
  • 24,728
  • 9
  • 85
  • 174
  • As this will certainly come up: I am not looking to preserve the insertion order for ties (i.e. stable sorting in the classic sense). I am merely looking to guarantee a platform-independent output. – Szabolcs Dec 29 '22 at 17:06
  • cppreference.com is generally considered to be a reputable source of C++ reference information, on Stackoverflow. A quick check there finds no evidence of any guarantee, at all. – Sam Varshavchik Dec 29 '22 at 17:14
  • 1
    @SamVarshavchik The lack of a mention on cppreference is not quite as convincing as the counterexample shown in the linked duplicate though :-) – Szabolcs Dec 29 '22 at 17:31
  • The ordering depends on the compare operator you specify for the datatype stored in your queue. Defaults to std::less (https://en.cppreference.com/w/cpp/container/priority_queue). I've done this for structs with timestamps (at which functions should execute) and that was completely portable between linux and windows (no issues). – Pepijn Kramer Dec 29 '22 at 17:31
  • @PepijnKramer I am guessing you are saying that one should provide a comparison operator that does not allow ties at all. This is workable in most cases, but sometimes it becomes a bit inconvenient. – Szabolcs Dec 29 '22 at 17:35
  • 2
    why inconvenient? Either you want the second number of the pair to be part of the comparison or not. You just need to pick – 463035818_is_not_an_ai Dec 29 '22 at 18:14
  • A heap-based priority queue cannot guarantee removal order of equal items without additional information. For a brief explanation of why, see https://stackoverflow.com/q/54893840/56778. I know you weren't asking specifically about removing in the order they were inserted (which is what that question addresses specifically), but we can extend the reasoning. The order of insertions and deletions from the queue affects the shape of the tree, and without additional information there can be no guarantees about which of two equal items will be removed first. – Jim Mischel Jan 01 '23 at 17:10

0 Answers0