Ist Liste :: size () wirklich O (n)?

StackOverflow https://stackoverflow.com/questions/228908

Frage

Vor kurzem bemerkte ich einige Leute, dass std::list::size() erwähnen eine lineare Komplexität hat.
Nach einige in diesem Blog-Eintrag sagt :

  

Eigentlich hängt es von dem STL Sie   benutzen. Microsoft Visual Studio V6   implementiert size () als {return (_Size);   } Während gcc (zumindest in den Versionen   3.3.2 und 4.1.0) tun es als {return std :: Abstand (begin (), Ende ()); } Das   erste konstante Geschwindigkeit hat, die zweite   hat o (N) Geschwindigkeit

  1. Also meine Vermutung ist, dass für die VC ++ Menge size() konstante Komplexität als Dinkumware hat wahrscheinlich nicht diese Tatsache seit VC6 geändert. Bin gleich da ich?
  2. Wie sieht es aus wie zur Zeit in gcc? Wenn es wirklich O (n) ist, hat, warum die Entwickler entscheiden, dies zu tun?
War es hilfreich?

Lösung

Pre-C ++ 11 Antwort

Sie sind richtig, dass die Norm gibt nicht an, was die Komplexität der Liste :: size () sein muss - es aber nicht empfehlen, dass sie (Anmerkung A in Tabelle 65) „konstante Komplexität haben sollten“

.

Hier ist ein interessanter Artikel von Howard Hinnant , die erklärt, warum einige Leute denken Liste :: Größe ( ) sollte O (N) Komplexität (im Grunde, weil sie glauben, dass O (1) Liste :: size () macht Liste :: splice () haben O (N) Komplexität) und warum ein O (1) Liste :: Größe haben ( ) ist eine gute Idee sein (in der Meinung des Autors):

Ich denke, die wichtigsten Punkte in dem Papier sind:

  • gibt es wenige Situationen, in denen eine interne Zählung aufrechterhalten wird, so kann list::size() O (1) bewirkt, dass die Spleiß-Operation linear werden
  • gibt es wahrscheinlich viele weitere Situationen, in denen jemand nichts von den negativen Auswirkungen sein könnten, was passieren könnte, weil sie eine O (N) size() (wie sein ein Beispiel, wo list::size() genannt wird, während eine Sperre hält) an.
  • , die anstelle von Genehmigungs size() O (N), im Interesse der ‚am wenigsten Überraschung‘ sein, sollte der Standard alle Behälter erfordern, die size() implementiert es in einem O zu implementieren (1) Art und Weise. Wenn ein Container dies nicht kann, sollte es nicht size() überhaupt umzusetzen. In diesem Fall wird der Benutzer des Behälters bewusst gemacht werden, dass size() nicht verfügbar ist, und wenn sie noch wollen oder müssen die Anzahl der Elemente in dem Behälter erhalten, die sie noch container::distance( begin(), end()) können diesen Wert erhalten - aber sie werden ganz bewusst dass es sich um eine O (N) Betrieb ist.

Ich glaube, ich neige dazu, mit den meisten seiner Argumentation zustimmen. Aber ich mag seine vorgeschlagene Zusatz nicht auf die splice() Überlastungen. Nachdem in einem n zu übergeben, das gleich sein muß, um distance( first, last) korrektes Verhalten wie ein Rezept scheint dafür zu bekommen, schwer Fehler zu diagnostizieren.

Ich bin mir nicht sicher, was sollte oder nach vorn getan werden könnte, bewegt, da jede Änderung erhebliche Auswirkungen auf die vorhandenen Code haben würde. Aber wie es aussieht, glaube ich, dass die bestehende Code bereits betroffen ist - Verhalten sehr unterschiedlich deutlich von einer Implementierung könnte zu einem anderen für etwas, das haben sollte gut definiert. Vielleicht OneByOne Kommentar über die Größe ‚im Cache‘ mit und markierte bekannt / unbekannt könnte gut funktionieren - Sie amortisieren O erhalten (1) Verhalten - das einzig Mal, wenn Sie O (N) Verhalten ist, wenn die Liste von einigen splice () Operationen modifiziert . Das Schöne daran ist, dass es durch Implementierer heute ohne eine Änderung der Norm durchgeführt werden kann (es sei denn, ich etwas fehlt).

Soweit ich weiß, C ++ 0x ist nichts in diesem Bereich zu ändern.

Andere Tipps

