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

Question

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

Каковы правила аннулирования итераторов для контейнеров C++?

Желательно в формате краткого списка.

_{(Примечание. Предполагается, что это будет вход в FAQ по C++ в Stack Overflow. Если вы хотите критиковать идею предоставления FAQ в этой форме, то публикация в meta, с которой все это началось, будет подходящим местом для этого. этот вопрос отслеживается в чате C++, где идея FAQ возникла в первую очередь, поэтому ваш ответ, скорее всего, будет прочитан теми, кто придумал эту идею.)}

596

c++ c++11 iterator c++17 c++03 c++-faq

Источник

user560648 22 июн '11 в 10:01

4 ответа

Решение

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

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

449

Источник

user560648 22 июн '11 в 10:01

C++ 17 (Все ссылки взяты из окончательного рабочего проекта CPP17 - n4659)

вставка

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

vector: Функции insert, emplace_back, emplace, push_back вызвать перераспределение, если новый размер больше, чем старая емкость. Перераспределение делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются действительными. [26.3.11.5/1]
С уважением к reserve Функция reallocation делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Перераспределение не должно происходить во время вставок, которые происходят после вызова reserve() до того времени, когда вставка сделает размер вектора больше, чем значение capacity(), [26.3.11.3/6]
deque: Вставка в середине deque делает недействительными все итераторы и ссылки на элементы deque. Вставка в любом конце deque делает недействительными все итераторы в deque, но не влияет на достоверность ссылок на элементы deque. [26.3.8.4/1]
list: Не влияет на достоверность итераторов и ссылок. Если выброшено исключение, никаких эффектов нет. [26.3.10.4/1].
insert, emplace_front, emplace_back, emplace, push_front, push_back функции подпадают под это правило.
forward_list: Ни одна из перегрузок insert_after должны влиять на действительность итераторов и ссылок [26.3.9.5/1]
array Как правило, итераторы массива никогда не аннулируются в течение всего времени жизни массива. Следует отметить, однако, что во время перестановки итератор будет продолжать указывать на тот же элемент массива и, таким образом, будет изменять его значение.

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

All Associative Containers: insert а также emplace члены не должны влиять на действительность итераторов и ссылки на контейнер [26.2.6/9]

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

All Unordered Associative ContainersПерефразирование делает недействительными итераторы, изменяет порядок между элементами и изменения, в которых появляются элементы сегментов, но не делает недействительными указатели или ссылки на элементы. [26.2.7/9]
insert а также emplace члены не должны влиять на достоверность ссылок на элементы контейнера, но могут сделать недействительными все итераторы для контейнера. [26.2.7/14]
insert а также emplace члены не должны влиять на действительность итераторов, если (N+n) <= z * B, где N количество элементов в контейнере до операции вставки, n количество вставленных элементов, B количество контейнеров контейнера, и z максимальный коэффициент загрузки контейнера. [26.2.7 / 15]
All Unordered Associative Containers: В случае операции слияния (например, a.merge(a2)), итераторы ссылаются на переданные элементы и все итераторы ссылаются на a будет признан недействительным, но итераторы для элементов, оставшихся в a2 останется в силе. (Таблица 91 - Неупорядоченные требования к ассоциативным контейнерам)

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

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

подчистка

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

