Давайте пройдемся по этим ...
- среднее время поиска элементов в худшем случае из сложности O (log (n))
- удаление / вставка элементов делаетне делает недействительными ранее полученные итераторы
- обеспечивает вставку и удаление элементов в худшем случае O (log (n)) сложности
Это в значительной степени кричит "дерево".
- предоставляет итератор с произвольным доступом (вместе с итераторным сравнением <,>)
- с учетом итератора, в худшем случае я могу узнать порядковую позицию элемента, на который указывает контейнер,сложности O (log (n))
- элементы повторяются в том же порядке, в котором они были добавлены в контейнер
Я предполагаю, что индекс выВы предоставляете свой итератор с произвольным доступом в порядке вставки, поэтому [0] будет самым старым элементом в контейнере, [1] будет следующим самым старым и т. д. Это означает, что при удалении итераторы должны бытьдопустимо, итератор внутренне не может хранить индбывший, так как он может измениться без предварительного уведомления.Так что просто использование map с ключом, являющимся порядком вставки, не сработает.
Учитывая, что каждый узел вашего дерева должен отслеживать, сколько элементов в каждом поддереве, кроме того,своим обычным членам.Это позволит произвольный доступ со временем O(log(N)).Я не знаю о готовом наборе кода, но подклассы std::rb_tree и std::rb_node были бы моей отправной точкой.