Форум программистов, компьютерный форум CyberForum.ru

Инкремент невалидного итератора - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
11.11.2011, 09:32     Инкремент невалидного итератора #1
Привет.

Этот вопрос задали знакомому на собеседовании...

Что произойдет при инкременте невалидного итератора?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2011, 09:32     Инкремент невалидного итератора
Посмотрите здесь:

[C++] Разыменование итератора. C++
C++ Проверка итератора
Ошибка в объявлении итератора C++
Возврат итератора из функции C++
Собственный класс итератора C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
11.11.2011, 09:45     Инкремент невалидного итератора #2
Цитата Сообщение от PointsEqual Посмотреть сообщение
Привет.

Этот вопрос задали знакомому на собеседовании...
Что произойдет при инкременте невалидного итератора?
Скорее всего по стандарту это UB. А в реальности - зависит от компилятора. Наиболее вероятный исход - аварийный останов программы.
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
11.11.2011, 09:47  [ТС]     Инкремент невалидного итератора #3
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Скорее всего по стандарту это UB
именно это он ответил. Ему сказали неправильно
Bers
Заблокирован
11.11.2011, 09:48     Инкремент невалидного итератора #4
Цитата Сообщение от PointsEqual Посмотреть сообщение
Что произойдет при инкременте невалидного итератора?
инкрементируется невалидный итератор. Не?
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
11.11.2011, 09:49  [ТС]     Инкремент невалидного итератора #5
Цитата Сообщение от Bers Посмотреть сообщение
Не?
ответ то ему не сказали.
Вот я хочу сам узнать что будет
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
11.11.2011, 09:51     Инкремент невалидного итератора #6
Цитата Сообщение от PointsEqual Посмотреть сообщение
именно это он ответил. Ему сказали неправильно
Ну и послать такую компанию нафиг. Здравый смысл рулит в программировании чаще, чем знание запятых в стандарте.
Понятно, что это будет авария в программе...
Или задать вопрос6 какой из итераторов, там их разных видов - дофига!
Bers
Заблокирован
11.11.2011, 09:51     Инкремент невалидного итератора #7
Цитата Сообщение от PointsEqual Посмотреть сообщение
ответ то ему не сказали.
Вот я хочу сам узнать что будет
Да ничего не произойдёт. Не_валидный итератор благополучно инкрементируется.
Просто доступ к самому элементу через него может привести к непредсказуемому результату. Сам итератор не знает, валидный он или нет.
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
11.11.2011, 09:51  [ТС]     Инкремент невалидного итератора #8
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Ну и послать такую компанию нафиг

Не по теме:

yandex не хочется посылать)

ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
11.11.2011, 09:58     Инкремент невалидного итератора #9
PointsEqual, посылать, непременно посылать!
Но можно по аналогии с указателем ответить. Указатель просто инкрементируется. А итератор - это абстрактный указатель (в стандарте так написано)... Сделан по аналогии с указателем. Значит и поведение должно быть аналогичное...

Добавлено через 2 минуты
Цитата Сообщение от PointsEqual Посмотреть сообщение
именно это он ответил. Ему сказали неправильно
Вот, кстати, программеры мыслят одинаково. Как ДОЛЖНО быть - для надежности...
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
31.07.2012, 12:11     Инкремент невалидного итератора #10
Цитата из книжки "Обобщённое программирование и STL":
Каждый массив в Си имеет один указатель, указывающий за его конец. Его нельзя разыменовывать, поскольку в действительности он ни на что не указывает, и к нему не применяется операция инкремента, потому что каждый массив имеет только один указатель за конец, но его можно использовать для сравнения и в арифметических операциях над указателями.
Вот только не понятно, что здесь значит "не применяется"? То ли нельзя так делать совсем, то ли просто никому в голову не придёт инкрементировать его. Хотя понятно, что хорошо спроектированный итератор должен и эту ситуацию предусматривать.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 12:50     Инкремент невалидного итератора #11
Цитата Сообщение от John Prick Посмотреть сообщение
Вот только не понятно, что здесь значит "не применяется"?
Вы б читали внимательнее.
> Каждый массив в Си имеет один указатель, указывающий за его конец. Его нельзя разыменовывать [...]
Его — указатель, указывающий за конец массива.

Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Но можно по аналогии с указателем ответить. Указатель просто инкрементируется. А итератор - это абстрактный указатель (в стандарте так написано)... Сделан по аналогии с указателем. Значит и поведение должно быть аналогичное...
А теперь хотите загадку? У меня есть итератор по связному списку. Как он работает и откуда берёт указатель на следующий элемент, вы себе представляете. Итератор остановился посередине списка. Я удаляю список. Теперь итератор для перемещения вперёд должен обратиться к памяти, которая не принадлежит программе, что есть UB.

