Для входных итераторов, почему a == b не подразумевает ++ a == ++ b? - PullRequest
14 голосов
/ 10 мая 2011

§24.1.1 / 3 из C ++ 03 Стандартные чтения,

Для входных итераторов a == b не подразумевает ++ a == ++ b. ( Равенство не означает гарантировать замещение имущества или ссылочная прозрачность. ) Алгоритмы на входных итераторах никогда не должно попытка пройти через то же самое итератор дважды. Они должны быть одинокими пройти алгоритмы. Тип значения T не должен быть назначаемого типа (23.1). Эти алгоритмы могут быть использованы с истоками в качестве источника входные данные через istream_iterator class.

Я не мог понять жирный текст в приведенной выше цитате. Может ли кто-нибудь помочь мне понять это?

Кроме того, что означает следующее утверждение (выделенный курсивом текст в приведенной выше цитате)? Как это связано с a==b и ++a==++b выражениями?

Равенство не гарантировать замещение имущества или ссылочная прозрачность.

Ответы [ 5 ]

9 голосов
/ 10 мая 2011

Для входных итераторов приращение итератора делает недействительными копии того же итератора.

Итак:

auto a = istream_iterator<whatever>(something);
auto b = a;
a == b; // true
++a;    // b is now invalid
++b;    // undefined behavior, I think, but in any case not guaranteed to
        // result in anything sensible.

Так что, конечно, ++a == ++b не гарантируется.То есть a == b не означает ++a == ++b.

Я думаю, что «свойство подстановки» означает, что «все, что вы делаете со значением a, имеет тот же результат, что и то же, что и со значениемb "или аналогичный - существуют различные варианты подстановки, на которые он может ссылаться, но что-то в этом роде.Я думаю, что в этом контексте это должно означать « позже , делающий то же самое с b», поскольку, если a == b и я еще ничего не сделал недействительным, то не имеет значения, какой из a и b Я использую, они ссылаются на одну и ту же точку в потоке.Но когда я увеличиваю, мне нужно выбрать один и потерять другой, поэтому сложность с ++a == ++b.

«Ссылочная прозрачность» означает, что разные объекты независимы, то есть они не являются ссылками / указателями наили псевдонимы друг друга.В сочетании с «свойством замещения» это означает:

Позже?Не существует ранее или позже , поскольку операции не имеют глобальных побочных эффектов.Если вы не можете заменить «позже», тогда вы не можете заменить

Итераторы ввода в одной и той же последовательности обычно ссылаются на одни и те же «фактические данные», такие как дескриптор файла или любой другой объект, который сам содержитизменчивое состояние.Поскольку a и b ссылаются на один и тот же дескриптор файла, а их значение зависит от его состояния, у вас нет ссылочной прозрачности.Этот недостаток , почему замена не удалась.

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

6 голосов
/ 10 мая 2011

Как говорится в объяснении: «Это должны быть однопроходные алгоритмы».

Дело в том, что итератор входного потока представляет переходное состояние.Как только итератор изменен, это состояние больше не существует;все другие итераторы, представляющие это состояние, становятся недействительными: после увеличения a итератор b становится недействительным.

3 голосов
/ 10 мая 2011

Указанные свойства:

Свойство замещения

Для любых величин a и b и любого выражения F (x), если a = b, тогда F (a) = F (b) (если любая сторона имеет смысл, т.е. имеет правильную форму).

Ссылочная прозрачность

Неформально это означает, что нет разницы между значением и ссылкой на это значение (таким образом, как термин был придуман).

В императивном программировании это сложная концепция, потому что мыиспользуются для изменения наших переменных.Рик Хикки (позади Clojure) рассказывает о различии между Идентичностью и Государством , которое может вам помочь.Суть в том, что переменная - это идентичность.В любой момент времени идентификатор относится к государству.Состояние никогда не изменяется, однако идентификатор может быть изменен для ссылки на другое состояние.

Итераторы ввода

Свойство подстановки нарушение очевидно«здесь, если мы определим F(x) в вышеприведенном значении ++x, то получим, что если входные итераторы проверяют свойство подстановки, следующее будет содержать a == b => ++a == ++b.

Однако это не такпотому что увеличение входного итератора может сделать недействительными все другие входные итераторы из того же источника.Из таблицы 107 в n3290 (стр. 831, чуть выше упомянутого вами абзаца):

++ r

pre: r является разыменованным.

post: rявляется разыменовываемым или r является устаревшим.

post: любые копии предыдущего значения r больше не должны быть разыменованными или находиться в области ==.

То есть, когда мы выполняем ++a, тогда b может стать недействительным, и поэтому ++b само будет неопределенным поведением.

Это прямое нарушение ++a == ++b, поэтому свойство подстановки не выполняется.

Ссылочная прозрачность немного более очевидна.Если бы входные итераторы были прозрачными по ссылкам, это означало бы, что они были бы неразличимы от значения, на которое они указывают.Ясно, что это не так, поскольку применение ++ увеличивает значение не на единицу, а на итератор.

2 голосов
/ 10 мая 2011

Входные итераторы определяют последовательность, которую можно прочитать только один раз;Ввод с клавиатуры или трубы будет хорошим примером.Увеличение istream_iterator фактически означает дальнейшее чтение в istream, извлечение символов, поэтому другие istream_iterator в том же потоке больше не будут действительны в отношении их положения.Представьте себе поток символов "abcdefg..." (алфавит, в сумме) с двумя istream_iterator<char>, указывающими на 'a'.Увеличение одного из них приведет к чтению 'b' из потока, и никакой другой итератор не сможет его увидеть.

1 голос
/ 10 мая 2011

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

Увеличение копии итератора также не означает чтение того же символа.

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