Laufzeit insert in multimap
-
Wie ist eigentlich die Laufzeit bei einem insert in eine Multimap, wenn es den Key schon M mal gibt?
-
http://www.cplusplus.com/reference/map/multimap/insert/ schrieb:
If a single element is inserted, logarithmic in size in general, but amortized constant if a hint is given and the position given is the optimal.
Demnach logarithmisch. Wieviele Elemente mit dem gleichen Key schon existieren ist dabei uerheblich. Der Map liegt ein Binärbaum zu Grunde und bei gleichem Key wird einfach ein zweiter Knoten eingefügt.
-
Es ist nicht unerheblich wieviele Elemente mit dem gleichen Key existieren, denn auch die gehen in diesen Logarithmus ein. k * log(Elemente mit anderem Key + Elemente mit gleichen Key).