В стандарте вроде бы достаточно очевидно написано про UB (lib.iterator.requirements + предусловия для всех инкрементов того, чтобы итератор был разыменовываемым).

Другое дело, что UB — это не требование форматировать диски и пулять ракетами по Пентагону. Это только значит, что поведение оставляется на усмотрение реализации, а она вольна творить, что ей хочется: сообщать об ошибке, ничего не ломать или форматировать диски. Хороший итератор ругнётся, если он инвалидный.
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
31.07.2012, 12:54     Инкремент невалидного итератора #12
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Вы б читали внимательнее.
> Каждый массив в Си имеет один указатель, указывающий за его конец. Его нельзя разыменовывать [...]
Его — указатель, указывающий за конец массива.
К Вам тоже относится. "не применяется" - относилось к операции инкремента к указателю за конец массива. Собственно, об этом и разговор, а не об его (указателя, естественно, а не конца массива) разыменовывании.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 13:08     Инкремент невалидного итератора #13
My bad. Понял.

В любом случае это UB. Мои пруфы:
[lib.iterator.requirements]/5
Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding container. These values are called past-the-end values. Values of an iterator i for which the expression *i is defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable. Iterators can also have singular values that are not associated with any container. [ Example: After the declaration of an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular value of a pointer. — end example ] Results of most expressions are undefined for singular values; the only exceptions are destroying an iterator that holds a singular value and the assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable values are always non-singular.

[lib.iterator.requirements]/10
An invalid iterator is an iterator that may be singular.

Сноска к нему же: This definition applies to pointers, since pointers are iterators. The effect of dereferencing an iterator that has been invalidated is undefined.
Отсюда следует, что итератор в положении «past-the-end» и итератор, не связанный с каким-либо контейнером (singular; например, итератор от удалённого контейтера) не обязательно являются dereferenceable, а значит могут быть singular, а значит являются invalud, а значит их разыменование и большая часть операций приводят к UB.

Но, как уже говорил, UB — это не взрывать Пентагон (defns.undefined).
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
31.07.2012, 20:31     Инкремент невалидного итератора #14
~OhMyGodSoLong~, Ну тут про разыменование говорится, а не конкретно про инкремент.
DaskOFF
 Аватар для DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 521
Записей в блоге: 1
31.07.2012, 20:37     Инкремент невалидного итератора #15
что такое UB подскажите
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 20:42     Инкремент невалидного итератора #16
Цитата Сообщение от ForEveR Посмотреть сообщение
~OhMyGodSoLong~, Ну тут про разыменование говорится, а не конкретно про инкремент.
Там же чуть выше есть и про «результат большинства операций не определён для сингулярных значений» и «итераторы за границей допустимых не обязательно разыменовываемы» (а разыменовываемость прописана в предусловиях для инкремента). Это раз, а ещё плюс «всё, что не указано явно, может считаться неопределённым поведением» (из определения неопределённого поведения).

Цитата Сообщение от DaskOFF Посмотреть сообщение
что такое UB подскажите
Undefined behavior, «неопределённое поведение».
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,578
Записей в блоге: 17
31.07.2012, 20:47     Инкремент невалидного итератора #17
Итератор это класс, а значит результат инкремента главным образом будет определятся именно его реализацией.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
31.07.2012, 20:49     Инкремент невалидного итератора #18
~OhMyGodSoLong~, Вообще в стандарте явно прописано.

pre: r is dereferenceable.
post: r is dereferenceable or
r is past-the-end.
post: any copies of the
previous value of r are no
longer required either to be
dereferenceable or to be in
the domain of ==.
Это для input итераторов, а следовательно и для forward, bidirectional, и random-access.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2012, 20:55     Инкремент невалидного итератора
Еще ссылки по теме:

C++ реализация итератора
C++ Валидность итератора
Ошибка в объявлении итератора C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 20:55     Инкремент невалидного итератора #19
Ну именно. Итератор должен быть dereferencable. Singular-итераторы (итераторы на несуществующие коллекции) по определению не dereferencable. Итератор за границей контейнера никогда не полагаются dereferencable (могут быть, но не обязаны). Нарушается предусловие операции — вся операция это один большой UB.

Но. В свете изначальной сути вопроса. Вот это всё моё про UB касается стандартных итераторов. Для остальных Avazart правильно сказал: «См. реализацию».
Yandex
Объявления
31.07.2012, 20:55     Инкремент невалидного итератора
Ответ Создать тему
Опции темы

Текущее время: 21:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru