Ищу специальную структуру данных C ++

Я ищу реализацию C ++ структуры данных (или комбинации структур данных), которая удовлетворяет следующим критериям:

• элементы доступны так же, как в std :: vector
• предоставляет итератор произвольного доступа (вместе со сравнением итераторов )
• среднее время доступа к элементу (: поиск) в худшем случае составляет O (log (n)) Элементы сложности
• повторяются в том же порядке, в котором они были добавлены в контейнер
• с учетом итератора, я могу узнать порядковое положение элемента, на который указывает в контейнере, в худшем случае O ( log (n)) сложность
• обеспечивает вставку и удаление элемента в определенной позиции в худшем случае O (log (n)) сложность
• удаление / вставка items не отменяет ранее полученные итераторы

Заранее благодарим вас за любые предложения

Dalibor

(Edit) Ответы:

Выбранный мной ответ описывает структуру данных, которая соответствует всем Эти требования. Однако boost :: multi_index, предложенный Максимом Егорушкиным, предоставляет функции, очень близкие к перечисленным выше.

(Edit) Некоторые требования были указаны неправильно. Они изменены в соответствии с исправлением (: original)

(Edit) Я нашел реализацию структуры данных, описанной в принятом ответе. Пока все работает как положено. Это называется дерево счетчиков

(Edit). Рассмотрите возможность использования AVL-массива, предложенного sp2danny