Ändert std :: sort die relative Reihenfolge gleicher Elemente?

Question

Gewährleistet der Standard, dass sich die Reihenfolge gleicher Elemente nicht ändert (wie, vergessen Sie den Begriff dafür), indem Sie std :: sort verwenden oder muss ich eine alternative Lösung in Betracht ziehen, um dieses Ziel zu erreichen?

Answer 1

std::sort nicht als stabil gewährleistet ist (der Begriff, den Sie zu denken versuchten). Wie Sie vermuten, ist std::stable_sort garantiert stabil. std::stable_sort bietet auch eine Garantie für Worst-Case-Komplexität, die std::sort nicht tut. std::sort ist jedoch im Durchschnitt normalerweise schneller.

Answer 2

Nein, wenn Sie die Garantie Verwendung std :: wollen stable_sort

Answer 3

Nein, es explizit dies nicht garantieren. Wenn Sie die relative Reihenfolge beibehalten müssen, verwenden Sie stattdessen stable_sort.

Dokumentation der Art, die sich auf entsprechende Elemente

• http://msdn.microsoft.com/en-us/library/ecdecxh1(VS.80).aspx

Answer 4

Der Begriff für das, was ist stability Sie beschreiben, enthält.

Von SGI STL docs:

Hinweis: sort ist nicht stabil sein garantiert.

Verwenden Sie stable_sort, wenn Sie dies benötigen.

Answer 5

Von C++ Referenz: here

Elemente, die zueinander gleich vergleichen würden nicht ihre ursprüngliche relative Ordnung zu halten garantiert.

Sie könnten stable_sort, wollen aber beachten Sie, dass es (im Durchschnitt) nicht so schnell ist