Почему сравнение с итератором end () допустимо?

Question

В соответствии со стандартом C ++ (3.7.3.2/4) с использованием (не только разыменование, но и копирование, преобразование и все остальное) недопустимый указатель является неопределенным поведением (в случае сомнения также см. этот вопрос ). Теперь типичный код для обхода контейнера STL выглядит следующим образом:

std::vector<int> toTraverse;
//populate the vector
for( std::vector<int>::iterator it = toTraverse.begin(); it != toTraverse.end(); ++it ) {
    //process( *it );
}

std::vector::end() является итератором для гипотетического элемента за последним элементом контейнера. Там нет элемента, поэтому использование указателя через этот итератор является неопределенным поведением.

Теперь, как тогда работает != end()? Я имею в виду, что для выполнения сравнения должен быть создан итератор, заключающий в себе недопустимый адрес, а затем этот недопустимый адрес должен быть использован в сравнении, которое опять-таки является неопределенным поведением. Законно ли такое сравнение и почему?

Answer 1

Единственное требование для end() - это ++(--end()) == end(). end() может быть просто особым состоянием, в котором находится итератор. Нет никаких причин, по которым итератор end() должен соответствовать указателю любого вида.

Кроме того, даже если бы это был указатель, сравнение двух указателей в любом случае не требует разыменования. Учтите следующее:

char[5] a = {'a', 'b', 'c', 'd', 'e'};
char* end = a+5;
for (char* it = a; it != a+5; ++it);

Этот код будет отлично работать, и он отражает ваш векторный код.

Answer 2

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

Стандарт C, раздел 6.5.6.8, говорит, что он хорошо определен и действителен:

... если выражение P указывает на последний элемент объекта массива, Выражение (P) +1 указывает на один последний элемент объекта массива ...

, но не может быть разыменовано:

... если результат указывает на единицу последний элемент объекта массива, это не должен использоваться в качестве операнда унарный * оператор, который вычисляется ...

Answer 3

Один конец не является недопустимым значением (ни с обычными массивами или итераторами). Вы не можете разыменовать его, но его можно использовать для сравнения.

std::vector<X>::iterator it;

Это единственный итератор. Вы можете назначить ему только действительный итератор.

std::vector<X>::iterator it = vec.end();

Это совершенно правильный итератор. Вы не можете разыменовать его, но вы можете использовать его для сравнения и уменьшения (при условии, что контейнер имеет достаточный размер).

Answer 4

А? Нет правила, которое гласит, что итераторы должны быть реализованы, используя только указатель.

Там может быть логический флаг, который устанавливается, когда операция приращения обнаруживает, что, например, проходит конец допустимых данных.

Answer 5

Simple.Итераторы не являются (обязательно) указателями.

Они имеют некоторые сходства (то есть вы можете разыменовать их), но это все.

Answer 6

Реализация итератора end() контейнера стандартной библиотеки, ну, в общем, определяется реализацией, поэтому реализация может выполнять хитрости, которые она знает для поддержки платформы. Если вы реализовали свои собственные итераторы, вы можете делать все, что захотите - при условии, что они соответствуют стандарту. Например, ваш итератор, если хранит указатель, может хранить указатель NULL, чтобы указать конечный итератор. Или он может содержать логический флаг или еще много чего.

Answer 7

Я отвечаю здесь, поскольку другие ответы устарели; тем не менее, они были не совсем правы в этом вопросе.

Во-первых, C ++ 14 изменил правила, упомянутые в вопросе. Направление через недопустимое значение указателя или передача недопустимого значения указателя в функцию освобождения все еще не определено, но другие операции теперь определяются реализацией, см. Документация по преобразованию "недопустимого значения указателя" в реализациях C ++ .

Во-вторых, слова имеют значение. Вы не можете обойти определения при применении правил. Ключевым моментом здесь является определение «недействительным». Для итераторов это определяется в [iterator.requirements] . На самом деле, даже верно, что указатели являются итераторами , значения «недопустимых» для них немного отличаются. Правила для указателей отображают «недопустимый» как «не косвенный через недопустимое значение», что является частным случаем «не разыменовываемый » для итераторов; однако «не допускается» - это , а не , что означает «недопустимый» для итераторов. «Недопустимый» явно определен как « может быть единственным », тогда как «единственное» значение определено как «не связанный с какой-либо последовательностью» (в том же абзаце определения «разыменованный»). В этом абзаце даже явно определены «ценности прошлого».

Из текста стандарта в [iterator.requirements] ясно, что:

• Прошлые значения не считаются разыменованными (по крайней мере, стандартной библиотекой), как заявляет стандарт.
• Обращающиеся значения не являются единичными, поскольку они связаны с последовательностью.
• Прошлые значения не являются единичными, поскольку они связаны с последовательностью.
• Итератор не является недействительным, если он определенно не является единичным (отрицанием определения «недопустимый итератор»). Другими словами, , если итератор связан с последовательностью, он не является недействительным.

Значение end() является последним значением, которое связано с последовательностью до ее аннулирования. Так что это действительно допустимо по определению. Даже при неверном понимании буквально «неверно» правила указателей здесь не применимы.

Правила, разрешающие == сравнение с такими значениями, содержатся в требованиях к входным итераторам , которые наследуются некоторой другой категорией итераторов (прямой, двунаправленный и т. Д.). Более конкретно, действительные итераторы должны быть сопоставимы в домене итератора таким образом (==). Кроме того, в требованиях прямого итератора указано, домен находится над базовой последовательностью . А требования к контейнерам определяют типы элементов iterator и const_iterator в любой категории итераторов, удовлетворяющие требованиям прямого итератора . Таким образом, == для end() и итератор для одного и того же контейнера должны быть четко определены. Как стандартный контейнер, vector<int> также подчиняется требованиям. Вот и вся история.

В-третьих, даже когда end() является значением указателя (это может произойти при оптимизированной реализации итератора vector экземпляра), правила в вопросе все еще не применимы. Причина упомянута выше (и в некоторых других ответах): «неверный» относится к * (косвенный сквозной), а не к сравнению. Стандартно разрешено сравнивать одно конечное значение определенным образом. Также обратите внимание, что ISO C ++ не является ISO C, они также слегка не совпадают (например, для < для значений указателей, не входящих в один и тот же массив (не указано и не определено), хотя здесь действуют аналогичные правила.

Answer 8

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

Согласно стандарту C ++ (3.7.3.2/4) использование (не только разыменование, но тоже копирование, кастинг, что угодно еще) неверный указатель не определен поведение

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

int arr[5];
int *p=0;
p==arr+4; // OK
p==arr+5; // past-the-end, but OK
p==arr-1; // also OK
p==arr+123456; // not OK, according to your rule