Reputation: 44568
Does the standard guarantee that order of equal elements will not change (eh, forgot the term for that) by using std::sort or do I need to consider an alternative solution to achieve this goal?
Upvotes: 12
Views: 4504
Reputation: 490108
std::sort
is not guaranteed to be stable (the term you were trying to think of). As you'd guess, std::stable_sort
is guaranteed to be stable. std::stable_sort
also provides a guarantee on worst-case complexity, which std::sort
does not. std::sort
is typically faster on average though.
Upvotes: 24
Reputation: 299790
From C++ reference: here
Elements that would compare equal to each other are not guaranteed to keep their original relative order.
You might want stable_sort, but note that it's not as fast (in average)
Upvotes: 3
Reputation: 59827
The term for what you're describing is stability.
From SGI's STL docs:
Note:
sort
is not guaranteed to be stable.
Use stable_sort
if you need this.
Upvotes: 2
Reputation: 754595
No it explicitly does not guarantee this. If you need to maintain relative ordering use stable_sort instead.
Documentation of sort which includes reference to equivalent elements
Upvotes: 2