iterator -> reverse_iterator
От: LightGreen  
Дата: 29.05.13 07:49
Оценка:
Конструктор reverse_iterator при создании из iterator ведет себя очень странно. Казалось бы, я должен получить указатель на тот же элемент контейнера, только противоположно направленный.
Вот что написано на cplusplus.com:
>explicit reverse_iterator (iterator_type it);
>--- Constructs a reverse iterator from some original iterator it. The behavior of the constructed object replicates the original, except that it iterates through its pointed elements in the reverse order.
На деле я получаю вот что:

void test()
{
   std::list<int> x;
   x.push_back(1);
   std::list<int>::iterator it = x.begin();
   std::list<int>::reverse_iterator itr(it);
   std::cout << *itr;  // <--- в этом месте выскакивает assert: 'list iterator not decrementable'
}

Интересно, это у меня компилятор такой или стандарт C++ заставляет разработчика учитывать реализацию reverse_iterator и делать предварительный сдвиг вперёд?
Re: iterator -> reverse_iterator
От: jazzer Россия Skype: enerjazzer
Дата: 29.05.13 07:56
Оценка:
Здравствуйте, LightGreen, Вы писали:

LG>
void test()
LG>   std::list<int>::iterator it = x.begin();
LG>   std::list<int>::reverse_iterator itr(it);
LG>   std::cout << *itr; 
LG>}


ты разыменовываешь rend() — неудивительно, что получаешь по рукам...

rbegin == reverse_iterator(end())
rend == reverse_iterator(begin())
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re: iterator -> reverse_iterator
От: Evgeny.Panasyuk Россия  
Дата: 29.05.13 08:30
Оценка:
Здравствуйте, LightGreen, Вы писали:

LG>Конструктор reverse_iterator при создании из iterator ведет себя очень странно. Казалось бы, я должен получить указатель на тот же элемент контейнера, только противоположно направленный.


Пример 1: представь что у тебя есть vector, у которого внутри есть "new int[10]". Допустим что итераторы в этом случае — это просто указатели.
По стандарту можно использовать указатель на элемент после последнего, но не указатель на элемент перед первым.
Подумай, как бы ты реализовал ReverseIterator?
По твоей логике, должно быть (*) :
*ReverseIterator(begin(l)) == *begin(l)

Но как бы ты это реализовал? Какой бы был layout у такого reverse итератора?

LG>Интересно, это у меня компилятор такой или стандарт C++ заставляет разработчика учитывать реализацию reverse_iterator и делать предварительный сдвиг вперёд?


Пример 2: У тебя есть range, в котором один элемент. Опять же, следуя твоей логике (*) объясни, как должен вести себя ReverseIterator(end(l))? Должен ли он быть dereferencable? Какой range будет определятся по ReverseIterator(end(l)) .. ReverseIterator(begin(l))? left-open, right-closed ?

Пример 3:
Несмотря на то, что в STL синтаксически происходят операции над итераторами, семантически во многих случаях за этими итераторами скрываются вполне конкретные range'ы. И эти range'ы намного "важнее" конкретных итераторов.

Возьмём допустим std::partition — он производит перестановку элементов согласно унарному предикату: у кого true — налево, а у кого false — направо. И возвращается итератор M на первый элемент второй группы.
Этот итератор M, определяет два range'а:
1. [begin, M) — элементы с pred == true
2. [M, end) — элементы с pred == false

Вот представь, что согласно твоей логике (*)
*ReverseIterator(M) == *M

Будет ли этот ReverseIterator(M) адекватно разбивать ReverseIterator(end) .. ReverseIterator(begin) на два range'а? Сравни с тем что получается при использовании стандартного ReverseIterator.
Это применимо ко многим алгоритмам STL. Даже если взять std::find — там тоже получаются range'ы с чёткими инвариантами.
Re[2]: iterator -> reverse_iterator
От: LightGreen  
Дата: 29.05.13 09:34
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Подумай, как бы ты реализовал ReverseIterator?


Тут думать нечего, реализовал бы точно так же, но в конструктор бы добавил ++it, чтобы получаемый итератор указывал на тот же элемент. Иначе это вообще подстава, тем более, что в приведённой мне цитате из cplusplus нет ни слова про этот неявный сдвиг.
Пример:

[a] [b] [c] [d] [e]

Если iterator содержит указатель на [d], тогда reverse_iterator при создании будет содержать внутренний указатель на [e], и разыменовываться опять в [d]. В чём отличия? Нельзя будет получить reverse_iterator для end() т.к. в конструкторе вылезет assert(), но это логично. Скорее, текущая реализация нелогична — я могу получить reverse_iterator для end(), но не могу разыменовать rbegin().base().
Re[3]: iterator -> reverse_iterator
От: jazzer Россия Skype: enerjazzer
Дата: 29.05.13 09:49
Оценка:
Здравствуйте, LightGreen, Вы писали:

LG>Здравствуйте, Evgeny.Panasyuk, Вы писали:


EP>>Подумай, как бы ты реализовал ReverseIterator?


LG>Тут думать нечего, реализовал бы точно так же, но в конструктор бы добавил ++it, чтобы получаемый итератор указывал на тот же элемент. Иначе это вообще подстава, тем более, что в приведённой мне цитате из cplusplus нет ни слова про этот неявный сдвиг.


У Майерса, помнится, целая глава была про это.

LG>Пример:


LG> [a] [b] [c] [d] [e]


LG>Если iterator содержит указатель на [d], тогда reverse_iterator при создании будет содержать внутренний указатель на [e], и разыменовываться опять в [d]. В чём отличия? Нельзя будет получить reverse_iterator для end() т.к. в конструкторе вылезет assert(), но это логично.


Вот это как раз нелогично. Потому что у тебя на входе пара begin/end — и ты не можешь из нее по-человечески сделать пару rbegin/rend, так как ассерты полезут.

LG>Скорее, текущая реализация нелогична — я могу получить reverse_iterator для end(), но не могу разыменовать rbegin().base().

И в чем тут проблема? Зачем тебе разыменовывать base? Тем более что в данном случае это end
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[4]: iterator -> reverse_iterator
От: LightGreen  
Дата: 29.05.13 10:31
Оценка:
Здравствуйте, jazzer, Вы писали:

J>Вот это как раз нелогично. Потому что у тебя на входе пара begin/end — и ты не можешь из нее по-человечески сделать пару rbegin/rend, так как ассерты полезут.


А это не мой косяк, а авторов STL. Надо было вводить диапазоны итераторов, и тогда конструктор диапазона reverse_range(range) сработал бы отлично. Потому что reverse_iterator(iterator) как раз в текущей реализации сохраняет семантику диапазонов, но нарушает семантику отдельных итераторов.

LG>>Скорее, текущая реализация нелогична — я могу получить reverse_iterator для end(), но не могу разыменовать rbegin().base().


J>И в чем тут проблема? Зачем тебе разыменовывать base? Тем более что в данном случае это end


У меня есть список, который создаётся динамически и итераторы гоняются по нему в обе стороны. Мне нужно, чтобы независимо от типа итератора (прямой или обратный) я мог получить доступ к данным элемента и сделать правильную вставку или удаление. Сейчас добавил две простые шаблонные функции forward_of и reverse_of, которые решают проблему. А если без этих функций, код становится слишком неочевидным.
Re[3]: iterator -> reverse_iterator
От: Evgeny.Panasyuk Россия  
Дата: 29.05.13 12:42
Оценка:
Здравствуйте, LightGreen, Вы писали:

LG>Иначе это вообще подстава, тем более, что в приведённой мне цитате из cplusplus нет ни слова про этот неявный сдвиг.


ISO:

The fundamental relation between a reverse iterator and its corresponding iterator i is established by the identity: &*(reverse_iterator(i)) == &*(i — 1)

SGI:

