Das Spleißen eines Bereichs von einer Liste zu einer anderen kann in konstanter Zeit erfolgen, wobei die Komplexität von size() linear ist.
C ++ 11 hat das im Fall von std::list geändert, indem size() als konstante Zeit benötigt wird. Dies hat zum Beispiel die Implementierung von gcc durchbrochen, siehe [C ++ 0x] std :: list :: size-Komplexität .
Abgesehen vom Bereich splice() gibt es einen anderen Grund, warum size() in der früheren, C ++ 03-konformen % -Konfiguration nicht als konstante Zeit definiert werden konnte. co_de% Implementierungen?
Warum wird eine ganze Liste oder ein linearer Bereich für std::list ?
Siehe std::forward_list , Fälle (1) und (3). Siehe auch 23.3.4.6 forward_list-Operationen [forwardlist.ops] im Standardentwurf N3485 . Das splice_after() implementiert nicht einmal std::forward_list .
Ich weiß, forward_list ist eine einfach verknüpfte Liste, aber ich sehe nicht, warum man den Bereich size() nicht in konstanter Zeit machen kann. Vermutlich vermisse ich hier etwas Triviales ...
BEARBEITEN: OK, es war zumindest teilweise mein Missverständnis, ich erwartete, dass 4 nicht in der Quellenliste verbleiben würde. Code:
%Vor%Ausgabe:
%Vor% Wie würden Sie im Fall einer forward_list den Bereich spleißen_ nach konstanter Zeit machen? In der Quellenliste haben Sie nur die Iteratoren. Um die Knoten aus der verknüpften Quellverweisliste zu entfernen, benötigen Sie den Knoten unmittelbar vor last . Daher müssen Sie die Quelle linear nach diesem verknüpften Listenknoten durchsuchen. Daher ist es linear in der Entfernung zwischen first und last
Die Version, die die gesamte Quellenliste verwendet, muss immer noch unmittelbar vor dem Ende der Quelle nach dem Knoten suchen, damit sie so geändert werden kann, dass sie auf das Element nach dem Splice im Ziel verweist. Also benötigt es auch lineare Zeit in der Größe der Quelle.
Der Bereichsspleiß ist der einzige Grund, warum size in früheren C ++ - Standards keine konstante Zeit gewesen wäre. Tatsächlich hat der Sun CC-Compiler size konstante Zeit und alle Versionen von splice linear gewählt.
Das Spleißen einer ganzen Forward-Liste ist linear, da Sie die Liste, die Sie zusammenführen, durchqueren müssen, um den letzten Knoten wieder mit der Liste verknüpfen zu können, in die Sie spleißen. Ich kann nicht herausfinden, warum der Bereichsspleiß jedoch linear ist.
EDIT: Wie @Xeo hervorhebt, benötigt die range-basierte Version auch lineare Zeit, da last nicht im Bereich enthalten ist und von first gesucht werden muss, um den Iterator vor last .
Tags und Links c++ c++11 list splice forward-list