Deque стереть с середины, указатель потерян?

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

Я пытался прочитать реализацию deque, но это сложно, я не понимаю, действует ли она как список или вектор.

Я использую реализацию deque на VisualC ++ std.


c++ pointers deque
person mikbal    schedule 30.12.2011    source источник

Ответы (2)


arrow_upward
3
arrow_downward

да. Вставка в середине делает недействительными все итераторы и ссылки на элементы (и, следовательно, указатели на элементы). Вставка на любом конце делает недействительными все итераторы, но не ссылки или указатели. И вы не читаете реализацию, чтобы узнать о таких вещах; читаешь документацию. (Реализация может фактически разрешать операции, которые официально не поддерживаются. До следующего исправления ошибки.)

person James Kanze    schedule 30.12.2011
comment
тогда я перейду на std :: list. Есть ли в списке проблемы со стиранием с середины? Я просто хочу быть уверенным, потребуется время, чтобы переключиться. У меня много вызовов [] и .at (). - person mikbal; 30.12.2011
comment
@mikbal: список безопаснее и защищает вас от недействительности итератора, но выбор контейнера стандартной библиотеки действительно зависит от типа данных, которые вы хотите сохранить, и операций, которые вы хотите выполнить с данными. - person Alok Save; 30.12.2011
comment
я повторяю все элементы. Это o (n) для всех, но мне вроде как не нравится list, потому что он как-то очень медленный по сравнению с deque и vector на практике. хотя, похоже, перечислите мою судьбу. - person mikbal; 30.12.2011
comment
@mikbal std::list - единственный стандартный контейнер, который гарантирует итераторы, ссылки и указатели, несмотря ни на что (если вы не удалите элемент под итератором). С другой стороны, это O (n) для произвольного доступа (а не O (1)), и он намного медленнее, чем другие контейнеры, потому что каждый элемент выделяется отдельно - много распределения и освобождения, и очень бедная местность. - person James Kanze; 30.12.2011

arrow_upward
2
arrow_downward

стирает ли средний элемент из двухсторонней очереди недействительными все указатели на двухстороннюю очередь, как это происходит с векторами?

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

Для вектора все итераторы и ссылки до точки вставки не затрагиваются, если только новый размер контейнера не превышает предыдущий размер.

person Alok Save    schedule 30.12.2011