Doppelte Einträge verbieten - vector, list oder deque?
-
Hi,
Was sollte ich nehmen, wenn ich doppelte Einträge in einem Array verbieten möchte?
Man könnte natürlich vorm hinzufügen jedesmal mit find() suchen usw., aber geht das auch schneller/besser?
Danke
-
std::set verwenden
-
Danke, das sieht ganz gut aus.
-
temp schrieb:
Was sollte ich nehmen, wenn ich doppelte Einträge in einem Array verbieten möchte?
Shade Of Mine schrieb:
std::set verwenden
Seid wann lässt sich ein Array mit std::set anlegen?
-
FritzeX schrieb:
temp schrieb:
Was sollte ich nehmen, wenn ich doppelte Einträge in einem Array verbieten möchte?
Shade Of Mine schrieb:
std::set verwenden
Seid wann lässt sich ein Array mit std::set anlegen?
Wer sagt denn das es dann noch ein Array ist?
-
Die Eigenschaften eines Arrays (alle Elemente liegen nacheinander im Speicher, wodurch auch Random Access möglich wird) ist bei
std::setnatürlich nicht mehr gegeben. Aber wenn einem das nichts ausmacht, ist ein Set eine gute Wahl.
-
Nexus schrieb:
Die Eigenschaften eines Arrays (alle Elemente liegen nacheinander im Speicher, wodurch auch Random Access möglich wird) ist bei
std::setnatürlich nicht mehr gegeben. Aber wenn einem das nichts ausmacht, ist ein Set eine gute Wahl.Es spricht nichts dagegen ein set zur implementation eines arrays zu verwenden. etwas hoeherer Speicherbedarf aber dafuer recht trivial ein array ohne doppelte elemente realisierbar.
-
Shade Of Mine schrieb:
Es spricht nichts dagegen ein set zur implementation eines arrays zu verwenden. etwas hoeherer Speicherbedarf aber dafuer recht trivial ein array ohne doppelte elemente realisierbar.
Ja, aber es ist dann eben kein Array mehr. Wenn man lineare Zeit für Random Access benötigt, kann das besonders bei grossen Containern mühsam werden.
Oder wenn nicht alle Elemente sortiert sein sollen...
-
Nexus schrieb:
Ja, aber es ist dann eben kein Array mehr. Wenn man lineare Zeit für Random Access benötigt, kann das besonders bei grossen Containern mühsam werden.
Oder wenn nicht alle Elemente sortiert sein sollen...
Du kannst 2 Container nehmen:
eine std::map/std::set fuer die werte (als key) und einen std::vector mit iteratoren in die map.so hast du O(1) random access und O(log n) insert.
Das Problem mit nur einem array als implementierung waere, dass du nicht in O(log N) inserten kannst, da du entweder einen nicht sortierten container hast oder aber kopieren musst um ein element in der mitte einfuegen zu koennen (eben dort wo es laut sortierung sein muesste).
auf diese art und weise kannst du dir neue datenstrukturen bauen die fuer dich passende komplexitaeten haben.
-
Du hast Recht, das klingt sehr praktisch. So kann man relativ gut einen Wrapper-Container anbieten, der intern einen assoziativen und einen sequenziellen verwaltet.
Danke für deine Antwort!
