Правила аннулирования итераторов - PullRequest
Новая
       34

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

493 голосов
/ 22 июня 2011

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

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

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

Ответы [ 5 ]

403 голосов
/ 22 июня 2011

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: унаследовано от базового контейнера

Erasure

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

  • 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

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

346 голосов
/ 22 июня 2011

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: унаследовано от базового контейнера

Erasure

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

  • 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: (n /a)

Примечание 1

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

Примечание 2

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

Примечание 3

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

Примечание 4

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

42 голосов
/ 02 января 2019

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

Вставка

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

  • vector: Функции insert, emplace_back, emplace, push_back вызывают перераспределение, если новый размер больше старой емкости. Перераспределение делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Если нет перераспределения случается, все итераторы и ссылки до точки вставки остаются действительными. [26.3.11.5/1]
    Что касается функции reserve, перераспределение делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Перераспределение не должно происходить во время вставок, которые происходят после вызова 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: наследуется от нижележащего контейнера

Erasure

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

  • 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)) (для версии unique с аргументом предиката). Делает недействительными только итераторы и ссылки на стертые элементы. [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]

  • Функция

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

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

  • Алгоритм transform: функции op и binary_op не должны делать недействительными итераторы или поддиапазоны или изменять элементы в диапазонах [28.6.4 / 1]

  • accumulate алгоритм: В диапазоне [first, last], binary_op не должен ни изменять элементы, ни делать недействительными итераторы или поддиапазоны [29.8.2 / 1]

  • reduce алгоритм: binary_op не должен делать недействительнымиитераторы или поддиапазоны, ни изменять элементы в диапазоне [первый, последний].[29.8.3 / 5]

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

39 голосов
/ 05 июля 2012

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

22 голосов
/ 08 марта 2014

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

...