Когда требуется перераспределение std :: deque?

Question

Насколько я знаю, std::deque хранит свои элементы в кусках кусков (хотя и зависит от реализации, но это то, что я читаю в большинстве источников), а не std::vector, который в большинстве случаев использует один блок памяти ,

Итак, это довольно разумно для std::vector, чтобы встретить перераспределение как часть вставки. Тем не менее, я не могу связать ситуацию, когда потребуется перераспределение для std::deque, поскольку она только начинается с нового фрагмента памяти, когда ток взорван.

Может ли кто-нибудь предоставить мне случай, когда std::deque нуждается в перераспределении вследствие каких-либо операций, выполненных на нем?

Answer 1

Единственное, что приходит мне на ум, это то, что происходит, когда вы делаете вставку на deque и страницу, в которую нужно перейти, заполняется? cplusplus.com состояния на функцию вставки около

двусторонних очередей

If the insertion happens at the beginning or the end of the sequence, all iterators 
related to this container are invalidated, but pointers and references remain valid, 
referring to the same elements they were referring to before the call. If the 
insertion happens anywhere else in the deque, all iterators, pointers and references 
related to this container are invalidated. 

Та часть, которая действительно бросается в глаза, что все аннулируется является вставка в середине, который мне звучит как что-то происходит с базовой структурой данных , Я не уверен, что это перераспределение, но это, по крайней мере, сменная копия-вставка.

Answer 2

Может ли кто-нибудь предоставить мне случай, когда std :: deque требует перераспределения, как , является следствием некоторых операций, выполняемых над ним.

В типичном случае никогда. Хотя точные сведения о реализации deque не указаны, чтобы сохранить итератор/указатель/ссылку на недействительность *, а алгоритмические требования найдут вредное практическое применение для любого сценария, который требует перераспределения существующего блока памяти на больший или меньший размер.

[Особо следует обратить внимание на недействительность указателя/ссылки, поскольку это говорит нам больше о том, что должно продолжаться в памяти. Итераторы могут делать некоторые исключения, которые отделяют их действительность от представления памяти deque].

Попробуйте положить себя в обувь разработчика. Как вы реализуете такие функции, как push_front, push_back и расширяете resize таким образом, чтобы не лишить никаких существующих указателей на deque, если вам когда-либо захотелось перераспределить блоки памяти?

А также сохранить аналогичные требования для pop_front и pop_back и сокращение resize (недействительность только указателей на элементы, которые были удалены), если вы когда-либо соблазну перераспределить существующий блок памяти для меньшего размера?

Участок, где вы можете найти самую удаленную возможность перераспределения, вставляется в середину deque. Это единственное место, где все указатели на deque могут быть признаны недействительными, и там может быть возможно перераспределить содержимое deque's (возможно, необязательно практично). Только в этом конкретном случае, как разработчики deque, мы можем аннулировать указатели на элементы, которые все еще существуют, где у нас даже есть свобода перераспределения любых существующих блоков памяти.Но маловероятно, что это произойдет, поскольку эффективная реализация insert, как правило, просто хочет перетасовать и перемещать элементы, а не перераспределять блоки памяти, в которых они находятся.

Все эти требования объединяются, чтобы ограничить реализацию тем типом, который описывает Саттер, даже если он вроде небрежно там и затушевывает теоретическую часть. Это похоже на то, как код C++ 03 часто считал само собой разумеющимся, что std::vector всегда был смежным, хотя он был неуказан, так как требования алгоритма и итератора для std::vector сделали смежное представление в значительной степени единственным практическим выбором.

Так что теоретически возможно, что кто-то может каким-то образом прокрасть перераспределение где-то, соблюдая эти требования. Но на практике это почти невозможно, и, безусловно, непрактично, так что вам будет трудно найти такую ​​реализацию deque.