Was sind die Komplexitätsgarantien der Standardcontainer?

Lesezeit: 4 Minuten

Was sind die Komplexitatsgarantien der Standardcontainer
Martin York

Anscheinend 😉 bieten die Standardcontainer eine Art Garantie.

Welche Art von Garantien und was genau sind die Unterschiede zwischen den verschiedenen Containertypen?

Arbeiten von die SGI-Seite (Über STL) Mir ist folgendes eingefallen:

Container Types:
================
Container:
    Forward Container
        Reverse Container
            Random Access Container
    Sequence
        Front Insert Sequence
        Back  Insert Sequence
    Associative Container
        Simple   Associative Container
        Pair     Associative Container
        Sorted   Associative Container
        Multiple Associative Container

Container Types mapped to Standard Containers
=============================================

std::vector:    Sequence    Back        Sequence                    Forward/Reverse/Random Container
std::deque:     Sequence    Front/Back  Sequence                    Forward/Reverse/Random Container
std::list:      Sequence    Front/Back  Sequence                    Forward/Reverse Container
std::set:       Sorted/Simple/Unique    Associative Container       Forward Container
std::map:       Sorted/Pair/Unique      Associative Container       Forward Container
std::multiset:  Sorted/Simple/Multiple  Associative Container       Forward Container
std::multimap:  Sorted/Pair/Multiple    Associative Container       Forward Container


Container Guarantees:
=====================

                                                                                  Simp
                                                                                  or
                          For   Rev  Rand        Front  Back  Assoc        Sort   Mult
                    Cont: Cont: Cont Cont: Sequ: Sequ:  Sequ: Cont:        Cont:  Cont:
Copy    Const:      O(n)
Fill    Const:                             O(n)
begin()             O(1)
end()               O(1)
rbegin()                        O(1)
rend()                          O(1)
front()                                    O(1)
push_front()                                     O(1)
pop_front()                                      O(1)
push_back()                                             O(1)
pop_back()                                              O(1)
Insert()                                                                          O(ln(n))
Insert: fill                               O(n)
Insert: range                              O(n)                                   O(kln(n)+n)
size()              O(1)
swap()              O(1)
erase key                                                     O(ln(n))
erase element                                                 O(1)
erase range                                                   O(ln(n)+S)
count()                                                       O(log(n)+k)
find()                                                        O(ln(n))
equal range                                                   O(ln(n))
Lower Bound/Upper Bound                                                    O(ln(n))
Equality                  O(n)
InEquality                O(n)
Element Access                       O(1)

  • Fang hier an: STL-Komplexitätsspezifikationen. Lesen Sie dann alle Containertypen auf dieser Website durch und sehen Sie sich die angegebenen Komplexitätsanforderungen an. Hoffe das hilft!

    – Chris Jester-Young

    8. Oktober 2008 um 7:42 Uhr


  • Kann ich eine Kopie Ihrer Arbeit haben, um sie in meiner Klasse zu studieren?

    – Dzung Nguyen

    7. Mai 2010 um 4:14 Uhr

  • @nXqd: siehe www.sgi.com/tech/stl

    – Martin York

    9. Mai 2010 um 17:13 Uhr

  • @MartinYork Dieser Link ist jetzt tot.

    – Chani

    23. März 2018 um 10:29 Uhr

  • john-ahlgren.blogspot.com/2013/10/… Schau doch einfach mal hier vorbei 🙂

    – Schalomi90

    20. November 2018 um 14:27 Uhr

1646979606 699 Was sind die Komplexitatsgarantien der Standardcontainer
Nayana Adassuriya

Ich habe die nette Ressource gefunden Standard-C++-Container. Wahrscheinlich ist es das, wonach Sie alle suchen.

VEKTOR

Konstrukteure

vector<T> v;              Make an empty vector.                                     O(1)
vector<T> v(n);           Make a vector with N elements.                            O(n)
vector<T> v(n, value);    Make a vector with N elements, initialized to value.      O(n)
vector<T> v(begin, end);  Make a vector and copy the elements from begin to end.    O(n)

Accessoren

v[i]          Return (or set) the I'th element.                        O(1)
v.at(i)       Return (or set) the I'th element, with bounds checking.  O(1)
v.size()      Return current number of elements.                       O(1)
v.empty()     Return true if vector is empty.                          O(1)
v.begin()     Return random access iterator to start.                  O(1)
v.end()       Return random access iterator to end.                    O(1)
v.front()     Return the first element.                                O(1)
v.back()      Return the last element.                                 O(1)
v.capacity()  Return maximum number of elements.                       O(1)

Modifikatoren

v.push_back(value)         Add value to end.                                                O(1) (amortized)
v.insert(iterator, value)  Insert value at the position indexed by iterator.                O(n)
v.pop_back()               Remove value from end.                                           O(1)
v.assign(begin, end)       Clear the container and copy in the elements from begin to end.  O(n)
v.erase(iterator)          Erase value indexed by iterator.                                 O(n)
v.erase(begin, end)        Erase the elements from begin to end.                            O(n)

Weitere Container finden Sie auf der Seite.

Mir ist nichts wie eine einzelne Tabelle bekannt, mit der Sie alle auf einen Blick vergleichen können (ich bin mir nicht sicher, ob eine solche Tabelle überhaupt machbar wäre).

Natürlich listet das ISO-Standarddokument die Komplexitätsanforderungen im Detail auf, manchmal in verschiedenen recht lesbaren Tabellen, manchmal in weniger lesbaren Stichpunkten für jede spezifische Methode.

Auch die STL-Bibliotheksreferenz unter http://www.cplusplus.com/reference/stl/ liefert gegebenenfalls die Komplexitätsanforderungen.

  • Die Informationen auf cplusplus.com sind veraltet (und manchmal falsch). Bitte verweisen Sie die Leute auf de.cppreference.com/w/cpp/container stattdessen. Für jede Methode jedes Containers ist die vorgeschriebene Komplexität aufgeführt.

    – Duthomhas

    9. November 2021 um 17:37 Uhr

Eine weitere schnelle Nachschlagetabelle ist hier verfügbar github-Seite

Hinweis : Dies berücksichtigt nicht alle Container wie unordered_map usw., ist aber dennoch großartig anzusehen. Es ist nur eine sauberere Version von Das

990080cookie-checkWas sind die Komplexitätsgarantien der Standardcontainer?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy