Структура данных C ++ STL Постоянное время Push / Pop / Произвольный доступ по индексу с надежными указателями на элементы

Question

Я просматривал C ++ STL и не уверен, какая структура данных является наиболее подходящей для этого конкретного варианта использования. Он должен уметь выполнять следующие три вещи в постоянное время:

1. Произвольный доступ с постоянным временем по индексу (поэтому случайный элемент может быть выбран за постоянное время)
2. Постоянное время push / pop только в конце
3. Указатели на содержащиеся элементы не могут быть недействительными при нажатии / выталкивании (не заботятся об итераторах)

Первоначально я пытался использовать вектор; он полностью удовлетворяет первым двум критериям. Тем не менее, я усвоил трудный путь, что когда вы помещаете новые элементы в вектор, указатели на его элементы становятся недействительными, поскольку вектор перемещает себя, сохраняя всю свою память непрерывной. Хотя проблема может быть решена с помощью заблаговременного использования метода reserve() вектора, проблема заключается в том, что для этого требуется знать наибольшее количество элементов, которые могут понадобиться для хранения внутри него, и это не то значение, которое я знаю заранее времени, и при этом я не могу действительно рассчитать это. Я также не могу просто использовать резерв снова, когда размер становится большим, потому что тогда указатели на элементы вектора все равно станут недействительными.

Итак, я попробовал deque. Хотите верьте, хотите нет, deque фактически полностью удовлетворяет всем трем критериям. Указатели на элементы НЕ аннулируются нажатием / выталкиванием, которые имеют постоянное время. Тем не менее, я заметил, что была стоимость; Deque был примерно в два раза медленнее, чем вектор. Я знаю, что у deque есть дополнительная возможность помещать предметы впереди, что не нужно для моих целей, , и я не уверен, является ли это именно этой дополнительной возможностью ИЛИ фактом, что не вся память сохраняется непрерывно, что ответственно за замедление.

Итак, хотя deque удовлетворяет этим трем критериям, существует ли структура данных в C ++ STL, которая может работать лучше? Или, возможно, обходной путь с вектором для предотвращения аннулирования указателей? Что ты думаешь?

Answer 1

В основном вам нужен std::deque, однако std::deque основан на std::vector, который делает недействительными все итераторы, если достигнута емкость и должен быть выделен новый непрерывный блок памяти ( Reference ). Так как вас не волнует недействительность итератора, это не должно вас беспокоить, а структура std::deque достаточна для вашего варианта использования. Посмотрите на ссылку . Однако, если вы хотите иметь только push/pop интерфейс, подумайте о написании оболочки.