Why Your Comparator Isn’t Enough: The Hidden Stability Problem in C++ STL

§1 — The Bug

vector<pair<int,int>> v = {{3,0},{1,1},{1,2},{2,3}};
// Sort by first element only
sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.first < b.first; });
// Expected: (1,1),(1,2) stay in insertion order
// Got:      (1,2),(1,1) — ORDER FLIPPED. No warning.

The comparator was correct. The mental model was wrong. Here’s the fix — permanently.

§2 — The 3-Type Model (Backbone)

Every STL container/algorithm fits one type. Learn the type, know the behavior.

Type 1 — Full Ordering (Linear)

Algorithms: sort, stable_sort

• Touches every element once
• sort: order among equals is arbitrary
• stable_sort: preserves insertion order for equals

Type 2 — Heap / Partial Ordering

Algorithms: priority_queue, make_heap / push_heap, nth_element, partial_sort

• Heap shape, not sorted order
• Instability is structural — unavoidable
• nth_element: partition only, no ordering inside either partition

Type 3 — Structural / Tree Ordering

Containers: set / multiset, map / multimap

• Comparator defines identity and order
• Insertion order is invisible — forever
• Equality: !comp(a,b) && !comp(b,a)

Know the type → predict the behavior. There are only 3.

§3 — Comparator Truth

• Comparator defines: the ordering rule
• Comparator does NOT define: stability
• Comparator does NOT define: insertion order
• Comparator does NOT define: which equal element surfaces first

Comparator decides ranking, not history.

§4 — Stability in 5 Lines

• Definition: Equal elements appear in their original relative order after sorting.
• Example: Sort [(A,1),(B,1),(C,2)] by value → stable gives [(A,1),(B,1)], unstable may give [(B,1),(A,1)].
• Only stable_sort guarantees it in Type 1.
• Type 2 (heap) and Type 3 (tree) have no stability guarantee, ever.
• If you need stability elsewhere — encode it (see §6).

§5 — Case Breakdown

A · sort vs stable_sort

• Bug triggers when: comparator only compares a subset of fields
• Equal elements can land in any order after sort

// Input: [(A,1),(B,1)] — sort by second field only
sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.second < b.second; });
// Result: [(B,1),(A,1)]  ← A and B swapped. Bug.
stable_sort(...); // Result: [(A,1),(B,1)] ← Safe.

B · priority_queue — Heap Reality

• A heap is a shape constraint, not a sorted array
• Internal rebalancing during push/pop ignores arrival order
• Fix: index-tag every element — (value, index)

// Push (1,A) then (1,B) — expect A out first
pq.push({1, "A"}); pq.push({1, "B"});
pq.top(); // May return B. Heap does not preserve push order.

// Fix: break ties with push index
pq.push({1, idx++, "A"}); // comparator uses idx as tiebreak

C · set / map

• Ordered purely by comparator — insertion order is gone at insert time
• Two elements are equal if: !comp(a,b) && !comp(b,a)
• set drops the second equal element; multiset keeps both but does not preserve insert order

D · nth_element — Common CP Trap

• Only guarantees: v[n] is the n-th element in sorted order
• Elements before n are ≤ v[n]; elements after are ≥ v[n]
• No ordering inside either partition — a common wrong assumption
• Use when: finding median or top-K, not when ordering matters

E · partial_sort

• Sorts only the first k elements correctly
• Remaining elements are in unspecified order
• Use for: top-K problems where you only need the sorted prefix

§6 — The Real Bug: Partial vs Total Order

• A comparator that ignores some fields creates a partial order
• Equal-ranked elements form an equivalence class with no defined order within
• Stability requires a total order — every pair must be distinguishable

Universal fix: extend (value) → (value, index)

// Partial order — bugs
[](auto& a, auto& b){ return a.freq < b.freq; }

// Total order — safe
[](auto& a, auto& b){
  if(a.freq != b.freq) return a.freq < b.freq;
  return a.idx < b.idx; // tiebreak = insertion index
}

§7 — Strict Weak Ordering (Advanced Edge)

• Antisymmetry: if comp(a,b) then !comp(b,a)
• Transitivity: if comp(a,b) and comp(b,c) then comp(a,c)
• Violate either → undefined behavior (crashes, infinite loops, silent corruption)

// Violates antisymmetry when a == b
[](int a, int b){ return a <= b; } // ← WRONG. comp(x,x) must be false.

// Also broken: not transitive
[](auto& a, auto& b){ return a.x != b.x; } // ← UB waiting to happen.

§8 — CP Problem Patterns

§9 — Visual Dry Run: Heap Instability

Push (1,"A"), (1,"B"), (1,"C") into a max-heap (compare by value). Pop all 3.

Step 1: Push (1,A). Heap: [A]. Root = A.
Step 2: Push (1,B). Heap rebalances. Both equal — root can be A or B.
Step 3: Push (1,C). After sift-up: root = C  (implementation-defined swap).
Step 4: Pop order: C → B → A.  Expected FIFO: A → B → C.  Completely wrong.
Step 5: Fix: store (value, push_index). Comparator breaks ties by index → FIFO restored: A → B → C.

§10 — Instant Decision Rules

• Equal elements must keep original order → use stable_sort or add index field
• Using any heap / priority_queue → always assume instability; always index-tag
• Comparator ignores one or more fields → expect undefined order among equals
• Using nth_element → do not assume order inside the partition
• Inserting into set / map → insertion order is gone; comparator is identity
• Unsure if bugs exist → add index, make it a total order
• Comparator returns true for equal elements → undefined behavior, fix immediately

§11 — Final Takeaways

• ✗ Comparator ≠ Stability. They are orthogonal. The comparator ranks; stability is a contract of the algorithm.
• ✗ Heap destroys order. Structural rebalancing ignores push sequence. No exceptions.
• ✗ Trees ignore insertion. set/map see only the comparator. Your push order is erased.
• ✓ Stability must be encoded. Use stable_sort, or encode it in (value, index) tuples.
• ✓ Index tagging = universal fix. Append insertion index to any comparator key → total order, stability guaranteed.
• ✓ Know your type. Full / Heap / Tree. That alone eliminates 90% of ordering bugs before you write a line.

“Are you defining order, or assuming it?”