Правила аннулирования итераторов

C ++ 03 (Источник: Правила признания итераторов (C ++ 03))

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

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

Ассоциативные контейнеры

• [multi]{set,map}: все итераторы и ссылки не затронуты [23.1.2 / 8]

Контейнерные адаптеры

• stack: наследуется от нижележащего контейнера
• queue: наследуется от нижележащего контейнера
• priority_queue: наследуется от нижележащего контейнера

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

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

Ассоциативные контейнеры

• [multi]{set,map}: только итераторы и ссылки на стертые элементы становятся недействительными [23.1.2 / 8]

Контейнерные адаптеры

• stack: наследуется от нижележащего контейнера
• queue: наследуется от нижележащего контейнера
• priority_queue: наследуется от нижележащего контейнера

• vector: согласно вставке / стиранию [23.2.4.2/6]
• deque: согласно вставке / стиранию [23.2.1.2/1]
• list: согласно вставке / стиранию [23.2.2.2/1]

Примечание 1

Если не указано иное (или
явно или путем определения функции
с точки зрения других функций), вызывая
функция-член контейнера или передача
контейнер в качестве аргумента
функция библиотеки не должна делать недействительной
итераторы или изменить значения,
объекты в этом контейнере.
[23.1 / 11]

Заметка 2

В C ++ 2003 не ясно, подчиняются ли «конечные» итераторы вышеуказанным правилам; в любом случае вы должны предположить, что они есть (как это имеет место на практике).

Заметка 3

Правила аннулирования указателей такие же, как и правила аннулирования ссылок.

C ++ 11 (Источник: Правила признания итераторов (C ++ 0x))

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

• vector: все итераторы и ссылки до точки вставки не затрагиваются, если только новый размер контейнера не превышает предыдущую емкость (в этом случае все итераторы и ссылки становятся недействительными) [23.3.6.5/1]
• deque: все итераторы и ссылки становятся недействительными, если только вставленный элемент не находится в конце (передний или задний) deque (в этом случае все итераторы становятся недействительными, но ссылки на элементы не затрагиваются) [23.3.3.4/1]
• list: все итераторы и ссылки не затронуты [23.3.5.4/1]
• forward_list: все итераторы и ссылки не затронуты (относится к insert_after) [23.3.4.5/1]
• array: (П / а)

Ассоциативные контейнеры

• [multi]{set,map}: все итераторы и ссылки не затронуты [23.2.4 / 9]

Несортированные ассоциативные контейнеры

• unordered_[multi]{set,map}: все итераторы становятся недействительными, когда происходит перефразировка, но ссылки не затрагиваются [23.2.5 / 8]. Перефразировка не происходит, если вставка не приводит к превышению размера контейнера z * B где z максимальный коэффициент загрузки и B текущее количество ведер. [23.2.5 / 14]

Контейнерные адаптеры

• stack: наследуется от нижележащего контейнера
• queue: наследуется от нижележащего контейнера
• priority_queue: наследуется от нижележащего контейнера

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

• vector: каждый итератор и ссылка в или после точки стирания становятся недействительными [23.3.6.5/3]
• deque: стирание последнего элемента делает недействительными только итераторы и ссылки на стертые элементы и итератор «за конец»; удаление первого элемента делает недействительными только итераторы и ссылки на стертые элементы; стирание любых других элементов делает недействительными все итераторы и ссылки (включая итератор «за конец») [23.3.3.4/4]
• list: только итераторы и ссылки на стертый элемент признаны недействительными [23.3.5.4/3]
• forward_list: только итераторы и ссылки на стертый элемент недействительны (относится к erase_after) [23.3.4.5/1]
• array: (П / а)

Ассоциативные контейнеры

• [multi]{set,map}: только итераторы и ссылки на стертые элементы становятся недействительными [23.2.4 / 9]

Неупорядоченные ассоциативные контейнеры

• unordered_[multi]{set,map}: только итераторы и ссылки на стертые элементы становятся недействительными [23.2.5 / 13]

Контейнерные адаптеры

• stack: наследуется от нижележащего контейнера
• queue: наследуется от нижележащего контейнера
• priority_queue: наследуется от нижележащего контейнера

• vector: согласно вставке / стиранию [23.3.6.5/12]
• deque: согласно вставке / стиранию [23.3.3.3/3]
• list: согласно вставке / стиранию [23.3.5.3/1]
• forward_list: согласно вставке / стиранию [23.3.4.5/25]
• array: (нет данных)

Примечание 1

