Search code examples
c++sortingstdlist

c++ std::list sort preserve order

Possible Duplicate:
Is std::list<>::sort stable?

Does C++ std::list sort function is guaranteed to preserve the order of equal elements in the list? E.g. if we have objects A, B and C in the list and the comparison operators are overloaded so that A == C and B < A, will we necessarily get B-A-C or is it possible to get a B-C-A?

Solution

  • Yes, in C++ list::sort() is stable, per ISO 14882:2003 23.2.2.4[lib.list.ops]/31

    Effects: Sorts the list according to the operator< or a Compare function object.
Notes: Stable: the relative order of the equivalent elements is preserved. 
If an exception is thrown the order of the elements in the list is indeterminate.