Почему сравнение с "end()" итератором законно?

В соответствии со стандартом С++ (3.7.3.2/4), использующим (не только разыменование, но и копирование, кастинг, что бы то ни было) неправильный указатель undefined (в случае сомнения также см. этот вопрос). Теперь типичный код для перемещения 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() является итератором на гипотетическом элементе за последним элементом контейнера. Там нет элемента, поэтому использование указателя через то, что итератором является поведение undefined.

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

Ответы

Ответ 1

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

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

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

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

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

Ответ 2

Единственное требование для 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);

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

У них есть некоторые общие черты (т.е. вы можете их разыменовать), но об этом.

Ответ 7

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

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

не будет применяться к итератору 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

Ответ 8

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

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

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

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

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

Значение end() - это значение, прошедшее в конце, которое связано с последовательностью до того, как оно будет признано недействительным. Итак, он действительно действителен по определению. Даже с неправильным представлением о "недействительном" буквально правила указателей здесь не применимы.

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

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