Неупорядоченный контейнер на основе пула памяти фиксированного размера с частой вставкой и удалением
Я ищу контейнер для хранения динамически растущего и уменьшающегося семейства объектов, размер которых, как я знаю, приближается, но никогда не превышает заданную границу. Контейнер не нужно заказывать, так что я рад любой вставке, где бы она ни происходила. Более того, я хочу, чтобы все объекты были сохранены в некотором фиксированном непрерывном пуле памяти, но мне не требуется, чтобы память, которая фактически занята в какой-то момент времени, была подключенным интервалом в пуле памяти.
Есть ли какой-либо контейнер / распределитель в STL или бусте, который обеспечивает вышеупомянутое?
Кажется, что разумным подходом было бы использовать связанный список с памятью, взятой из пула памяти фиксированного размера, но я бы предпочел использовать для этого уже существующую и устоявшуюся реализацию, чем пытаться делать это самому.
Спасибо!
Решение
Поскольку вам нужны элементы, чтобы быть смежными, я думаю, вы должны пойти на std::vectorзвонит reserve в начале.
Как я сказал в комментарии, как только вам понадобится непрерывная память, вам придется что-то перемещать, когда вы удаляете в середине, и это поведение уже обрабатывается std::vectorс помощью удалить / стереть идиому.
Помимо этого, если вы используете только векторную вставку или поиск будет дорогостоящим в соответствии с вашим дизайном:
- Либо вы всегда добавляете новый элемент в конце, и поиск элемента будет стоить вам, но вставка будет безболезненной
- Или вы сортируете вектор после каждой вставки (это будет стоить), и ваш поиск будет намного быстрее, используя
std::equal_range
В противном случае, если вы можете позволить себе дополнительный std::unordered_set<std::vector<your_element>::iterator> с пользовательским хеш / равенство у вас есть хорошее соотношение вставки / поиска, посмотрев с std::unordered_set<> чтобы найти, где хранится ваш элемент.
Другие решения
Подводя итоги, ваши требования:
- динамически растущий и уменьшающийся
- нет необходимости заказывать
- фиксированный непрерывный пул памяти
С третьим требованием вы исключаете большинство контейнеров на основе узлов (таких как списки или очереди). То, что у вас осталось, это массивные контейнеры. конкретно std::array а также std::vector (или даже std::valarray/boost::valarray).
Но с первым требованием вы исключаете std::array (если вы не хотите реализовать какой-то странный вид std::array<std::optional<T>> что имитирует функциональность std::vector).
То, что вы остались с std::vector, что также соответствует требованию номер два. Конечно, вы можете управлять вместимость с std::vector::reserve а также std::vector::shrink_to_fit.