Ich habe C ++ 11% forward_list als Container für schnelle Einfügungen ohne viel Speicheraufwand verwendet, da es sich um eine einfach verknüpfte Liste handelt.
Nachdem ich erkannt habe, dass forward_list keine size() -Methode hat, bin ich etwas verwirrt über die Gründe dahinter. Könnte es nicht einfach ein privates Feld behalten, das die eingefügten und entfernten Knoten verfolgt und somit eine Operation O (1) size () implementiert?
N2543 ist der Vorschlag, und er hat eine ausführliche Diskussion über size() .
Die Entscheidung zwischen Option 3 [keine Angabe von
size()] und Option 2 [die Angabe von O (1)size()] ist eher eine Frage der Beurteilung. Ich habe Option 3 aus dem gleichen Grund ausgewählt, aus dem ich die Option "Einfügen nach" gewählt habe anstelle von Insert-Before: Option 3 ist konsistenter mit dem Ziel von Overhead im Vergleich zu einer handgeschriebenen C-style Linked List. Die Verwaltung einer Zählung verdoppelt die Größe einesforward_list-Objekts (1 Wort für den Listenkopf und eins für die Zählung), und es verlangsamt jeden Operation, die die Anzahl der Knoten ändert. In den meisten Fällen ist dies nicht ein Veränderung der asymptotischen Komplexität (die einzige Veränderung asymptotisch Komplexität ist in einer der Formen vonsplice), aber es ist nicht Null Overhead. Es ist eine Kosten, dass alle Benutzer bezahlen müssten, ob Sie benötigen diese Funktion oder nicht, und für Benutzer, die sich interessieren eine Zählung aufrechtzuerhalten, ist es genauso einfach, es außerhalb zu halten Liste, indem die Zählung mit jeder Einfügung inkrementiert und dekrementiert wird mit jedem Löschen, wie es ist, um die Zählung in der Liste zu halten.
Die STL-Container haben traditionell / intelligent die Merkmale von Datenstrukturen entfernt, die in Bezug auf Zeit und Raum nicht gut funktionieren.
Zitat von "C ++ - Standardbibliothek hinzufügen - ein Tutorial und eine Referenz"
A
std::forward_listbietet keinesize()-Memberfunktion. Dies ist eine Folge des Weglassens Features, die Zeit oder Platz Overhead relativ zu einer handgeschriebenen einfach verknüpften Liste erstellen.
Ich frage mich, ob das Standard-Komitee ein Mix-In als Template-Parameter betrachtet, das die Pflege eines optionalen Size-Mitglieds zu den Listen-Klassen hinzufügen kann? Dies hätte der Klasse erlaubt, eine optionale Elementzählung zu haben, ohne die Allgemeinheit zu verlieren.
gefällt das
%Vor%/ Diese Frage wurde als dupliziert markiert, also füge sie hier hinzu /
Tags und Links c++11 stl forward-list