вектор реализован с множеством блоков и без изменения размера копии

Question

Мне интересно, можно ли было бы реализовать stl-подобный вектор, где хранение осуществляется в блоках, и вместо того, чтобы выделять больший блок и копировать из исходного блока, вы могли бы хранить разные блоки в разных местах,и перегружаем оператор [] и оператор итератора ++, чтобы пользователь вектора не знал, что блоки не являются смежными.

Это может сохранить копию при выходе за пределы существующей емкости.

Answer 1

Вы бы искали std :: deque

См. ПОЛУЧИЛ # 54 Используя Vector и Deque

В большинстве случаев предпочитают использовать Deque (спорную)

Содержит тесты, демонстрирующие поведение

Последний стандарт C ++ 11 гласит:

§ 23.2.3 Контейнеры последовательности

[2] Контейнеры последовательности предлагают программисту различные компромиссы сложности и должны использоваться соответственно. вектор или массив - это тип контейнера последовательности, который должен использоваться по умолчанию. список или forward_list следует использовать при частых вставках и удалениях из середины последовательности. deque is выбор структуры данных, когда большинство вставок и удалений происходит в начале или в конце последовательность.

FAQ> Уголок прелюдии> Вектор или Deque? (средний) Говорит:

• Вектор может только эффективно добавлять элементы в конец, любая попытка вставить элемент в середине вектора или в начале может быть и часто очень неэффективна. Deque может вставлять элементы как в начале, так и в конце в постоянное время , O (1), что очень хорошо. Вставки в середине все еще неэффективны, , но если такая функциональность необходима, следует использовать список . Метод deque для вставки спереди - push_front (), метод insert () также можно использовать, но push_front более понятен.

• Так же, как и вставки, стирания в начале вектора неэффективны, , но deque также предлагает стирание в постоянном времени с фронта .

• Deque использует память более эффективно. Рассмотрим фрагментацию памяти: вектору требуется N последовательных блоков памяти для хранения своих элементов, где N - количество элементов, а блок - размер одного элемента. Это может быть проблемой, если для вектора требуется 5 или 10 мегабайт памяти, но доступная память фрагментирована до такой степени, что нет 5 или 10 мегабайт последовательной памяти. У deque нет этой проблемы, если не хватает последовательной памяти, deque будет использовать серию меньших блоков.

[...]

Answer 2

Да, это возможно.

ты знаешь веревку? это то, что вы описываете для строк (большая строка == веревка, получил шутку?). Веревка не является частью стандарта, но для практических целей: она доступна на современных компиляторах. Вы можете использовать его для представления всего содержимого текстового редактора.

Взгляните сюда: Веревка STL - когда и где использовать

И всегда помните:

• первое правило (производительности) оптимизации: не делайте этого
• второе правило (только для экспертов): не делайте этого сейчас.