[3] Note the implications of this remark. The variable rfirst is initialized as reverse_iterator<...> rfirst(V.end());. The value obtained when it is dereferenced, however, is *(V.end() — 1). This is a general property: the fundamental identity of reverse iterators is &*(reverse_iterator(i)) == &*(i — 1). This code sample shows why this identity is important: if [f, l) is a valid range, then it allows reverse_iterator(l), reverse_iterator(f)) to be a valid range as well. Note that the iterator l is not part of the range, but it is required to be dereferenceable or past-the-end. There is no requirement that any such iterator precedes f.

даже у cplusplus.com есть ASCII картинка в примере, и соответствующие описания в: operator*, base.

LG>Пример:

LG> [a] [ь] [c] [d] [e]
LG>Если iterator содержит указатель на [d], тогда reverse_iterator при создании будет содержать внутренний указатель на [e], и разыменовываться опять в [d]. В чём отличия? Нельзя будет получить reverse_iterator для end() т.к. в конструкторе вылезет assert(), но это логично.

reverse_iterator<...>(begin(...)) будет указывать на [ь] и разыменовываться в [a],
reverse_iterator<...>( [e] ) будет указывать на end и разыменовываться в [e],
Так?
У тебя получается range [e .. a], то есть closed range. В то время как STL алгоритмы работают с left-closed, right-open range'ами. То есть у тебя либо один элемент теряется, либо невозможно использовать STL алгоритмы

LG>А это не мой косяк, а авторов STL.


Всегда когда приходилось использовать reverse_iterator — находил его логичным и удобным.
Да даже тут на форуме: 1
Автор: Evgeny.Panasyuk
Дата: 25.03.13
, 2
Автор: Evgeny.Panasyuk
Дата: 11.05.13
, 3
Автор: Evgeny.Panasyuk
Дата: 23.02.13
, 4
Автор: Evgeny.Panasyuk
Дата: 19.03.13
.

LG>Надо было вводить диапазоны итераторов, и тогда конструктор диапазона reverse_range(range) сработал бы отлично. Потому что reverse_iterator(iterator) как раз в текущей реализации сохраняет семантику диапазонов, но нарушает семантику отдельных итераторов.


