Unterschiede: set-vector
-
Ich glaube die set war sortiert, aber welche unterschiede gibt es noch???
-
Achja, noch nebenbei; ist ne map so etwas wie ne Dictionary???
-
Was mir jetzt so einfaellt:
set ist sortiert
set enthaelt jedes Element nur einmal (multiset wenns mehrmals sein soll)
einige Methoden sind nicht gleich/beim set nicht vorhanden (siehe www.cppreference.com)
suchen ist beim set selbstverstaendlich schneller, einfuegen langsamer (denke ich zumindest)
-
In Kurzfassung: Du versuchst hier Äpfel mit Birnen zu vergleichen - set<> und vector<> sind zwei völlig verschiedene Containerkonzepte.
Shinja schrieb:
Was mir jetzt so einfaellt:
set ist sortiert
set enthaelt jedes Element nur einmal (multiset wenns mehrmals sein soll)
einige Methoden sind nicht gleich/beim set nicht vorhanden (siehe www.cppreference.com)Bis dahin stimme ich zu.
suchen ist beim set selbstverstaendlich schneller, einfuegen langsamer (denke ich zumindest)
Nein, auch Einfügen ist beim set<> (Laufzeit O(log n) meistens schneller als beim vector<> (Laufzeit idR O(n) - außer push_back()).
AGS'ler schrieb:
Achja, noch nebenbei; ist ne map so etwas wie ne Dictionary???
Ja, so kannst du sie verwenden (auch bekannt als "Assoziatives Array").
-
Ups, sry, ich meinte eigentlich push_back, hab das falsch hingeschrieben. So ist's natürlich falsch. Danke fürs korrigieren.
Wenn es eine logarithmische Laufzeit hat, dann ist das set wohl als list oder als deque implemntiert, üblicherweise? Oder wurde beim set keiner der 3 Container als unterliegende Datenstruktur verwendet?
-
Shinja schrieb:
Wenn es eine logarithmische Laufzeit hat, dann ist das set wohl als list oder als deque implemntiert, üblicherweise? Oder wurde beim set keiner der 3 Container als unterliegende Datenstruktur verwendet?
Üblicherweise wird für (multi)set und (multi)map ein balancierter binärer Suchbaum als Datenstruktur verwendet - ist effektiver zu handhaben als eine doppelt verkettete Liste (std::list) oder ein dynamisches Array (std::vector oder std::deque).
-
Danke!
Klingt auch logischer, hehe.