Ich versuche, den folgenden Code mithilfe von clang zu kompilieren, habe aber den folgenden Fehler erhalten.
Ich frage mich, warum sort von der Klasse list funktionieren würde, aber nicht std::sort .
/ usr / include / c ++ / 4.2.1 / bits / stl_iterator.h: 320: 25: Fehler: ungültig Operanden zum binären Ausdruck ('iterator_type' (aka 'std :: _ List_iterator & gt;') und 'iterator_type') {return __y.base () - __x.base (); }
std::sort erfordert Direktzugriff Iteratoren, die std::list nicht bereitstellt. Folglich implementieren std::list und std::forward_list ihre eigenen Elementfunktionen zum Sortieren, die mit ihren schwächeren Iteratoren arbeiten. Die Komplexitätsgarantien dieser Mitgliedsfunktionen sind schlechter als die des effizienteren allgemeinen Algorithmus. [Whoops: siehe Kommentare.]
Darüber hinaus können die Elementfunktionen die besondere Eigenschaft der Listendatenstruktur ausnutzen, indem sie einfach die Listenknoten neu verknüpfen, während der Standardalgorithmus etwas wie swap (oder etwas mit diesem Effekt) ausführen muss, was ein Objekt erfordert Konstruktion, Zuweisung und Löschung.
Beachten Sie, dass remove() ein ähnlicher Fall ist: Der Standardalgorithmus ist lediglich eine Iteratorrückkehranordnung, während die list -Memberfunktion das Nachschlagen und das tatsächliche Entfernen auf einmal durchführt; wieder dank der Fähigkeit, das Wissen über die interne Struktur der Liste zu nutzen.