1. STL практически всегда подразумевает работу с range'ами. Об этом написано в первоисточнике:

Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges.
A range is a pair of iterators that designate the beginning and end of the computation. A range
[i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i. The result of the application of the algorithms in the library to invalid ranges is undefined.


2. чисто range'ы без итераторов, как в D — теряют свойства композиции, код алгоритмов получается менее эффективным, что неприемлемо для C++. Например тот же partition:
auto result = r;
for (;;)
{
    for (;;)
    {
        if (r.empty) return result;
        if (!pred(r.front)) break;
        r.popFront();
        result.popFront();
    }
    // found the left bound
    assert(!r.empty);
    for (;;)
    {
        if (pred(r.back)) break;
        r.popBack();
        if (r.empty) return result;
    }
    swap(r.front, r.back);
    r.popFront();
    result.popFront();
    r.popBack();
}

Чтобы вернуть вменяемый результат, параллельно "рабочему" range'у приходится передёргивать дополнительный range result. В то время как в STL, нет этих лишних телодвижений — возвращается итератор, который практически бесплатно определяет два range'а.

3. В тех случаях, где достаточно простых range и не нужна какая-то особая композиция — можно использовать удобные обвёртки вокруг итераторов:
boost::copy(input | reversed, output);


LG> У меня есть список, который создаётся динамически и итераторы гоняются по нему в обе стороны. Мне нужно, чтобы независимо от типа итератора (прямой или обратный) я мог получить доступ к данным элемента и сделать правильную вставку или удаление.


Покажи решаемую задачу.
Re[4]: iterator -> reverse_iterator
От: LightGreen  
Дата: 29.05.13 14:09
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, LightGreen, Вы писали:


LG>>Иначе это вообще подстава, тем более, что в приведённой мне цитате из cplusplus нет ни слова про этот неявный сдвиг.

EP>даже у cplusplus.com есть ASCII картинка в примере, и соответствующие описания в: operator*, base.

А не проще ли признать, что описание конструктора reverse_iterator в cplusplus написано неверно. В нём должно было быть примечание или ссылка на информацию о преобразовании итераторов. Всего мест в документации, важных для reverse_iterator, не так уж много, и это — одно из них.

LG>>Пример:

LG>> [a] [ь] [c] [d] [e]
LG>>Если iterator содержит указатель на [d], тогда reverse_iterator при создании будет содержать внутренний указатель на [e], и разыменовываться опять в [d]. В чём отличия? Нельзя будет получить reverse_iterator для end() т.к. в конструкторе вылезет assert(), но это логично.

EP>reverse_iterator<...>(begin(...)) будет указывать на [ь] и разыменовываться в [a],

EP>reverse_iterator<...>( [e] ) будет указывать на end и разыменовываться в [e],
EP>Так?
EP>У тебя получается range [e .. a], то есть closed range.

Это не у меня, а у тебя получается closed range, потому что ты заказал begin...[e], а не begin...end. Мой тезис был в том, что нужна либо отдельная функция get_reverse_range(ib, ie, rib, rie), и тогда reverse_iterator(iterator) можно сделать, как я описал, либо функции forward_of(i), reverse_of(i) для случаев, когда преобразуется не диапазон, а отдельный итератор. Собственно, я и добавил эти функции. А какие у меня ещё были варианты? Всегда использовать range вместо отдельного итератора?

EP>1. STL практически всегда подразумевает работу с range'ами. Об этом написано в первоисточнике:

EP>2. чисто range'ы без итераторов, как в D — теряют свойства композиции, код алгоритмов получается менее эффективным, что неприемлемо для C++.
EP>Чтобы вернуть вменяемый результат, параллельно "рабочему" range'у приходится передёргивать дополнительный range result. В то время как в STL, нет этих лишних телодвижений — возвращается итератор, который практически бесплатно определяет два range'а.

Ничего не понял из твоего кода, что он делает и какая семантика range подразумевается. Если вместо итераторов у нас всегда range (с предельным случаем range.size()=0, а не 1, и тогда глупое действие *end() никогда не будет выполнено!), то код поиска и удаления максимального значения из списка выглядит, например, так:
std::list<T>::range r = someList.all(), rbest = someList.none();
for(;r;++r.begin)
{
   if(!rbest || *r < *rbest) rbest = r;
}
someList.erase(rbest);


Здесь подразумевается, что *r эквивалентно *r.begin, а оператор bool() возвращает true, если range не пустой.

EP>3. В тех случаях, где достаточно простых range и не нужна какая-то особая композиция — можно использовать удобные обвёртки вокруг итераторов:

EP>
EP>boost::copy(input | reversed, output);
EP>


Можно использовать, а можно и не использовать (см. выше).

LG>> У меня есть список, который создаётся динамически и итераторы гоняются по нему в обе стороны. Мне нужно, чтобы независимо от типа итератора (прямой или обратный) я мог получить доступ к данным элемента и сделать правильную вставку или удаление.


EP>Покажи решаемую задачу.


Сколько предлагаешь за строчку кода?
Re: iterator -> reverse_iterator
От: Кодт Россия  
Дата: 29.05.13 17:28
Оценка: +2
Здравствуйте, LightGreen, Вы писали:

LG>Конструктор reverse_iterator при создании из iterator ведет себя очень странно. Казалось бы, я должен получить указатель на тот же элемент контейнера, только противоположно направленный.

LG>Вот что написано на cplusplus.com:
>>explicit reverse_iterator (iterator_type it);
>>--- Constructs a reverse iterator from some original iterator it. The behavior of the constructed object replicates the original, except that it iterates through its pointed elements in the reverse order.

Итераторы — это точки на границах элементов:
                       rbegin+1
        rend              | rbegin
          |               |   |
          v               v   v
за-началом [0] [1] [2] [3] [4] за-концом
          ^   ^               ^
          |   |               |
        begin |              end
            begin+1

Прямые итераторы берут элемент справа от себя, обратные — слева от себя.

Всякие маневры по превращению begin в rend-1 недопустимы, потому что в случае begin==end (пустой контейнер) мы получили бы rbegin-1, то есть, вылетели бы за границу области определения.
Тогда как begin <-> rend, end <-> rbegin избавлены от этого противоречия.

Правда, цена удовольствия — лишняя арифметика:
reverse_iterator::operator*() const
{
  iterator it = this->it_;
  return *(--it);
}


Может быть, на cppreference об этом невнятно сказано, а может, даже в стандарте есть дефект — эта самая невнятность. Мне сейчас лень лезть в стандарт смотреть.
Но суть прозрачна.
Перекуём баги на фичи!
Re[5]: iterator -> reverse_iterator
От: Evgeny.Panasyuk Россия  
Дата: 29.05.13 18:23
Оценка:
Здравствуйте, LightGreen, Вы писали:

LG>А не проще ли признать, что описание конструктора reverse_iterator в cplusplus написано неверно. В нём должно было быть примечание или ссылка на информацию о преобразовании итераторов. Всего мест в документации, важных для reverse_iterator, не так уж много, и это — одно из них.


cplusplus.com для меня не авторитет, и тут я его не оправдываю — можно было лучше.
Но необходимый минимум есть — в описании конструктора пример, а в описании самого шаблона класса:

Notice however that when an iterator is reversed, the reversed version does not point to the same element in the range, but to the one preceding it. This is so, in order to arrange for the past-the-end element of a range: An iterator pointing to a past-the-end element in a range, when reversed, is pointing to the last element (not past it) of the range (this would be the first element of the reversed range). And if an iterator to the first element in a range is reversed, the reversed iterator points to the element before the first element (this would be the past-the-end element of the reversed range).


LG>>>Пример:

LG>>> [a] [ь] [c] [d] [e]
LG>>>Если iterator содержит указатель на [d], тогда reverse_iterator при создании будет содержать внутренний указатель на [e], и разыменовываться опять в [d]. В чём отличия? Нельзя будет получить reverse_iterator для end() т.к. в конструкторе вылезет assert(), но это логично.
EP>>reverse_iterator<...>(begin(...)) будет указывать на [ь] и разыменовываться в [a],
EP>>reverse_iterator<...>( [e] ) будет указывать на end и разыменовываться в [e],
EP>>Так?
EP>>У тебя получается range [e .. a], то есть closed range.
LG>Это не у меня, а у тебя получается closed range, потому что ты заказал begin...[e], а не begin...end.

Подчёркнутое это твои слова?

LG>А какие у меня ещё были варианты? Всегда использовать range вместо отдельного итератора?


Я не знаю какие у тебя были варианты, так как ты не показываешь свою задачу

LG>Ничего не понял из твоего кода, что он делает и какая семантика range подразумевается.


Это код из библиотеки алгоритмов стандартной библиотеки языка D, в котором используются iterator-free range'и.

LG>Если вместо итераторов у нас всегда range (с предельным случаем range.size()=0, а не 1, и тогда глупое действие *end() никогда не будет выполнено!), то код поиска и удаления максимального значения из списка выглядит, например, так:

LG>
std::list<T>::range r = someList.all(), rbest = someList.none();
LG>for(;r;++r.begin)
LG>{
LG>   if(!rbest || *r < *rbest) rbest = r;
LG>}
LG>someList.erase(rbest);

LG>Здесь подразумевается, что *r эквивалентно *r.begin, а оператор bool() возвращает true, если range не пустой.

Как-то криво, rbest это range, а someList.erase(rbest) удаляет одно значение

LG>>> У меня есть список, который создаётся динамически и итераторы гоняются по нему в обе стороны. Мне нужно, чтобы независимо от типа итератора (прямой или обратный) я мог получить доступ к данным элемента и сделать правильную вставку или удаление.

EP>>Покажи решаемую задачу.
LG>Сколько предлагаешь за строчку кода?

Ты предаешь мне $ за решение твоей задачи? Нет, спасибо — здесь джентльменский форум — помогают друг другу бесплатно
Или ты предлагаешь мне заплатить тебе за показ твоей задачи, чтобы мы её тут решили?
Re[6]: iterator -> reverse_iterator
От: LightGreen  
Дата: 29.05.13 20:35
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Как-то криво, rbest это range, а someList.erase(rbest) удаляет одно значение


Упс, там опечатка, должно быть rbest = r.current()

EP>Ты предаешь мне $ за решение твоей задачи? Нет, спасибо — здесь джентльменский форум — помогают друг другу бесплатно

EP>Или ты предлагаешь мне заплатить тебе за показ твоей задачи, чтобы мы её тут решили?

Я тут никого не просил решать за меня задачи. Просто задал вопрос про reverse_iterator.
Re[2]: iterator -> reverse_iterator
От: LightGreen  
Дата: 29.05.13 20:37
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Итераторы — это точки на границах элементов:


К>Может быть, на cppreference об этом невнятно сказано, а может, даже в стандарте есть дефект — эта самая невнятность. Мне сейчас лень лезть в стандарт смотреть.

К>Но суть прозрачна.

Спасибо, так намного понятнее. Жаль, что не Вы составляли стандарт C++. Он был бы намного короче и информативнее!
Re[3]: iterator -> reverse_iterator
От: _NN_ www.nemerleweb.com
Дата: 30.05.13 09:12
Оценка:
Здравствуйте, LightGreen, Вы писали:

LG>Спасибо, так намного понятнее. Жаль, что не Вы составляли стандарт C++. Он был бы намного короче и информативнее!


При таком подходе, товарищ Кодт должен был бы составить также всю теоретическую часть программирования
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re[7]: iterator -> reverse_iterator
От: Evgeny.Panasyuk Россия  
Дата: 30.05.13 12:04
Оценка:
Здравствуйте, LightGreen, Вы писали:

EP>>Как-то криво, rbest это range, а someList.erase(rbest) удаляет одно значение

LG>Упс, там опечатка, должно быть rbest = r.current()

Какой тип результата у r.current() ?
Re[4]: iterator -> reverse_iterator
От: LightGreen  
Дата: 30.05.13 20:09
Оценка:
Здравствуйте, _NN_, Вы писали:

_NN>При таком подходе, товарищ Кодт должен был бы составить также всю теоретическую часть программирования


Товарищ Кодт никому ничего не должен. Он просто помог мне разобраться с нюансами reverse_iterator. Думаю, что эту ветку уже можно закрывать.
Re[5]: iterator -> reverse_iterator
От: Кодт Россия  
Дата: 30.05.13 20:16
Оценка:
Здравствуйте, LightGreen, Вы писали:

LG>Товарищ Кодт никому ничего не должен. Он просто помог мне разобраться с нюансами reverse_iterator. Думаю, что эту ветку уже можно закрывать.


Товарищ Кодт, может быть, всему человечеству должен...
Кстати, должен извиниться — ты упомянул cplusplus.com, чья слава подпорчена ляпами, а я погрешил на cppreference.
Меж тем, http://en.cppreference.com/w/cpp/iterator/reverse_iterator даже с картинкой, объясняющей суть.

std::reverse_iterator is an iterator adaptor that reverses the direction of a given iterator. In other words, when provided with a bidirectional iterator, std::reverse_iterator produces a new iterator that moves from the end to the beginning of the sequence defined by the underlying bidirectional iterator.
For a reverse iterator r constructed from an iterator i, the relationship &*r == &*(i-1) is always true; thus a reverse iterator constructed from a one-past-the-end iterator dereferences to the last element in a sequence.
This is the iterator returned by member functions rbegin() and rend() of the standard library containers.

Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.