Путаница с аннулированием итераторов в deque - PullRequest
Новая
       41

Путаница с аннулированием итераторов в deque

14 голосов
/ 27 мая 2009

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

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

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

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

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

ИМХО, deque - это набор блоков, в которых первый блок растет в одном направлении, а последний - в противоположном. 

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

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

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

Ответы [ 3 ]

13 голосов
/ 27 мая 2009

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

шаблон void insert (позиция итератора, Сначала InputIterator, затем InputIterator);

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

Так что оба верны. Как указывает Джосуттис, вставка спереди или сзади не делает недействительными ссылки на элементы deque, а только итераторы самой deque .

РЕДАКТИРОВАТЬ: более современный черновик говорит по существу то же самое (раздел 23.2.2.3)

12 голосов
/ 05 января 2013

ИМХО, deque - это набор блоков с первым блоком, растущим в одном направлении, и последним блоком в противоположном направлении.

Ваше мнение является вашей прерогативой, но оно неверно. :)

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

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

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

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

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

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

C ++ 03

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

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

  • Изменение размера : согласно вставке / удалению [23.2.1.2/1]

C ++ 11

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

  • Стирание : стирание последнего элемента делает недействительными только итераторы и ссылки на стертые элементы и итератор «за конец»; удаление первого элемента делает недействительными только итераторы и ссылки на стертые элементы; Стирание любых других элементов делает недействительными все итераторы и ссылки (включая итератор конца-в-конце) [23.3.3.4/4]

  • Изменение размера : согласно вставке / стиранию [23.3.3.4/1]

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

Я не уверен, какую дополнительную ссылку на достоверные источники вы ищете & mdash; соответствующий стандартный отрывок уже процитирован и процитирован.

0 голосов
/ 27 мая 2009

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

РЕДАКТИРОВАТЬ:

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

...