Monday, April 25, 2011

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

I couldn't find any definitive answer to this question.

I suppose most implementation use merge sort that is stable but, is the stability a requirement or a side effect?

From stackoverflow
  • Yes, std::list<>::sort is guaranteed to be stable.

    See http://www.sgi.com/tech/stl/List.html

    Edouard A. : Exactly what I was looking for, thanks!
  • According to "The C++ Programming Language" (Stroustrup p470), yes, stl::list<>::sort is stable.

    dalle : Quote from source: +1
  • C++ Standard ISO/IEC 14882:2003 says:

    23.2.2.4/31

    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.

    MSalters : +1. SGI and Stroustrup are both correct but not the "definitive answer". ISO 14882 is.
    Dominic Rodger : +1 - welcome to stackoverflow :)
    Edouard A. : Only great answers but I admit this is the best. ;)

0 comments:

Post a Comment

Note: Only a member of this blog may post a comment.