was ist die zugrunde liegende Datenstruktur der STL-Liste, Vektor und einstellen?

was ist die zugrunde liegende Datenstruktur der STL-Liste, Vektor und einstellen ?

Meine Lösung:

  • Vektor : (dynamisch zugewiesene) array
  • Liste: ?
  • set: heap (oder einen binären Baum mit allen Blatt-Knoten befindet sich Links wie möglich und halten Sie min/max-element auf der Oberseite)

Recht?

  • Umsetzung definiert, aber im Allgemeinen std::vector ist eines dynamisch reservierten Arrays. std::list ist eine doppelt verkettete Liste (C++11 führt std::forward_list ist eine einfach verkettete Liste), und eine set basieren in der Regel auf rot-schwarz-Bäume, wenn nichts passt, dass die amortisierten Komplexität und Verhalten-Anforderungen an die Schnittstellen in der Norm definiert sind akzeptabel Implementierungen.
InformationsquelleAutor user1002288 | 2011-10-26
  1. 20

    Basierend auf Kommentare, um zu klären, diese sind die am häufigsten verwendeten Optionen, aber basierend auf den gewünschten Komplexität und anderer Faktoren, die Unterstützung von diese Implementierungen können variieren:

    Vektor = dynamisch Größenänderung array

    Liste = Doppelt Verkettete Liste

    Set = Rot/Schwarz-Baum (ausgeglichener Binärer Suchbaum)

    Ich glaube, Sie könnte möglicherweise mischen Haufen und BSTs. Ein heap ist visualisiert, wie ein Baum, aber es ist eigentlich basiert auf einer Wendeplatten-Verzeichnis-Struktur (z.B. array-oder vector). C++ - heap-Funktionen über die Algorithmus header in der STL . BSTs sind eher ein Schlüssel/Wert-basierte Struktur zur effizienten lookup (das ist, was Sie wollen in der Regel für ein Satz).

    • list ist eine doppelt verkettete Liste
    • Dies ist in der Regel wahr, aber beachten Sie, dass dies nicht die einzige option (es ist von der Implementierung abhängig).
    • Karte ist rot-schwarz-Baum-set ist nicht, weil die Elemente nicht sortiert sind. Was ist der Unterschied zwischen Liste und verkettete Liste ? was ist die Datenstruktur "verkettete Liste" ? eine Liste?
    • Dies ist von der Implementierung Abhängig, aber die Komplexität, die die Standard-Anforderungen, lässt wenig Optionen für drastisch unterschiedliche Implementierungen.
    • hat die Bestellung den Anforderungen. C++11 ist std::unordered_set nicht. Ein doppelt verkettete Liste ist eine Gruppe von Knoten, die Verweise auf die Knoten davor und danach (oder NULL).
    • Obwohl in der Praxis Sie haben Recht, der standard-Bibliothek-implementation ist frei, welche Datenstrukturen es will, solange Sie erfüllen die Garantien und die Schnittstellen in der Norm festgelegt sind.
    • Gute call. Ich werde klären.
    • stimmt, aber std::list unterstützt bidirektionale Iteratoren und -- muss Konstante Zeit. Plus die andere zeitliche Einschränkungen, es wäre eine Herausforderung zu implementieren, die Liste nicht eine doppelt-verkettete Liste.
    • Zugegeben, es kann variieren. Karte, Set, MultiSet und MultiMap sind wirklich Abstrakte Datentypen (ADTs) definieren Verhalten. Die zugrunde liegende Implementierung umgesetzt werden könnte, mit allen Daten-Struktur (in der Regel eine BST-Variante oder eine hashtable) abhängig von der gewünschten Komplexität und die Durchführung der Launen.
    • Ich war eigentlich reagiert nicht auf @Praetorian und bezog sich auf set, die leicht implementiert werden zahlreiche Möglichkeiten 🙂

    InformationsquelleAutor Brent Writes Code
  2. 5

    Der standard gibt keine Garantien, auf welche Datenstrukturen verwendet werden, gibt es nur die Komplexität garantiert, so dass die Umsetzung können Sie wählen Sie eine Struktur, die erfüllt Sie.

    Sagte, std::vector ist in der Regel eine dynamische array, std::list ist wahrscheinlich ein doppelt verknüpfte Liste und std::set ist meist irgendeine Art von self-balancing binary tree.

    InformationsquelleAutor Fanael
Schreibe einen Kommentar