Разыменование std::reverse_iterator всегда требует дополнительной итерации, что то вроде:

reference reverse_iterator::operator*() const
{
    iterator tmp = current;
    return (*--tmp);
}

Соответственно, проход по контейнеру с доступом к каждому элементу с использованием reverse_iterator
потребует в два раза больше итераций, нежели прямой проход с использованием iterator

Некоторые контейнеры (деревья, списки) теоретически допускают возможность циклической итерации.
То есть, кроме выполнения обязательных условий:

++rightmost() == end()
--end() == rightmost()

позволяют реализовать выполнение дополнительных:

++end() == begin()
--begin() == end()

Возможность циклической итерации позволяет реализовать более эффективные reverse_iterator для таких контейнеров, то есть вместо сопоставления rend — begin, rbegin — end использовать явное сопоставление rend — end, rbegin — rightmost.

Тогда можно будет не делать сдвиг при разыменовании итератора, а выполнять его только в требуемых стандартом операциях конвертации и сравнения между reverse_iterator и iterator. Такая реализация не будет уступать в эффективности обычным итераторам, но стандарт предписывает использование контейнерами именно std::reverse_iterator. Теоретически, можно было бы предусмотреть предоставление типом итератора информации о возможности циклической итерации. Тогда std::reverse_iterator мог бы реализовать две стратегии — сдвиг при конверсии и сдвиг при разыменовании.

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

S>Разыменование std::reverse_iterator всегда требует дополнительной итерации, что то вроде:
S>

S>reference reverse_iterator::operator*() const
S>{
S>    iterator tmp = current;
S>    return (*--tmp);
S>}
S>

может это издержки реализации? по крайней мере http://www.sgi.com/tech/stl/ReversibleContainer.html ничего не говорит о невозможности сделать reverse_iterator не отличающимся по скорости от обычного итератора.

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

S>Разыменование std::reverse_iterator всегда требует дополнительной итерации, что то вроде:
S>

S>reference reverse_iterator::operator*() const
S>{
S>    iterator tmp = current;
S>    return (*--tmp);
S>}
S>

А зачем у него такая странная реализация? Почему current не указывает непосредственно на нужный элемент?

Здравствуйте, Константин Б., Вы писали:

КБ>А зачем у него такая странная реализация? Почему current не указывает непосредственно на нужный элемент?
Это мелкомягкая(дикумваровская или как ее там) реализация. Сделано, скорее всего, для того, чтобы rend() выглядел достаточно просто.

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

D>Здравствуйте, Константин Б., Вы писали:

КБ>>А зачем у него такая странная реализация? Почему current не указывает непосредственно на нужный элемент?
D>Это мелкомягкая(дикумваровская или как ее там) реализация. Сделано, скорее всего, для того, чтобы rend() выглядел достаточно просто.

Нет, это требование стандарта:

24.4.1 Reverse iterators

1 Bidirectional and random access iterators have corresponding reverse
iterator adaptors that iterate through the data structure in the oppo-
site direction. They have the same signatures as the corresponding
iterators. The fundamental relation between a reverse iterator and
its corresponding iterator i is established by the identity:
&*(reverse_iterator(i)) == &*(i — 1).

2 This mapping is dictated by the fact that while there is always a
pointer past the end of an array, there might not be a valid pointer
before the beginning of an array.

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

S>Нет, это требование стандарта:

S>

S>24.4.1 Reverse iterators

S> 1 Bidirectional and random access iterators have corresponding reverse
S> iterator adaptors that iterate through the data structure in the oppo-
S> site direction. They have the same signatures as the corresponding
S> iterators. The fundamental relation between a reverse iterator and
S> its corresponding iterator i is established by the identity:
S> &*(reverse_iterator(i)) == &*(i — 1).

S>2 This mapping is dictated by the fact that while there is always a
S> pointer past the end of an array, there might not be a valid pointer
S> before the beginning of an array.

это говорит только о том, что мы не можем уменьшать итератор begin(), и о том, что разименованный reverse_iterator должен возврщать тоже значение что и соответствующий ему обычный итератор, *rbegin() == *(end() — 1), *(rend() — 1) == *begin(), но это не запрещает сделать reverse_iterator без дополнительного копирования и декремента обычного итератора.

Здравствуйте, Аноним, Вы писали:

А>это говорит только о том, что мы не можем уменьшать итератор begin(), и о том, что разименованный reverse_iterator должен возврщать тоже значение что и соответствующий ему обычный итератор, *rbegin() == *(end() — 1), *(rend() — 1) == *begin(), но это не запрещает сделать reverse_iterator без дополнительного копирования и декремента обычного итератора.

Приведите пример реализации?

Здравствуйте, Константин Б., Вы писали:

КБ>А зачем у него такая странная реализация? Почему current не указывает непосредственно на нужный элемент?

А вы видели где нибудь другую реализацию?

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

S>Здравствуйте, Аноним, Вы писали:

