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