Niepoprawna <asercja operatora w sortowaniu

Question

Próbuję zaimplementować prosty komparator do sortowania indeksów na podstawie wartości w tablicy "_vec". Otrzymuję komunikat o błędzie "run-time" niepoprawnego operatora <. I nie rozumiem, co jest nie tak z następującego kodu:

class Compare{ 
vector<int>& _vec; 
public: 
    Compare(vector<int>& vec) : _vec(vec) {} 
    bool operator()(size_t i, size_t j){ 
     if(_vec[i] != _vec[j]) 
     return _vec[i] < _vec[j]; 
     else 
     return (double)rand()/RAND_MAX < 0.5; 
    } 
}; 

Używam następujące wywołanie funkcji:

sort(inds.begin(),inds.end(),Compare(vals)); 

gdzie Inds jest tylko tablica zawierająca indeksy od 1 do 15 (powiedzmy) i vals to tablica o długości 15 z pewnymi wartościami, których posortowane indeksy chcę obliczyć. Ogólnym celem jest losowanie kolejności sortowania, gdy dwa (lub więcej) wpisów w vals są równe. Jakaś pomoc?

Answer 1

std::sort() spodziewa się, że operacja porównania będzie stabilna - jeśli dany wynik zostanie zwrócony, gdy porównane zostaną dwie pozycje, porównanie musi zwrócić ten sam wynik, jeśli elementy zostaną porównane później. Gdy zwrócisz losową wartość, oczywiście nie musi to być trzymane.

C++ 03 25,3/4 "Sortowanie i działania powiązane" mówi:

Jeśli zdefiniujemy równoważnik (a, b), jak komp (a, b) & & comp (B, A!), a następnie wymagania jest to, że zarys i equiv być zarówno stosunki przechodniego:

• o (a, b) & & zarys (b, c) oznacza zarys (a, C)
• równoważnik (a, b) & & równoważników (b, c) oznacza równoważnik (a, c)

[Uwaga: W tych warunkach, można było wykazać, że

• równ jest stosunek równoważności
• zarys indukuje również -definiowana relacja na klasach równoważności określona przez równ.
• Indukowana zależność jest ściśle uporządkowanym zbiorowo.

końcem Uwaga]

I wyjaśnienia Tabela 28 określa stosunek równoważności:

== jest równoważnością, to znaczy, że spełnia następujące właściwości:

• Dla wszystkich a, a == a.
• Jeśli a == b, to b == a.

Więc operacja Compare() nie będzie produkować relacją równoważności.

Fajnie jest uzyskać twierdzenie, a nie losowo tracić dane.

Jednym ze sposobów rozwiązania problemu randomizacji kolejności sortowania, gdy dwie (lub więcej) pozycji w _vec są równe, jest utworzenie losowej wartości dla tych indeksów i śledzenie tych losowych wartości na mapie indeksu => wartość losowa lub coś podobnego. Po prostu upewnij się, że śledzisz i używasz tych losowych wartości w taki sposób, że zachowują właściwości przechodnie i równoważności.

Answer 2

std::sort spodziewa swoje mniej niż operator dostarczył przechodni związek, to znaczy wtedy, gdy rodzaj widzi A < B jest prawdą i B < C jest prawdziwe, to implikuje że A < C jest prawdą, jak również.

W swojej implementacji reguła przechodniości nie jest zachowana: gdy dwa elementy są równe, możesz losowo powiedzieć, że jeden z nich jest większy od drugiego. Spowoduje to uruchomienie asercji debugowania.

Zwróć wartość false, aby uzyskać równe wartości, aby to naprawić.