А>>это говорит только о том, что мы не можем уменьшать итератор begin(), и о том, что разименованный reverse_iterator должен возврщать тоже значение что и соответствующий ему обычный итератор, *rbegin() == *(end() — 1), *(rend() — 1) == *begin(), но это не запрещает сделать reverse_iterator без дополнительного копирования и декремента обычного итератора.

S>Приведите пример реализации?

первое что пришло в голову:

reverse_iterator& operator++()
{
  if (current != begin)
    --current;
  else
    current = end;
  return *this;
}

но вообще, это все не очень актуально, гцц на -O2 проседает всего на 20% по сравнению с обычной прямой итерацией, имхо это будет ботлнеком только в очень специфических случаях.

Здравствуйте, Аноним, Вы писали:

А>первое что пришло в голову:

А>

А>reverse_iterator& operator++()
А>{
А>  if (current != begin)
А>    --current;
А>  else
А>    current = end;
А>  return *this;
А>}
А>

хехе, итератор, содержащий end — ещё куда ни шло... но begin?

А>но вообще, это все не очень актуально, гцц на -O2 проседает всего на 20% по сравнению с обычной прямой итерацией, имхо это будет ботлнеком только в очень специфических случаях.

20% — это как раз не константа, а специфический случай

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

S>хехе, итератор, содержащий end — ещё куда ни шло... но begin?
не вижу принципиальной разницы, и то и то — зависимость реализации от контейнера, не более.

А>>но вообще, это все не очень актуально, гцц на -O2 проседает всего на 20% по сравнению с обычной прямой итерацией, имхо это будет ботлнеком только в очень специфических случаях.
S>20% — это как раз не константа, а специфический случай
это "пустая" итерация по вектору, на деле, проседание на векторе будет ещё меньше... другие контейнеры конечно могут дать худшие результаты, но они вроде как и не предназначены для хранения больших объемов данных и последовательной итерации по ним (деку можно приравнять к вектору в данном случае).

Здравствуйте, Аноним, Вы писали:

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

S>>хехе, итератор, содержащий end — ещё куда ни шло... но begin?
А>не вижу принципиальной разницы, и то и то — зависимость реализации от контейнера, не более.
reverse_iterator по стандарту не является частью реализации контейнера. Это именно std::reverse_iterator. Причем такой, что std::reverse_iterator(container.begin()) == container.rend() и std::reverse_iterator(container.end()) == container.rbegin(). В плане общности он такой какой есть и к нему нет претензий. Я просто говорю о том, что есть определённый класс контейнеров, позволяющий реализацию более эффективных reverse_iterator'ов.

А>>>но вообще, это все не очень актуально, гцц на -O2 проседает всего на 20% по сравнению с обычной прямой итерацией, имхо это будет ботлнеком только в очень специфических случаях.
S>>20% — это как раз не константа, а специфический случай
А>это "пустая" итерация по вектору, на деле, проседание на векторе будет ещё меньше...
пустая итерация неинтересна, нужно разыменование

А>другие контейнеры конечно могут дать худшие результаты,
речь в первую очередь о других контейнерах, для которых итерация — не просто сдвиг указателя

А>но они вроде как и не предназначены для хранения больших объемов данных и последовательной итерации по ним (деку можно приравнять к вектору в данном случае).
э... а почему не предназначены?

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

А>>не вижу принципиальной разницы, и то и то — зависимость реализации от контейнера, не более.
S>reverse_iterator по стандарту не является частью реализации контейнера.
так об этом в общем-то и речь, итератор зависящий от контейнера в реализации ничему не противоречит, хоть и выглядит "не очень".

А>>>>но вообще, это все не очень актуально, гцц на -O2 проседает всего на 20% по сравнению с обычной прямой итерацией, имхо это будет ботлнеком только в очень специфических случаях.
S>>>20% — это как раз не константа, а специфический случай
А>>это "пустая" итерация по вектору, на деле, проседание на векторе будет ещё меньше...
S>пустая итерация неинтересна, нужно разыменование
разыменование было, но быстрое (std::vector<size_t>), специально чтобы понять насколько проседает именно итерация, а не разыменование, прочие действия с элементами контейнера.

А>>но они вроде как и не предназначены для хранения больших объемов данных и последовательной итерации по ним (деку можно приравнять к вектору в данном случае).
S>э... а почему не предназначены?
потому что все дают фрагментацию памяти, а для сортированных контейнеров итерация по порядку вообще имеет смысл наверное только при сериализации. разве что возможен случай, не "много объектов в одном контейнере", а "много контейнеров по которым нужно итерироваться в обе стороны"...

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

S>Соответственно, проход по контейнеру с доступом к каждому элементу с использованием reverse_iterator
S>потребует в два раза больше итераций, нежели прямой проход с использованием iterator

По-моему еще 2003я студия давала на таких итераторах код, аналогичый прямым (по крайней мере для list и vector)

Однако новый стандарт несколько усложняет вещи:

