Путаница в недействительности итераторов в deque

Я немного смущен относительно недействительности итератора в deque. (В контексте этого вопроса)

Ниже приведены выдержки из: - стандартной библиотеки С++: учебника и справочника, Николай М. Йосуттис

Любая вставка или удаление элементов кроме в начале или в конце аннулирует все указатели, ссылки, итераторы, которые ссылаются на элементы от deque.

Ниже приведены выдержки из SGI сайт:

Семантика аннулирования итератора для deque выглядит следующим образом. Вставить (включая push_front и push_back) аннулирует все итераторы, которые ссылаются к деку. Стереть в середине deque аннулирует все итераторы, которые обратитесь к деку. Стереть на начало или конец дека (в том числе pop_front и pop_back) аннулирует итератором, только если он указывает на стираемый элемент.

IMHO, deque - это совокупность блоков с первым блоком, растущим в одном направлении, а последний блок в противоположном направлении.

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_front не должно влиять на итераторы deque (я согласен с Josuttis).

Какое правильное объяснение? что стандарт говорит об этом?

Ответ 1

Из стандартного рабочего проекта

template < class InputIterator > void insert (позиция итератора, InputIterator сначала, InputIterator последний);

1 Эффекты: вставка в середине deque аннулирует все итераторы и ссылки на элементы от deque. Вставка с обоих концов deque аннулирует все итераторы к deque, но не имеют влияние на достоверность ссылок к элементам deque. "

Итак, оба правильны. Как указывает Йосутис, вставка спереди или назад не приводит к недействительности ссылок на элементы дека, только итераторы к самому деку.

EDIT: более современный проект говорит по существу то же самое (раздел 23.2.2.3)

Ответ 2

IMHO, deque - это совокупность блоков с первым блоком, растущим в одном направлении, а последний блок в противоположном направлении.

Ваше мнение - ваша прерогатива, но это неправильно.:)

deque является таким контейнером семантически, но с точки зрения реализации он предназначен для реализации одним или несколькими блоками памяти. правила аннулирования итератора С++ взяты из реализации, поэтому вот почему. Возможно, это небольшая утечка абстракции, но, ну, что угодно.

Документация SGI STL не является надлежащей документацией для чтения, поскольку SGI STL не является стандартной библиотекой С++. К сожалению, Josuttis - один из тех людей, который называет его "STL", и это привело к вашей путанице.

Ниже приведены выдержки из - Стандартная библиотека С++: Учебное пособие и справочник, Николай М. Йосуттис

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

Проще говоря, этот отрывок из Josuttis вводит в заблуждение, подразумевая, что вставка или удаление элементов, которые находятся в начале или в конце, не делают недействительными указатели, ссылки или итераторы & hellip; хотя стоит отметить, что он никогда не выходит и утверждает это прямо.

Вот реальные, правильные, официальные правила для std::deque:

С++ 03

Вставка: все итераторы и ссылки недействительны, если вставленный элемент не находится на конце (спереди или сзади) deque (в этом случае все итераторы недействительны, но ссылки на элементы не затронуты) [23.2.1.3/1]
Erasure: все итераторы и ссылки являются недействительными, если только стертые члены не находятся на конце (спереди или сзади) deque (в этом случае только итераторы и ссылки на стертые элементы недействительны) [23.2.1.3/4]
Изменение размера: по вставке/стиранию [23.2.1.2/1]

С++ 11

Вставка: все итераторы и ссылки недействительны, если вставленный элемент не находится на конце (спереди или сзади) deque (в этом случае все итераторы недействительны, но ссылки на элементы не затронуты) [23.3.3.4/1]
Erasure: стирание последнего элемента делает недействительными только итераторы и ссылки на стираемые элементы и итератор прошедшего конца; стирание первого элемента аннулирует только итераторы и ссылки на стертые элементы; стирание любых других элементов делает недействительными все итераторы и ссылки (включая итератор прошедшего конца) [23.3.3.4/4]
Изменение размера: согласно вставке/стиранию [23.3.3.4/1]

Дальнейшее чтение

_{Я не уверен, что дальнейшая ссылка на надежные источники, которые вы ищете — соответствующий стандартный отрывок уже цитируется и цитируется.}

Ответ 3

SGI-реализация, вероятно, использует растущий массив, поэтому, если вставка заставляет массив расти, итераторы, указывающие на старый массив, являются недопустимыми.

ИЗМЕНИТЬ:

В разделе 17.2.3 языка программирования С++ 3rd Edition я ничего не вижу в описании deque, который указывает, какие операции сохраняют или отменят итераторы. Возможно, я смотрю не в то место, иначе поведение может быть undefined.