stl wybór kontenera

Witam, potrzebuję kontenera który:

• (1) będzie trzymał elementy posortowane
• (2) czas dodawania elementów max: log(n)
• (3) możliwe duplikaty elementów
• (4) czas wyszukiwania elementu o zadanej pozycji: max: log(n)
• (5) możliwość określenia globalnej pozycji iteratora (chodzi o określenie ile elementów większych/mniejszych) znajduje się na prawo/lewo od iteratora w czasie max log(n)
  // maksymalna ilość elementów w kontenerze jest znana

(1),(2),(3),(4) spełnia według mnie tylko multiset, ale za to nie spełnia on (5) bo std::distance dla niego działa w czasie stałym. Chyba że da się jakoś dodawać elementy do vectora tak żeby od razu były posrtowane.

I teraz moje pytanie:
Czy da się określić pozycję iteratora do multisetu w czasie max log(n) lub czy istnieje jakaś funkcja która dodaje elementy do vectora w taki sposób, aby nadal były posorotwane lub inne rozwiązanie do mojego problemu?

EDIT:
z ogólniejszym problemem sobie poradziłem w inny sposób, jednak pytanie nadal jest aktualne (ciekawość)

krwq napisał(a)

• (5) możliwość określenia globalnej pozycji iteratora (chodzi o określenie ile elementów większych/mniejszych) znajduje się na prawo/lewo od iteratora w czasie max log(n)

(....) za to nie spełnia on (5) bo std::distance dla niego działa w czasie stałym. Chyba że da się jakoś dodawać elementy do vectora tak żeby od razu były posrtowane.

przeciez? stały < logarytmiczny..
a wstawiac elementy do wektora w multisecie dosc prosto.. skoro trafiaja do wektora, to znaczy ze maja ten sam klucz, czyli sa sobie wszystkie 'rowne' pod wzgledem porzadku, wiec dostawiaj zawsze na koniec i niech pozycja elementu bedzie okreslona jako "kluczwmapie, indekswwektorze"

chyba, ze amsz zachowac podwojny porzadek? tzn. osobny porzadek w secie o soobny (inny) wewnatrz wektorow?

liniowy miałem na myśli, nie wiem czemu stały napisałem

domyślam się, że nie masz tam vector'a, ale chciałem Ci zasugerować sposob wykorzystania go. w tej chwili nie pamietam juz co myslalem o multisecie, ale z set'em wydaje mi sie ze jestes w stanie to osiagnac poprzez:
set<Key, Compare, Alloc>
Key = struct Group { int wartosc; vector<XYZ> faktyczneelementy; } // napialem 'int' ale moze to byc double lub cokolwiek
Compare = func(Group& left, Group& right) { return left.wartosc < right.wartosc; }
Alloc = default
celem 'wstawienia', przygotowujesz nowy Group z wartosc=wieszile i pustym vectorem, wstawiasz go poprzez "pair<iterator, bool> set::insert(const value_type& x)". jesli wstawienie sie uda - super, koniec. jesli wstawienie sie nie uda, to IIRC i tak dostajesz iterator z pozycja istniejacego elementu, wiesz mozesz się dobrac do "starego" wektora juz pamietanego w secie i do niego dostawic element, na przyklad na koniec, bo ich wartosci i tak sa rowne.
przy takiej konstrukcji, określnik pozycji to struct MyKey { int outer; size_t inner; }, a bi-dir iterator do Twojego "agregatu" bedzie mial postac w stylu struct MyIter { set<Group>::iterator outer; set<Group>::iterator rev_outer; vector<XYZ>::iterator inner; }, wydaje mi sie ze taki MyIter bedzie spelnial (5), w ramach grupy w vector jest to oczywiste, a poza grupa korzystajac z outer/rev_outer powinno byc chodliwe w log(n) per sąsiad. nie sprawdzalem, wydaje mi sie..