Резервируют ли реализации динамических массивов место в начале для подготовки?
Основные реализации динамические массивы имеют размер 2n, где половина пространства заполнена существующими элементами, а другая половина зарезервирована в конце для добавления новых элементов в O (1) времени.
Для вставки новых элементов в любое место, кроме конца массива, требуется перераспределение массива, что является дорогостоящей операцией.
Существуют ли в C ++ реализации изменяемых массивов, где пространство также зарезервировано в начале массива для эффективного добавления элементов? Если да, то сколько места зарезервировано по сравнению с местом, зарезервированным в конце для добавления? Я полагаю, что предоплата является гораздо менее распространенной операцией, но если она происходит в программе достаточно часто, это может иметь разрушительные последствия для перераспределения при каждой операции предоплаты.
Решение
двусторонние очереди учитывают добавление и добавление в амортизированном постоянном времени.
В отличие от векторы, где массив хранится непрерывно и перераспределяется при достижении емкости, не гарантируется, что элементы deque будут храниться непрерывно. Вместо этого deques хранит элементы в чанках. Если в результате отталкивать() или же push_front () вызов, новый кусок пространства выделен и связан с.
Спасибо тебе Марк Рэнсом для публикации о запросах в комментариях.
Другие решения
Я не слышал о такой реализации. Однако, если вам не требуется упорядочивать элементы в памяти, как они находятся в контейнере, вы можете использовать std :: list и иметь O (1) при вставке в любом месте.