Freddard Freddard - 3 months ago 36
C++ Question

C++ sort iteration sometimes gives wrong value

tour_indexes.clear();
for (int i=0; i<num_of_cities; i++)
{
tour_indexes.push_back(i);
}

mt19937 gen(random_engine());
uniform_real_distribution<> dis(0, 1);

// Sort indexes based on comparing values in tour. Choose at random if equal
sort(tour_indexes.begin(), tour_indexes.end(),
[&tour, &dis, &gen](int &i1, int &i2)
{
if (tour[i1] == tour[i2])
{
return dis(gen) < 0.5;
}
return tour[i1] < tour[i2];
});


This gives me a segfault on
tour[i1] == tour[i2]
, and when debugging I find that it is because
i2
is sometimes (seemingly non deterministic) way bigger than it should be. F.ex 403163787 (it varies) when
tour_indexes
is f.ex 0 - 20 (and I've double checked at error time that
tour_indexes
does not contain
i2
).

This all happens in a member function in a class containing the member variable
tour_indexes
. The class object is in a shared_ptr if that is relevant. Any ideas what might be the problem? Thanks.

Answer

Your comparator does not provide a strict weak ordering. Specifically, if tour[i1] == tour[i2] there is a 50/50 chance that it will return true or false and the answer is not stable (it must be).

If your comparison function does not provide a strict weak ordering, the behaviour is undefined, and a seg-fault is one plausible behaviour.

I suggest using return i1 < i2; This will break the tie in a stable way.

Alternatively, there is no need to break the tie at all. Just use

[&tour](int i1, int i2) 
{
    return tour[i1] < tour[i2]; 
}

std::sort is quite happy with a weak ordering; which means that both cmp(i1,i2) and cmp(i2,i1) may return false. What it can't cope with is them both returning true (or two calls with the same arguments returning different values.)