C++ Art Iteration manchmal gibt falschen Wert

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]; 
}); 

Das gibt mir eine segfault auf tour[i1] == tour[i2], und wenn ich finde, das Debuggen, dass es ist, weil i2 ist manchmal (scheinbar nicht deterministisch) viel größer als es sein sollte. ZB 403163787 (es variiert), wenn tour_indexes ist zB 0 - 20 (und ich habe zur Fehlerzeit überprüft, dass tour_indexes enthält nicht i2).

Dies alles geschieht in einer Member-Funktion in einer Klasse, die die Elementvariable tour_indexes enthält. Das Klassenobjekt befindet sich in einem shared_ptr, wenn dies relevant ist. Irgendwelche Ideen, was könnte das Problem sein? Vielen Dank.

Answer 1

Ihr Komparator bietet keine streng schwache Reihenfolge. Speziell, wenn tour[i1] == tour[i2] gibt es eine 50/50 Chance, dass es wahr oder falsch zurückgibt und die Antwort ist nicht stabil (es muss sein).

Wenn Ihre Vergleichsfunktion keine strenge schwache Ordnung liefert, ist das Verhalten undefiniert, und ein seg-Fehler ist ein plausibles Verhalten.

Ich empfehle die Verwendung return i1 < i2; Dies wird die Krawatte in einer stabilen Weise zu brechen.

Alternativ besteht keine Notwendigkeit, die Verbindung zu unterbrechen. Verwenden Sie einfach

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

std::sort ganz mit einer schwachen Ordnung glücklich ist; Das bedeutet, dass sowohl cmp(i1,i2) als auch cmp(i2,i1) false zurückgeben können. Was sie nicht bewältigen kann, ist, dass beide True zurückgeben (oder zwei Aufrufe mit denselben Argumenten, die andere Werte zurückgeben).

Answer 2

Entfernen Sie die Randomisierung im Vergleichsoperator. Vielleicht scheitert die Art Algortihm, weil sowohl i1 < i2 als auch i2 < i1 wahr sein können, wenn Elemente gleich sind.

sort gibt bereits eine zufällige Reihenfolge aus, wenn eal element und stable_sort eine deterministische Reihenfolge von gleichen Elementen im Array ergeben.