необходимо придумать структуру данных типа std::set(history)+std::set+std::stack т.е. со свойствами
1) инициализировать объект (= в нем ничего нет и ничего не было до этого)
2) добавлять элемент в случае, если в объекте такового нет и не было до (т.е. добавляется предварительный поиск)
3) помечать элемент как удаленный
4) возможность завершить работу с объектом, если все его элементы помченны на удаление.
Шаг 1 выполняется n раз,
Шаги 2-4: n*m, n>>1, m>>1
Какая оптимальная структура данных подойдет для задачи?
Здравствуйте, icegood, Вы писали:
I>Какая оптимальная структура данных подойдет для задачи?
Так обычный std::set и подойдёт. insert добавляет элемент, erase удаляет, empty проверяет — осталось ли что-то ещё.
Гоняться за оптимизацией надо тогда, когда профайлер ткнёт носом в узкое место. И то, с некоторой вероятностью, достаточно будет заменить на hash_set или прикрутить собственный аллокатор.
Но, поскольку упомянут стек, то подозреваю иное.
Нужна логика наподобие MRU/LRU списка: при добавлении ранее существующего элемента выдёргивать его в головную позицию. Ну или что-то такое.
Чтобы давать точные советы, — напиши, как желаемое поведение выглядит. Не в терминах "помечать элемент как удалённый", а в терминах наблюдаемого поведения.
А пока что, см. boost::multi_index : там как раз одно из приложений — это LRU-список.
Естественно, что тамошняя реализация не самая быстрая и не самая компактная.
Когда мне надо было сделать очень быстрый кэш на десяток миллионов элементов, я сперва профилировал реальную задачу, узнал гистограммы количества коллизий для различных хэш-функций, и в итоге сделал всё на двух векторах. А начинал с мультииндекса, чисто для proof of concept, чтобы было что профилировать.
Перекуём баги на фичи!
