std::sort behaves different

[NullAndVoid]

Vector containing pairs of int64_t and a string, on two different systems a std::sort is run on the vector and where the int64_t is the same the order is different between systems.

One older Ubuntu 14 system with the "correct" behaviour leaves those duplicate ints in the same order they were found, the newer WSL Ubuntu 16 system does not. This results in unexpected behaviour on the new system.

vector<pair<int64_t, std::string> > sorted;
while (pindex)
{
sorted.push_back(make_pair(pindex->Time(), pindex->Hash()));
pindex = pindex->pprev;
}
reverse(sorted.begin(), sorted.end());
sort(sorted.begin(), sorted.end());

Old system...

time 1504540873 hash 92f5eb47690aa64e3efea15e5c212002129d050f3c229a1b4edddbbaa4ddf75b
time 1504540875 hash 27d2aafae09d47ffc94474cce0e114c6e5585c3a61aa964e26a7c12ada343f41
time 1504540875 hash 985d06f40448db2c35a2ff270c49174ee948835e3dd741b959b2bc22200f6c04
time 1504540876 hash 14853d0152fae361c18963950d7938c8eff51a5836cdd6aff944ea5132c00e66

New system...

2018-10-04 16:34:01 time 1504540873 hash 92f5eb47690aa64e3efea15e5c212002129d050f3c229a1b4edddbbaa4ddf75b
2018-10-04 16:34:01 time 1504540875 hash 985d06f40448db2c35a2ff270c49174ee948835e3dd741b959b2bc22200f6c04
2018-10-04 16:34:01 time 1504540875 hash 27d2aafae09d47ffc94474cce0e114c6e5585c3a61aa964e26a7c12ada343f41
2018-10-04 16:34:01 time 1504540876 hash 3bc2252b0154cb093789208406ed431567892027f87cb8684e8e21768f69c419

There's actually hundreds of entries which are all ordered except the ones with duplicate ints.

Old system had the reverse order the elements were added which is expected due to reverse being run on the set. New system sorts does not maintain the order even when std::stable_sort is used.

I could add a soft function to handle when there's a duplicate int but it seems cumbersome to do when you would expect the behaviour to be the same. If anyone can shed some light on this I'd be grateful.

[keskiverto]

Why does your "new system" output have timestamps before the "time 15*"?

The std::pair does have operator< and it should return lhs.second < rhs.second, if the .first are equal.

Make a test program that creates two pairs {foo, bar} and shows how they compare.

if ( foo < bar ) std::cout << "hello";
if ( bar < foo ) std::cout << "dolly";

That either behaves like your program, or differently. In any case, you can add further tests, like:

if ( foo.first < bar.first ) std::cout << "first";
if ( foo.second < bar.second ) std::cout << "second";

[helios]

std::sort() does not guarantee the relative order of incomparable elements (i.e. if !(x < y) && !(y < x) then x and y are incomparable). In other words, it may or may not be stable.

It sounds to me like std::stable_sort() should do what you want. If it's not, then you must be doing something wrong (or the implementation has a bug).

[NullAndVoid]

keskiverto has it with the lhs.second < rhs.second being compared if .first are equal.

It was not strings in the pair but an implementation of 256 bit uints, I tried to simplify the question. The second codebase is newer, hence added time stamps, and the 256 bit int implementation does not appear to be identical as < does not have the same behaviour.

Converting the second half of the pair and then comparing behaves as expected.

Thanks for the help.

[helios]

See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

If !(x < y) && !(y < x), they may not necessarily be equal.

bool compare(const std::pair<int, int> &a, const std::pair<int, int> &b){
    return a.first < b.first;
}

//...

std::pair<int, int> x(1, 0), y(1, 1);
assert(!compare(x, y) && !compare(y, x));

[Ganado]

Whoops, I had deleted my post right before you replied after realizing what you meant. Sorry about that...

I had originally written something along the lines of "Doesn't !(x < y) && !(y < x) just mean that they're equal".
Thanks for the reply though, I like the example.