Freddard Freddard - 27 days ago 13
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.)

Comments