Добрый день!

Посоветуйте контейнер (комбинацию контейнеров) для хранения элементов (числом до нескольких десятков тысяч) со следующими требованиями
(в порядке убывания):
— быстрый обход,
— быстрое удаление 10к элементов,
— быстрое добавление элемента,
— быстрая сортировка по своему правилу,
— ограничения по памяти нет (в разумных пределах).
— произвольный доступ не нужен.

Элементы, для простоты, — указатели.
Сортировка у меня сейчас отложенная, после добавления элементов. Элементы могут добавиться как 10, так и 10к.

Собсно, я использую сейчас deque.
Но нагрузка возросла с нескольких сотен элементов до пары десятков тысяч и сильно просело удаление. 10к элементов сейчас удаляются (последовательно) 3.5сек. Это огорчает.

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

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

А можно держать все элементы с одинаковым ключов в отдельном контейнере? Тогда их удаление — просто удаление одного элемента из главного контейнера.

Здравствуйте, RikkiTikkiTavi, Вы писали:

RTT>Но нагрузка возросла с нескольких сотен элементов до пары десятков тысяч и сильно просело удаление. 10к элементов сейчас удаляются (последовательно) 3.5сек. Это огорчает.

удалять 10к за 3 секунды это какая-то жесть жестокая. Тут даже std::vector должен работать на порядок(порядки) быстрее. Объекты тяжелые? Компаратор тяжёлый? Элементы хранятся по значению или по указателю? Если по значению — посмотрите, насколько эффективно работает move-конструктор, и собственно, деструктор.

Здравствуйте, antropolog, Вы писали:

A>Здравствуйте, RikkiTikkiTavi, Вы писали:

RTT>>Но нагрузка возросла с нескольких сотен элементов до пары десятков тысяч и сильно просело удаление. 10к элементов сейчас удаляются (последовательно) 3.5сек. Это огорчает.

A>удалять 10к за 3 секунды это какая-то жесть жестокая. Тут даже std::vector должен работать на порядок(порядки) быстрее.

Ну даже с вектором можно очень плохую реализацию написать, если, например, не использовать для группового удаления set_difference или remove_if, а вместо этого вызывать v.erase(find(v.begin(), v.end(), value)) в цикле, ну или делать нечто похожее с квадратичным временем работы.

Здравствуйте, RikkiTikkiTavi, Вы писали:

RTT>Собсно, я использую сейчас deque.
RTT>Но нагрузка возросла с нескольких сотен элементов до пары десятков тысяч и сильно просело удаление. 10к элементов сейчас удаляются (последовательно) 3.5сек. Это огорчает.

А пакетное удаление нельзя сделать?

// дано:
vector<T> the_collection; // вся коллекция (вектор, дек) 
vector<T> to_be_removed; // расстрельный список (вектор, сет)

// отсортировали для быстрой работы с расстрельным списком (если это вектор)
sort(begin(to_be_removed), end(to_be_removed));

// прошерстили-поудаляли за один проход
the_collection.erase(
  remove_if(
    begin(the_collection),
    end(the_collection),
    [&to_be_removed] (T t) {
      return binary_search(begin(to_be_removed), end(to_be_removed), t);
      // для множества так даже проще
      return to_be_removed.count(t);
    }
  ),
  end(the_collection)
);

И вообще!
boost::multi_index: один срез — естественный порядок добавления, второй срез — отсортированный по значению (кстати, нахаляву получаем проверку уникальности, если надо).
Да, структура данных более громоздкая, но уж не 3.5 секунды на деструкцию же!
(Я, конечно, видел, как 100 млн интов убивалось за 3 минуты, из-за адской фрагментации кучи и персонального вызова деструкторов... но тут на 4 порядка меньше элементов, должно прокатить безболезненно).