Если не указано иное (или
явно или путем определения функции
с точки зрения других функций), вызывая
функция-член контейнера или передача
контейнер в качестве аргумента
функция библиотеки не должна делать недействительной
итераторы или изменить значения,
объекты в этом контейнере.
[23.2.1 / 11]

Заметка 2

функция swap () не делает недействительной
ссылки, указатели или итераторы
ссылаясь на элементы
контейнеры меняются местами. [ Заметка:
end () итератор не относится ни к какому
элемент, так это может быть признан недействительным.
— Конечная записка] [23.2.1 / 10]

Заметка 3

Кроме вышеупомянутого предостережения относительно swap(), неясно, подчиняются ли «конечные» итераторы вышеупомянутым правилам для каждого контейнера; в любом случае вы должны предположить, что они есть.

Примечание 4

vector и все неупорядоченные ассоциативные контейнеры служба поддержки reserve(n) что гарантирует, что автоматическое изменение размера не произойдет, по крайней мере, пока размер контейнера не увеличится до n, Следует соблюдать осторожность при неупорядоченные ассоциативные контейнеры потому что будущее предложение позволит указать минимальный коэффициент нагрузки, который позволит перефразировать на insert после достаточно erase операции уменьшают размер контейнера ниже минимального; гарантия должна считаться потенциально недействительной после erase,

Вероятно, стоит добавить, что итератор вставки любого вида (std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator) гарантированно остается действительным, пока все вставки выполняются через этот итератор, и не происходит никакого другого независимого события, отменяющего итератор.

Например, когда вы выполняете серию операций вставки в std::vector используя std::insert_iterator вполне возможно, что эти вставки вызовут перераспределение вектора, что сделает недействительными все итераторы, которые «указывают» на этот вектор. Тем не менее, рассматриваемый итератор вставки гарантированно останется действительным, то есть вы можете безопасно продолжить последовательность вставок. Нет нужды беспокоиться о перераспределении вектора.

Это, опять же, относится только к вставкам, выполняемым через сам итератор вставки. Если событие отмены итератора инициируется каким-либо независимым действием над контейнером, то итератор вставки также становится недействительным в соответствии с общими правилами.

Например, этот код

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
*it_ins++ = rand();

гарантированно выполнить допустимую последовательность вставок в вектор, даже если вектор «решает» перераспределить где-то в середине этого процесса. Итератор it очевидно станет недействительным, но it_ins будет продолжать оставаться в силе.

Поскольку этот вопрос набирает столько голосов и становится своего рода FAQ, я думаю, что было бы лучше написать отдельный ответ, чтобы упомянуть одно существенное различие между C ++ 03 и C ++ 11 в отношении воздействия std::vectorОперация вставки на действительность итераторов и ссылок в отношении reserve() а также capacity(), который самый голосующий ответ не заметил.

C ++ 03:

Перераспределение делает недействительными все ссылки, указатели и итераторы
ссылаясь на элементы в последовательности. Гарантируется, что нет
перераспределение происходит во время вставок, которые происходят после вызова
reserve () до того времени, когда вставка сделает размер
вектор больше размера, указанного в последнем вызове
резерв().

C ++ 11:

Перераспределение делает недействительными все ссылки, указатели и итераторы
ссылаясь на элементы в последовательности. Гарантируется, что нет
перераспределение происходит во время вставок, которые происходят после вызова
reserve () до того времени, когда вставка сделает размер
вектор больше, чем значение емкости ().

Так что в C ++ 03 это не такunless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)«как уже упоминалось в другом ответе, вместо этого должно быть»greater than the size specified in the most recent call to reserve()«. Это одна вещь, которая отличает C ++ 03 от C ++ 11. В C ++ 03, однажды insert() заставляет размер вектора достигать значения, указанного в предыдущем reserve() вызов (который вполне может быть меньше, чем текущий capacity() с reserve() может привести к большему capacity() чем просил), любой последующий insert() может вызвать перераспределение и сделать недействительными все итераторы и ссылки. В C ++ 11 этого не произойдет, и вы всегда можете доверять capacity() точно знать, что следующее перераспределение не произойдет до того, как размер превысит capacity(),

В заключение, если вы работаете с вектором C ++ 03 и хотите, чтобы при выполнении вставки перераспределение не происходило, это значение аргумента, который вы ранее передали reserve() что вы должны проверить размер, а не возвращаемое значение вызова capacity()иначе вы можете удивитьсяпреждевременныйПерераспределение.