Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
PointsEqual
ниначмуроФ
836 / 520 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
#1

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

11.11.2011, 09:32. Просмотров 1395. Ответов 18
Метки нет (Все метки)

Привет.

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

Что произойдет при инкременте невалидного итератора?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2011, 09:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Инкремент невалидного итератора (C++):

Проверка итератора - C++
как проверить указывает ли на что либо итератор или он уже неправильный?

Валидность итератора - C++
Допустимо ли делать такие проверки? Код то отрабатывает, но можно ли так делать? std::vector<int> vec = {1, 2, 3, 4, 5}; auto it =...

Разыменование итератора - C++
Делаю предикат-функцию поиска внутри вектора,состоящего из экземпляров класса.Решил использовать итераторы.То есть мне нужно обратиться к...

реализация итератора - C++
Реализация класса List и его итератора: #ifndef LIST_H #define LIST_H #include<iostream> template<class T> class List ...

Достать строку из итератора - C++
имеется map<string, vector<string> > container; for (map<string, vector<string> >::const_iterator it = container.cbegin(); it !=...

Собственный класс итератора - C++
Добрый день! Пишу сейчас одну библиотеку (не использующею STL и другие библиотеки) и для контейнеров решил написать класс итератора: ...

18
ValeryLaptev
Эксперт С++
1046 / 825 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
11.11.2011, 09:45 #2
Цитата Сообщение от PointsEqual Посмотреть сообщение
Привет.

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

Не по теме:

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

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

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

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

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

Другое дело, что UB — это не требование форматировать диски и пулять ракетами по Пентагону. Это только значит, что поведение оставляется на усмотрение реализации, а она вольна творить, что ей хочется: сообщать об ошибке, ничего не ломать или форматировать диски. Хороший итератор ругнётся, если он инвалидный.
0
John Prick
823 / 756 / 152
Регистрация: 27.07.2012
Сообщений: 2,150
Завершенные тесты: 3
31.07.2012, 12:54 #12
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Вы б читали внимательнее.
> Каждый массив в Си имеет один указатель, указывающий за его конец. Его нельзя разыменовывать [...]
Его — указатель, указывающий за конец массива.
К Вам тоже относится. "не применяется" - относилось к операции инкремента к указателю за конец массива. Собственно, об этом и разговор, а не об его (указателя, естественно, а не конца массива) разыменовывании.
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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).
1
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
31.07.2012, 20:31 #14
~OhMyGodSoLong~, Ну тут про разыменование говорится, а не конкретно про инкремент.
0
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
31.07.2012, 20:37 #15
что такое UB подскажите
0
31.07.2012, 20:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2012, 20:37
Привет! Вот еще темы с ответами:

Возврат итератора из функции - C++
в чем заключается проблема с возвратом итератора и как ее исправить? заранее спасибо за ответ =) (ожидаемый от программы ответ "Yes",...

Упрощенная реализация итератора - C++
- Доброго дня завсегдатаи ! Видел на Вашем форуме упрошенную реализацию контейнера std::vector. По моему от Jupiter-а: template<...

Наследование стандартного итератора - C++
Добрый день! Хочу сделать класс "Фильтрующий Итератор" - наследованный от std::vector<int>::iterator, который будет перечислять только...

Ошибка в объявлении итератора - C++
Пытаюсь создать класс deque на основе класса vector. Создал итераторы для deque(все работало) vector<double> ::iterator begin() ...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.