Ich mag würde die Komplexität in Big O-Notation der STL multiset wissen, Karte und Hash-Map-Klassen, wenn:multiset, Karte und Hashzuordnung Komplexität
Sie diese Informationen in der SGI STL-Dokumentation finden: http://www.sgi.com/tech/stl/
Grundsätzlich sind sowohl Multiset als auch Maps sortierte Binärbäume, sodass das Einfügen/Finden von 1 von N Einträgen O (log N) erfordert. Siehe Sortierte Assoziation. Container in der Dokumentation.
Offensichtlich ist der große Vorteil von Hashmap O (1) zum Einfügen und Suchen von Einträgen.
Zugriff nach gefunden ist O (1) für alle Strukturen. Vergleich, was meinst du damit? Klingt nach O (1) zu mir, nachdem alle gefunden wurden.
Diese implementiert sind ein red-black tree, eine Art von balanced binary search tree. Sie haben folgende asymptotische Laufzeiten:
Insertion: O (log n)
Lookup: O (log n)
Löschung: O (log n)
Diese werden mit hash tables implementiert. Sie haben folgende Laufzeiten:
Insertion: O (1) erwartet, O (n) im schlechtesten Fall
Lookup: O (1) erwartet, O (n) im schlechtesten Fall
Löschung: O (1) zu erwarten, O (n) worst case
Wenn Sie eine ordnungsgemäße Hash-Funktion verwenden, werden Sie fast nie das Worst-Case-Verhalten sehen, aber es ist etwas zu beachten - siehe this paper für ein Beispiel.
Sagt alles, was Sie sagen über 'hash_ *' beziehen sich auf C++ 11 ungeordnet und Boost.Onordered Container? – myWallJSON
@myWallJSON: ja – sehe
Die Klassenschablonen 'hash_ *' sind Teil von [Silicon Graphics STL] (https://www.sgi.com/tech/stl/). Diese wurden in die C++ 11-Revision unter 'unordered_ *' - Namen (unordered_map, unordered_set, etc.) aufgenommen. Außerdem wurden sie in die Bibliotheken libstdC++, Visual C++ und Boost C++ aufgenommen. – soliosg
cppreference.com ist, wo ich für meine C++ Referenzfragen gehe. Sie machen einen ziemlich guten Job, indem sie die Big-O-Notation für die meisten der oben erwähnten Funktionen umreißen.
Dies ist eigentlich mein Beitrag und ich kann nicht verstehen, warum ich inaktiv und damit nicht ändern kann ... – Harry