What is the behavior of std::sort when used with ints that are equal is it going to keep them in the same order or just do some unpredictable stuff?
Asked
Active
Viewed 3,684 times
2 Answers
18
std::sort doesn't preserve the order of the equivalent elements, std::stable_sort does. However, in case of int's you will not notice the difference unless you use some non-trivial ordering as in the following example:
struct half_less
{
bool operator()(int a, int b) const { return (a / 2) < (b / 2); }
};
std::sort(begin, end, half_less());
Here is another example when std::stable_sort is a more suitable candidate than std::sort
Arsen Khachaturyan
- 7,904
- 4
- 42
- 42
vitaut
- 49,672
- 25
- 199
- 336
-
Isn't (a / 2) < ( b / 2) the same as a < b ? – Zebrafish Aug 29 '17 at 01:50
-
@Zebrafish no, consider for example a = 2 and b = 3 – vitaut Aug 29 '17 at 01:59
6
@vitaut is right. I just want to add that you would not notice if the order of equal integers is changed. This only matters if you sort values which happen to have an indentifying property. For example if you store pointers to integers and sort by the integer value.
frast
- 2,700
- 1
- 25
- 34
-
Right, or if some non-trivial ordering provided by the comparison functor is used. – vitaut Nov 05 '10 at 15:33
-
@vitaut: What "non-trivial ordering" could you use for ints that would detect the non-stability of the sort? – Nov 05 '10 at 15:47
-
@Roger Pate: Any under which non-equal numbers are considered equivalent. This sounds weird, but I don't see other explanation of why the OP cares about the order of ints. – vitaut Nov 05 '10 at 15:51