Ist das nicht unoptimized? Warum machen die das?

Methode size() der std::list (Quelle):

size_type size() const {
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
  }

Oder wären die 4 Bytes, um den Wert vorrätig zu halten die Katastrophe? Speicher ist ja knapp heutzutage.

Ponto

Optimizer schrieb:

Oder wären die 4 Bytes, um den Wert vorrätig zu halten die Katastrophe? Speicher ist ja knapp heutzutage.

Du hast die Wahl. Entweder ist size() in O(1) oder splice(). Beides geht nicht. Die einen entscheiden sich so und die anderen anders. Ich würde mich immmer dafür entscheiden splice() in O(1) zu machen, da size() bei Listen nicht so wichtig ist.

volkard

Optimizer schrieb:

Oder wären die 4 Bytes, um den Wert vorrätig zu halten die Katastrophe? Speicher ist ja knapp heutzutage.

wozu? wer will jemals size() auf ner liste aufrufen?
derjenige häte wahrscheinlich eher queue oder vector nehmen sollen, oder?

Vermutlich. Das mit dem splice() ist mir jetzt aber nicht klar. Deshalb müsste man doch trotzdem den Wert vorrätig halten können.
Ich versteh halt nicht, warum man etwas "künstlich" langsam halten sollte.

Es ist eine Sache, keine Dienste anzubieten, die aufgrund der Datenstruktur nicht performant sind. Aber etwas künstlich langsam zu machen, find ich dann doch ein bissl krass.

Ponto

Optimizer schrieb:

Vermutlich. Das mit dem splice() ist mir jetzt aber nicht klar. Deshalb müsste man doch trotzdem den Wert vorrätig halten können.
Ich versteh halt nicht, warum man etwas "künstlich" langsam halten sollte.

Es ist eine Sache, keine Dienste anzubieten, die aufgrund der Datenstruktur nicht performant sind. Aber etwas künstlich langsam zu machen, find ich dann doch ein bissl krass.

Schau dir mal die Funktion an:

void splice(iterator position, 
            list<T, Alloc>& x,
            iterator first, iterator last);

Hier wird ein Bereich aus x rausgeschnitten und vor position eingefügt. Ohne einen size member kann man das in konstanter Zeit machen. Mit einem size member, muß man die Elemente zwischen first und last zählen, um die Variable in beiden Listen aktuell zu halten. Das kostet halt lineare Laufzeit.

Gut, leuchtet irgendwo auch ein.

Ponto

Ich glaube Scott Meyers hat dem Thema ein Item (4) in seinem Buch Effective STL gewidmet. Falls du es zur Hand hast, werden dort auch ein paar Infos sein.

Ringding

http://www.sgi.com/tech/stl/FAQ.html, "Why is list<>::size() linear time?"

volkard

Optimizer schrieb:

Vermutlich. Das mit dem splice() ist mir jetzt aber nicht klar. Deshalb müsste man doch trotzdem den Wert vorrätig halten können.
Ich versteh halt nicht, warum man etwas "künstlich" langsam halten sollte.
Es ist eine Sache, keine Dienste anzubieten, die aufgrund der Datenstruktur nicht performant sind. Aber etwas künstlich langsam zu machen, find ich dann doch ein bissl krass.

vorrätig halten und bei jedem splice invalidieren? also nur als cache? und slange der benutzer nicht spliced isses schnell. jo, das geht.

aber das problemchen ist ein anderes. will man das? wenn ich verkettete listen baue, dann haben die gewöhlich nur push_front(), pop_front(), get_front(), is_empty(), ctor und dtor. eben genau die operationen, die auf dieser art einfach verketter listen schweineeffizient sind. winn ich push_back() und pop_front() haben, nehme ich halt ne einfach zyklisch verkettete liste oder ne einfach verkettet mit start- und ende-zeiger. meine listen haben niemals sort. und natürlich auch niemals nen op[] mit nem int als argment. das paßt einfach nicht zu den listen. es ist nicht natürlich.
und size() ist auch nicht ne neatürliche eigenschaft von verketteten listen. es gibt so viele datenstrukturen. so viele kombinationen derer. ach, die kann ja kein mensch aufzählen.
die stl bietet gerade mal ne hand voll davon an. und niemals mit dem anspruch auf vollständigkeit, sondern mit der klaren ansage, daß man selber welche dazubasteln soll. die hashtable ist damals rausgelassen worden mit dem klaren gedanen, "ach, die hat man ja so schnell dazugebaut, sollen die user mal machen". was seltsamerweise aber nicht pasiert ist!
ok, manche stl-implementierung hat ne hash_map angeboten. aber kam mal was von usern? wie oft sehe ich hier im forum, daß einer ne stl-kompatible datenstruktur bauet?
na, egal. die paar stl-datenstrukturen sollen gar nicht alles abdecken. sie sollen das ausdrücken, was sie sind. und ne liste ist in erster linie ne liste. und die kennt ihre größe natürlich nicht.
aber das willste nicht einsehen, ist mir klar. du willst mehr komfort, koste es was es wolle.

dann siehste vielleicht folgendes ein:
ich kann mir mit nem trivialen wraper um die std::liste ne vh::liste basteln, die ihre größe mitschreibt (und gegebenenfalls auch mal invalidiert). so können wir mit unerheblich wenig aufwand beide versionen benutzen. die mit size und die ohne.
gäbe es in der stl nur die version mit size, könnte ich mir unmöglich nen wrapper bastern, der die size nicht hat.

und überhaupt, kompromisse werden in der stl genug geschlossen. hat dein baum in der map auch aufwärtszeiger, die immer mitgeführt werden müsen, aber ausschließlich dafür notwendig sind, daß die iteratoren fein laufen können? mir ist es ein graus, dran zu denken, über ne map zu iterieren.