Freddard - 27 days ago 13

C++ Question

`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]`

`i2`

`tour_indexes`

`tour_indexes`

`i2`

This all happens in a member function in a class containing the member variable

`tour_indexes`

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.)

Source (Stackoverflow)

Comments