Teile einer std::list<> sortieren

Hallo,

ist es mit einer std::list<> möglich, nur bestimmte Teile einer dieser Liste zu sortieren?
Weil die Funktion std::list<>::sort() nimmt ja keine Iteratoren als Argumente entgegen.

SeppJ

Dann nimm doch std::sort. Ist dann allerdings weniger effizient. Oder teil die Liste kurzfristig in Unterlisten die du danach wieder zusammenfügst.

Bleiben die Iteratoren gültig, wenn std::sort() auf eine Liste angewandt wird?
Ansonsten ist die zweite Methode glaube ich besser.

camper

Du könntest mit splice die Liste auseinandernehmen und den zu sortierenden Teil in eine andere Liste verschieben und dort sortieren. danach einfach splice zurück. Dummerweise hat splice die unangenehme Eigenschaft, alle Iteratoren und Referenzen auf die ursprüngliche Liste ungültig zu machen, falls die zu sortierende Sequenz also nicht am Anfang oder Ende der Liste liegt, kann es umständlich sein, die Einfügestelle wiederzufinden. Abgesehen davon ist splice leider nicht in allen Implementationen mit konstanter Komplexität ausgeführt (nämlich all denen, für die size() konstante Laufzeit hat).

void sortrange(list<T>& x, list<T>::iterator begin, list<T>::iterator end)
{
    list<T>::difference_type delta = difference( x.begin(), begin );
    list<T> tmp;
    tmp.splice( tmp.begin(), x, begin, end );
    // ALLE Iteratoren zu x sind ab hier ungültig, insbesondere begin und end
    tmp.sort();
    begin = x.begin();
    advance( begin, delta );
    x.splice( begin, tmp, tmp.begin() );
}

2. Iteratoren bleiben unter sort gültig (es gibt allerdings verbugte Implementationen, vc++2003 etwa vernichtet den end()-Iterator).

camper schrieb:

begin = x.begin();
advance( begin, delta );

Was bewirken denn diese beiden Zeilen?

drakon

http://www.cplusplus.com/reference/std/iterator/advance/

Teile einer std::list&lt;&gt; sortieren

Teile einer std::list<> sortieren