24.4.1.2.4

1 Effects:
this->tmp = current;
--this->tmp;
return *this->tmp;

2 [ Note: This operation must use an auxiliary member variable, rather than a temporary variable, to
avoid returning a reference that persists beyond the lifetime of its associated iterator. (See 24.1.) The
name of this member variable is shown for exposition only. —end note ]

В общем, резюмируя:

Для некоторых контейнеров reverse_iterator действительно мог бы быть простой обёрткой вроде этого:

template<typename iterator>
class reverse_iterator : public iterator
{
    reverse_iterator() {}
    reverse_iterator(const iterator& x) : iterator(x) {}
    reverse_iterator& operator++() { iterator::operator--(); return *this; }
    reverse_iterator& operator--() { terator::operator++(); return *this; } 
    reverse_iterator operator++ (int) { reverse_iterator tmp = *this; ++*this; return tmp; }
    reverse_iterator operator-- (int) { reverse_iterator tmp = *this; --*this; return tmp; }
};

Тут тебе и та же эффективность что у обычных итераторов и явная конверсия (rbegin == --end и rend = --begin). Но в стандарте нет контейнеров, поддерживающих циклическую итерацию. Нет таких требований и к тем контейнерам, которые могли бы быть таковыми (например, map: в stlport --begin даст либо begin (если begin — root) либо end, а в dinkumware стоит assert на ++end). Опять таки это было бы нарушением общности — для одних контейнеров конверсия со сдвигом, для других — прямая и т.п.

Так что, смысл остаётся тем же: "не используйте reverse_iterator" (c)

Хотя обход контейнера в обратном направлении будет в таком случае не очень красивой конструкцией:

for(iterator it=container.end(); it!=container.begin();)
{
    --it; 
    ... 
}
или так:
for(iterator it=container.end(); it!=container.begin() && (--it, true);)

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

S>та же эффективность что у обычных итераторов

#include <vector>
#include <iterator>
#include <algorithm>

int main()
{
  typedef std::vector<int> container;
  typedef std::reverse_iterator<std::reverse_iterator<container::iterator> > iter;

  container v(200);

  std::fill(iter(v.rend()), iter(v.rbegin()), 0);

 /*
    mov    edx, eax
    cmp    eax, ecx
    je    SHORT $LN61@main
    npad    10
$LL37@main:
    mov    DWORD PTR [edx], 0
    add    edx, 4
    cmp    edx, ecx
    jne    SHORT $LL37@main
*/

}

это "наивная" реализация по Стандарту. По-моему проблема лишь в том, что цикл вообще остался.

Здравствуйте, gear nuke, Вы писали:

GN>[/c]это "наивная" реализация по Стандарту. По-моему проблема лишь в том, что цикл вообще остался.

Проблема лишь в том, что это вектор, то есть по сути массив, где итерация — это просто инкремент/декремент указателя.

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

S>Проблема лишь в том, что это вектор, то есть по сути массив, где итерация — это просто инкремент/декремент указателя.

С другой стороны, для доступа к предыдущей ноде std::list<> не обязательно делать декремент итератора. Каждая нода содержит ссылку на предыдущий элемент, можно добавить приватную функцию в итератор и специализировать reverce_iterator<>::operator*() для таких контейнеров

reference operator*() const { return current.__prev(); }

В результате получится

PUBLIC    _main
; Function compile flags: /Ogspy
_main    PROC                        ; COMDAT

; 6    : {
; skip
; 7    :   std::list<int> c(200);
; skip
; 8    :   std::find(c.begin(), c.end(), 0);

    mov    eax, DWORD PTR _c$[ebp+4]
    mov    ecx, eax
    cmp    eax, edx
    je    SHORT $LN42@main
$LL43@main:
    cmp    DWORD PTR [ecx+8], 0
    je    SHORT $LN42@main
    mov    ecx, DWORD PTR [ecx+4]
    lea    edx, DWORD PTR _c$[ebp]
    cmp    ecx, edx
    jne    SHORT $LL43@main
$LN42@main:

; 9    :   std::find(c.rend(), c.rbegin(), 0);

    lea    edx, DWORD PTR _c$[ebp]
    mov    ecx, eax
    cmp    eax, edx
    je    SHORT $LN74@main
$LL75@main:
    mov    ecx, DWORD PTR [ecx]
    cmp    DWORD PTR [ecx+8], 0
    je    SHORT $LN74@main
    lea    edx, DWORD PTR _c$[ebp]
    cmp    ecx, edx
    jne    SHORT $LL75@main
$LN74@main:

; 10   : }
; skip

Я не спроста заменил fill на find В случае с модификацией нод компилятор добавляет повторное чтение указателя на ноду. Это недостатки тестируемой реализации list, где каждая нода содержит неконстантную структуру с линками. При модификации значения, MSVC не может отследить, какая именно ячейка памяти изменилась и вместо того, что бы воспользоваться существующим tmp делает повторные вычисления.