Вопрос по vector, stl, c++, iterator – Что произойдет, если вы увеличите итератор, равный конечному итератору контейнера STL

59

Что если я увеличу итератор на 2, когда он укажет на последний элемент вектора? Вэтот вопрос на вопрос, как настроить итератор для контейнера STL с помощью 2 элементов, предлагаются два различных подхода:

either use a form of arithmetic operator - +=2 or ++ twice or use std::advance()

Я протестировал оба из них с VC ++ 7 для граничного случая, когда итератор указывает на последний элемент контейнера STL или дальше:

<code>vector<int> vec;
vec.push_back( 1 );
vec.push_back( 2 );

vector<int>::iterator it = vec.begin();
advance( it, 2 );
bool isAtEnd = it == vec.end(); // true
it++; // or advance( it, 1 ); - doesn't matter
isAtEnd = it == vec.end(); //false
it = vec.begin();
advance( it, 3 );
isAtEnd = it == vec.end(); // false
</code>

Я иногда видел совет, который можно сравнить с vector :: end () при обходе вектора и других контейнеров:

<code>for( vector<int>::iterator it = vec.begin(); it != vec.end(); it++ ) {
    //manipulate the element through the iterator here
}
</code>

Очевидно, что если итератор перемещается за последний элемент внутри цикла, сравнение в операторе for-loop будет иметь значение false, и цикл с радостью продолжит неопределенное поведение.

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

Ваш Ответ

8   ответов
-1

все же было бы полезно упомянуть использование операторов сравнения> и <, чтобы проверить, прошел ли вы итерацию после конца (или начала при повторении итераций) контейнера. Например

vector<int> vec;
vec.push_back( 1 );
vec.push_back( 2 );

vector<int>::iterator it = vec.begin();

it+=10; //equivalent to advance( it, 10 )
bool isPastEnd = it > vec.end(); //true
Извините, это НЕПРАВИЛЬНО. Как было объяснено ранее, действительный итератор не может быть после итератора «один за другим», то есть end (). curiousguy
Это работает только потому, что реализация std :: vector :: iterator на самом деле является необработанным указателем. С другим контейнером история может быть совершенно другой, она может даже выдать исключение, когда вы попытаетесь пройти конец. Sogartar
7

) и итератором в vec.begin () и сравнить его с размером вектора (полученного с помощью size ()).

В этом случае ваш цикл for будет выглядеть так:

for (vector<int>::iterator it = vec.begin(); distance(vec.begin(), it) < vec.size(); ++it)
{
     // Possibly advance n times here.
}
distance оптимизирована для итераторов с произвольным доступом: ее сложность равна O (1), поскольку она не учитывает ++, но выполняет вычитание Konstantin Tenzin
Это больше связано с тем, как оператор ++ реализован для каждого типа итератора. «расстояние» подсчитывает, сколько ++ или - должно быть выполнено одному итератору, чтобы достичь другого. Если бы я был тобой, я бы попробовал это на всех типах контейнеров, которые я ожидал, и посмотрел бы, какое расстояние мне дает. Kostas
Зависит ли это от непрерывного распределения памяти или будет работать и для других контейнеров? sharptooth
distance () работает на любом итераторе ввода, пересылки, двунаправленного или произвольного доступа в соответствии со стандартом (24.3.4) jalf
@ jalf "distance () работает на любом входном итераторе ": вы, вероятно, не хотите этого делать! curiousguy
13

Возможно, у вас должно быть что-то вроде этого:

template <typename Itr>
Itr safe_advance(Itr i, Itr end, size_t delta)
{
    while(i != end && delta--)
        i++;
    return i;
}

Ты можешь перегрузить это, когдаiterator_category<Itr> являетсяrandom_access_iterator сделать что-то вроде следующего:

return (delta > end - i)? end : i + delta;
3

который предлагает Марийн, немного ошибочен (как заметил любопытный парень).

Правильная версия последней строки:

bool isPastEnd = it >= vec.end();
it > vec.end() можно считать всегда ложным.++vec.end() неопределенное поведение Caleth
58

Обратите внимание, что advance () не проверяет, пересекает ли он конец () последовательности (он не может проверить, потому что итераторы вообще не знают контейнеры, с которыми они работают). Таким образом, вызов этой функции может привести к неопределенному поведению, потому что вызов оператора ++ для конца последовательности не определен

Другими словами, ответственность за поддержание итератора в пределах диапазона полностью лежит на вызывающей стороне.

Как проверить, находится ли он в диапазоне после арифметической операции? Narek
1

определенным внешним значением.

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

Я думаю, что лучшая практика - «не делай этого» - либо проверяй каждое значение итератора (желательно в чем-то, упакованном как фильтр), и работай только с интересными записями, либо используй индекс явно с

for (int i = 0; i <vec.size (); i + = 2) {...}

2

Boost.Range.
Это может быть безопаснее в использовании.
Это также будет в C ++ 0x.

1

for( vector<int>::iterator it = vec.begin(); it != vec.end() && it+1 != vec.end(); it+=2 ) {
    //manipulate the element through the iterator here
}

Я не знаю, как это будет работать против Kostas @ предложение, но оно @ Чувству вроде бы лучше за небольшой прирост. Конечно, это будет довольно неосуществимо для большого приращения, так как вам нужна проверка для каждого, но это другой вариант.

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

Похожие вопросы