vector: Функции erase а также pop_back сделать недействительными итераторы и ссылки в или после точки удаления. [26.3.11.5/3]
deque: Операция удаления, которая удаляет последний элемент deque делает недействительными только последний итератор и все итераторы и ссылки на стертые элементы. Операция удаления, которая удаляет первый элемент deque но не последний элемент делает недействительными только итераторы и ссылки на стертые элементы. Операция удаления, которая не стирает ни первый элемент, ни последний элемент deque делает недействительным итератор "за конец" и все итераторы и ссылки на все элементы deque, [ Заметка: pop_front а также pop_back являются операциями стирания. —Конечная записка] [26.3.8.4/4]
list: Делает недействительными только итераторы и ссылки на стертые элементы. [26.3.10.4/3]. Это относится к erase, pop_front, pop_back, clear функции.
remove а также remove_if функции-члены: удаляет все элементы в списке, на которые ссылается итератор списка i для которого выполняются следующие условия: *i == value, pred(*i) != false, Делает недействительными только итераторы и ссылки на стертые элементы [26.3.10.5/15].
unique функция-член - удаляет все элементы, кроме первого, из каждой последовательной группы равных элементов, на которые ссылается итератор i В диапазоне [first + 1, last) для которого *i == *(i-1) (для версии уникальной без аргументов) или pred(*i, *(i - 1)) (для версии уникального с аргументом предиката). Делает недействительными только итераторы и ссылки на стертые элементы. [26.3.10.5/19]
forward_list: erase_after аннулирует только итераторы и ссылки на стертые элементы. [26.3.9.5/1].
remove а также remove_if функции-члены - удаляет все элементы в списке, на которые ссылается итератор списка i, для которых выполняются следующие условия: *i == value (за remove()), pred(*i) верно (для remove_if()). Делает недействительными только итераторы и ссылки на стертые элементы. [26.3.9.6/12].
unique функция-член - удаляет все элементы, кроме первого, из каждой последовательной группы равных элементов, указанных итератором i в диапазоне [first + 1, last), для которого *i == *(i-1) (для версии без аргументов) или pred(*i, *(i - 1)) (для версии с аргументом предиката). Делает недействительными только итераторы и ссылки на стертые элементы. [26.3.9.6/16]
All Sequence Containers: clear делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы a, и может сделать недействительным итератор "за конец" (Таблица 87 - Требования к контейнеру последовательности). Но для forward_list, clear не делает недействительными последние итераторы. [26.3.9.5/32]
All Sequence Containers: assign делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы контейнера. За vector а также dequeтакже делает недействительным последний итератор. (Таблица 87 - Требования к контейнеру последовательности)

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

All Associative Containers: erase члены должны делать недействительными только итераторы и ссылки на стертые элементы [26.2.6/9]
All Associative Containers: extract члены делают недействительными только итераторы для удаленного элемента; указатели и ссылки на удаленный элемент остаются действительными [26.2.6/10]

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

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

Общие требования к контейнеру, касающиеся недействительности итератора:

Если не указано иное (явным образом или путем определения функции в терминах других функций), вызов функции-члена контейнера или передача контейнера в качестве аргумента библиотечной функции не должны делать недействительными итераторы или изменять значения объектов в этом контейнере., [26.2.1/12]
нет swap() Функция делает недействительными любые ссылки, указатели или итераторы, ссылающиеся на элементы переставляемых контейнеров. [Примечание: итератор end() не ссылается ни на один элемент, поэтому может быть признан недействительным. —Конечная записка] [26.2.1/(11.6)]

В качестве примеров приведенных выше требований:

transform Алгоритм: op а также binary_op функции не должны делать недействительными итераторы или поддиапазоны, или изменять элементы в диапазонах [28.6.4/1]
accumulate алгоритм: в диапазоне [первый, последний], binary_op не должен ни изменять элементы, ни делать недействительными итераторы или поддиапазоны [29.8.2/1]
reduce Алгоритм: binary_op не должен ни делать недействительными итераторы или поддиапазоны, ни модифицировать элементы в диапазоне [first, last]. [29.8.3/5]

и так далее...

195

Источник

user10190237 02 янв '19 в 10:44

Вероятно, стоит добавить, что итератор вставки любого вида (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 будет продолжать оставаться в силе.

45

Источник

user187690 04 июл '12 в 23:36

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

C++03:

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

C++11:

Перераспределение делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Гарантируется, что перераспределение не происходит во время вставок, которые происходят после вызова функции Reserve (), до тех пор, пока вставка не сделает размер вектора больше, чем значение Capacity ().

Так что в 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()иначе вы можете удивиться "преждевременному" перераспределению.

24

Источник

user3239559 08 мар '14 в 02:24

Вот хорошая сводная таблица с cppreference.com:

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

24

Источник

user2140449 24 апр '20 в 13:44

Другие вопросы по тегам c++ c++11 iterator c++17 c++03 c++-faq

user560648 22 июн '11 в 15:53 2011-06-22 15:53 · Accepted Answer · 2011-06-22 15:53

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,