Посоветуйте контейнер (комбинацию контейнеров) для хранения элементов (числом до нескольких десятков тысяч) со следующими требованиями
(в порядке убывания):
— быстрый обход,
— быстрое удаление 10к элементов,
— быстрое добавление элемента,
— быстрая сортировка по своему правилу,
— ограничения по памяти нет (в разумных пределах).
— произвольный доступ не нужен.
Элементы, для простоты, — указатели.
Сортировка у меня сейчас отложенная, после добавления элементов. Элементы могут добавиться как 10, так и 10к.
Собсно, я использую сейчас deque.
Но нагрузка возросла с нескольких сотен элементов до пары десятков тысяч и сильно просело удаление. 10к элементов сейчас удаляются (последовательно) 3.5сек. Это огорчает.
Мысли такие:
— Поскольку важна последовательность обхода, то контейнер должен поддерживать произвольное расположение элементов. Для быстрого удаления (по ключу — указателю) элементы надо упорядочить по этому ключу. Т.о. возникает мысль о комбинации контейнеров.
— Поскольку в целом все устраивает кроме затыка с удалением большого кол-ва элементов, возможно, стоит рассмотреть вариант удаления их всех сразу, а не последовательно. Но тут сходу чето не придумывается...
