Неверные векторные итераторы

std::vector итераторы могут быть реализованы как указатели. Следствием этого является то, что если вы добавите элементы в вектор, незавершенные итераторы, очевидно, станут недействительными, потому что в общем случае векторные данные должны быть перераспределены.

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

Является ли дополнение к правилам указателя чем-то вроде «не вычитать итераторы из разных блоков данных» или «не выполнять никаких арифметических действий с недопустимым итератором, пока ему не будет переназначено действительное значение» или что-то еще?

Например, допустима ли следующая программа (которая работает как на Microsoft C++, так и на GCC)?

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::ostream;
using std::vector;

template<class T> ostream& operator<<(ostream& os, vector<T>& v) {
    os << '[';
    bool c = 0;
    for (auto a: v) {
        if (c)
            os << ", ";
        c = 1;
        os << a;
    }
    return os << ']';
}

void f(vector<int>& v, vector<int>::iterator& i) {
    *i = 10;
    for (int j = 0; j < 10; j++)
        v.insert(begin(v), j);
    i = begin(v)+5;
}

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++)
        v.push_back(i);
    auto i = begin(v)+5;
    f(v, i);
    i[1] = 11;
    cout << v << '\n';
    return 0;
}

person rwallace    schedule 27.06.2013    source источник
comment
Что именно вы подразумеваете под итераторами, указывающими на разные блоки данных?   -  person jogojapan    schedule 27.06.2013
comment
И почему пример программы недействителен? В какой момент происходит что-то, что вы считаете недействительным?   -  person jogojapan    schedule 27.06.2013
comment
@jogojapan различные векторы или элементы одного и того же вектора до и после добавления новых элементов вызвали перераспределение.   -  person rwallace    schedule 27.06.2013
comment
Он вставляет несколько элементов, если он вставляет достаточно элементов, вам нужно будет перераспределить вектор (возможно, в другую ячейку памяти), и тогда «i» может стать недействительным   -  person Tomer Arazy    schedule 27.06.2013
comment
@jogojapan Я думаю, что это правильно; он делает итератор недействительным, но ничего с ним не делает, кроме переназначения ему допустимого значения. Я просто пытаюсь выяснить, где именно проходит граница, от которой я, надеюсь, нахожусь с правой стороны.   -  person rwallace    schedule 27.06.2013
comment
@rwallace Хорошо. Вычитание (а затем разыменование) итераторов из разных векторов недопустимо (но это то же самое, что и для указателей). И вычитание (а затем разыменование) итераторов до и после перераспределения недействительно два (так же, как при перераспределении обычного массива).   -  person jogojapan    schedule 27.06.2013
comment
@TomerArazy Но i сбрасывается после вставки с использованием begin(v). Это совершенно справедливо.   -  person jogojapan    schedule 27.06.2013
comment
@jogojapan верно, но с указателями простой акт вычитания в порядке, если вы этого не делаете, а затем разыменовываете, не так ли? Или стандарт С++ теперь рассматривает это как строго говоря неопределенное поведение даже для указателей?   -  person rwallace    schedule 27.06.2013
comment
@jogojapan - Ты прав, я пропустил это   -  person Tomer Arazy    schedule 27.06.2013
comment
Точные правила инвалидации итераторов прописаны в стандарте, и их не нужно угадывать. В соответствии с этими правилами поведение вашей программы не определено.   -  person n. 1.8e9-where's-my-share m.    schedule 27.06.2013
comment
@rwallace Хммм. Ok. Строго говоря, действительно, операция вычитания из итератора произвольного доступа на величину, превышающую его расстояние от начала, не определена. То есть сама операция не определена. Возможно, здесь есть разница с указателями. (У меня также есть ощущение, что мы здесь деликатно... во всех смыслах и целях итераторы должны действовать так же, как (или, как абстракция) указатели, §24.2.1).   -  person jogojapan    schedule 27.06.2013
comment
с указателями простой акт вычитания допустим, если вы не выполняете разыменование — нет, это не так. Любая арифметическая операция с указателем является UB, если либо операнд, либо результат недействительны.   -  person n. 1.8e9-where's-my-share m.    schedule 27.06.2013
comment
@н.м. Интересно. Я не был уверен в этом по указателям. Но что касается вашего предыдущего комментария: какой частью программы является UB?   -  person jogojapan    schedule 27.06.2013
comment
Моя ошибка, вероятно, это не undefined, просто в нем слишком много переменных с именами i.   -  person n. 1.8e9-where's-my-share m.    schedule 27.06.2013


Ответы (1)


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

person Marius    schedule 27.06.2013
comment
Не могли бы вы объяснить, какую часть кода вы конкретно имеете в виду? Также обратите внимание, что простое признание недействительным итератора не означает, что программа недействительна. Это просто означает, что есть определенные вещи, которые вы не должны делать с этим итератором. - person jogojapan; 27.06.2013