In C ++ 11 ist es erforderlich, dass für jeder Standard-Container des .size() Betrieb in "konstant" Komplexität muss vollständig sein (O (1)). (Tabelle 96 - Container-Anforderungen). Bisher in 03 .size() ++ C sollte hat konstante Komplexität, ist aber nicht erforderlich (siehe Ist std :: string size () ein O (1) -Operation? ).

Die Änderung der Norm eingeführt von n2923 : die Komplexität der Größe () (Revision 1) angeben.

Doch die Umsetzung von .size() in libstdc ++ noch einen O (N) Algorithmus in gcc verwendet bis zu 4.8: 

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

Siehe auch Warum ist std :: list größer auf c ++ 11? zum Detail, warum es auf diese Weise gehalten wird.

Update : std::list::size() ist richtig O (1) bei der Verwendung von gcc 5.0 in C ++ 11-Modus (oder oben).

Durch die Art und Weise, die .size() in libc ++ ist richtig O (1): 

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Ich habe musste vor gcc 3.4 Liste :: Größe schauen, so kann ich sagen:

  1. nutzt std :: Abstand (Kopf, Schwanz)
  2. std :: Abstand hat zwei Implementierungen: für Typen, die RandomAccessIterator erfüllen, verwendet er „tail-head“, und bei den Typen, die lediglich InputIterator erfüllen, verwendet es eine O (n) Algorithmus verlassen „Iterator ++“, bis sie das Zählen trifft den gegebenen Schwanz.
  3. std :: Liste nicht satsify nicht RandomAccessIterator, so Größe ist O (n).

In Bezug auf das „Warum“, kann ich nur sagen, dass std :: list für Probleme geeignet ist, die sequentielle Zugriff erfordern. Das Speichern der Größe als Klassenvariable bei jedem Einsatz Overhead einführen würde, löschen usw., und dass Abfall ist ein großes no-no pro die Absicht der STL. Wenn Sie wirklich eine konstante Zeitgröße () benötigen, verwenden Sie std :: deque.

Ich persönlich sehe nicht das Problem mit Spleiß für O (N) als den einzigen Grund, warum Größe erlaubt ist O (N) zu sein. Sie zahlen nicht für das, was Sie nicht verwenden ist ein wichtiges C ++ Motto. In diesem Fall erfordert die Liste Größe beibehalten wird eine zusätzliche Erhöhung / Verminderung bei jedem Einsatz / löschen, ob Sie die Größe der Liste überprüfen oder nicht. Dies ist eine kleine feste Overhead, aber es ist immer noch wichtig, zu berücksichtigen.

Überprüfen der Größe einer Liste wird selten benötigt. Iterieren von beginnen, ohne Sorge der Gesamtgröße zu Ende ist unendlich häufiger.

Ich würde den Quelle ( Archiv ). SGI STL Seite sagt, dass es eine lineare Komplexität zu haben ist erlaubt. Ich glaube, dass die Designrichtlinien sie folgte, waren die Liste Implementierung zu ermöglichen, wie möglich zu sein, wie allgemein und somit mehr Flexibilität zu ermöglichen, Listen verwenden.

Dieser Bug-Report: [C ++ 0x] std :: Liste: : Größe Komplexität fängt in allen Einzelheiten die Tatsache, dass die Umsetzung in GCC 4.x lineare Zeit ist und wie der Übergang zu konstanter Zeit für ++ 11 C in der nächsten (in 5,0 erhältlich) langsam war aufgrund ABI Kompatibilität Bedenken.

Die Manpage für die GCC 4.9-Serie umfasst noch den folgenden Haftungsausschluss:

  

Unterstützung für C ++ 11 ist nach wie vor   experimentell und kann in inkompatiblen Weise in zukünftigen Versionen geändert werden.

Der gleiche Fehlerbericht wird hier verwiesen: Sollte std :: list :: Größe haben konstante Komplexität in C ++ 11

Wenn Sie richtig Listen verwenden Sie nicht wahrscheinlich einen Unterschied bemerken.

Listen sind gut mit großen Datenstrukturen, die Sie ohne das Kopieren neu anordnen mögen, von für Daten, die Sie gültige Zeiger nach dem Einsetzen behalten mögen.

Im ersten Fall macht es keinen Unterschied, in den zweiten würde ich die alte (kleinere) Größe () Implementierung bevorzugen.

Wie auch immer std ist mehr über die Richtigkeit und Standard behavious und 'user Freundlichkeit' als reine Geschwindigkeit.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top