Woher weiss ich welche Datenstruktur ich nutzen sollte?

[sollteichwissen]

Ich will eine Multimap implementieren bei der einfuegen und loeschen moeglichst schnell sein sollen.

Wie finde ich raus welche Datenstruktur ich verwenden sollte?

Fuer C++ gibt es wohl multimap und hash_multimap. ich glaube multimap verwendet einen red-black-tree oder sowas.

laut wikipedia sind die zeitkomplexitaeten bei einem red-black-tree fuer einfuegen und loeschen(average, worst case):

Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)

fuer die hash-table sind's:

Insert	O(1)		  O(1)
Delete	O(1 + n/k)	O(n)

das sieht so aus als waere die hash-table fuer's einfuegen besser, aber das loeschen hab ich nich so ganz verstanden. daher weiss ich nicht wie ich das vergleichen soll

was gibt's sonst noch fuer sinnvolle datenstrukturen?

in was fuer quellen wuerdet ihr nachkucken wenn ihr sowas rausfinden muesstet?

[rüdiger]

Du meinst wohl unordered_multimap . Für C++ gibt es folgenden praktischen Leitfaden: http://www.linuxsoftware.co.nz/containerchoice.png Leider wurde er nicht für C++11 (unordered_*, forward_list, array) erweitert.

[kellerassel]

sollteichwissen schrieb:

fuer die hash-table sind's:

Insert	O(1)		  O(1)
Delete	O(1 + n/k)	O(n)

das kann aber nicht stimmen, oder ist deine hashfunktion optimal?

[knivil]

in was fuer quellen wuerdet ihr nachkucken wenn ihr sowas rausfinden muesstet?

Gar nicht! Ich wuerde einfach die Multimap nehmen.

[sollteichwissen]

hm, eigentlich soll die multimap schon geordnet sein. d.h. eine hash table kommt schonmal nicht in frage?

insert und erase waeren aber beide im durchschnitt konstant... hmm. http://en.cppreference.com/w/cpp/container/unordered_multimap/insert http://en.cppreference.com/w/cpp/container/unordered_multimap/erase

@ruediger: es geht mir darum womit ich eine (nach keys geordnete) multimap implementieren sollte, nicht darum welchen container ich benutzen soll.