Мне нужна структура данных, в которую я вставляю элементы, и сразу после вставки она остается отсортированной, и я узнаю индекс элемента, который я только что вставил, в журнал N раз.
У меня есть попытался использовать вектор и мультимножество, но ни один из них не удовлетворял обоим требованиям.
Вектор:
Если я хочу найти индекс элемента, я могу сделать:
using namespace std;
vector<int>::iterator it = lower_bound(myvec.begin(), myvec.end(), someElement);
int index = (it - myvec.begin());
Однако, вектор не учитывает время вставки O (log N), оставаясь отсортированным. Сортировка вектора после каждой вставки будет O (N log N) каждый раз. Я попытался:
vector<int>::iterator it = lower_bound(myvec.begin(), myvec.end(), someElement);
myvec.insert(it, someElement);
Это находит правильное место для вставки элемента, но myve c .insert запускается по времени O (N), а не O (log N).
Мультимножество:
Мультимножество позволяет мне вставлять и сохранять сортировку, но там, где этого не хватает, это получение индекса элемента после вставки.
multiset<int>::iterator it = lower_bound(myset.begin(), myset.end(), someElement);
После использования lower_bound я не могу просто сделать
int index = (it - myset.begin());
как с вектором. Вместо этого я рассмотрел следующий метод:
int index = distance(myset.begin(), it);
Однако расстояние проходит за время O (N) вместо времени O (log N).
Существует ли структура данных или метод, который позволяет мне удовлетворить оба требования в журнале N раз?