for_each в reverse_iterator настраиваемого двунаправленного итератора требует OutputIterator

Я создал простой неизменяемый двунаправленный итератор:

#include <iostream>
#include <memory>
#include <iterator>
#include <vector>
#include <algorithm>

class my_iterator : public std::iterator<std::bidirectional_iterator_tag, int
//, std::ptrdiff_t, int*, int
> {
  int d_val;
public:
  my_iterator() : d_val(0) {}
  my_iterator(int val) : d_val(val) {}

  my_iterator  operator--(int) { d_val--; return my_iterator(d_val + 1); }
  my_iterator &operator--()    { d_val--; return *this; }
  my_iterator  operator++(int) { d_val++; return my_iterator(d_val - 1); }
  my_iterator &operator++()    { d_val++; return *this; }

  int operator*() const { return d_val; }

  bool operator==(my_iterator const  &o) { return d_val == o.d_val; }
  bool operator!=(my_iterator const  &o) { return d_val != o.d_val ; }
};


int main() {
  std::reverse_iterator<my_iterator> reverse_it_begin(25);
  std::reverse_iterator<my_iterator> reverse_it_end(12);
  std::for_each(reverse_it_begin, reverse_it_end, [](int e){ std::cout << e << ' '; });
  std::cout << '\n';
}

Итератор неизменяем, поскольку operator * () возвращает int вместо int ссылки. Насколько я понимаю, это возможно, поскольку независимо от того, соответствует ли итератор концепции BidirectionalIterator или концепции OutputIterator, ортогонален (возможны все 4 комбинации).

Однако приведенный ниже код приводит к ошибке времени компиляции, а именно:

/usr/include/c++/4.9/bits/stl_iterator.h:164:9: error: invalid initialization of non-const reference of type 'std::reverse_iterator<my_iterator>::reference {aka int&}' from an rvalue of type 'int'

Полный контекст:

In file included from /usr/include/c++/4.9/bits/stl_algobase.h:67:0,
                from /usr/include/c++/4.9/bits/char_traits.h:39,
                from /usr/include/c++/4.9/ios:40,
                from /usr/include/c++/4.9/ostream:38,
                from /usr/include/c++/4.9/iostream:39,
                from prog.cpp:1:
/usr/include/c++/4.9/bits/stl_iterator.h: In instantiation of 'std::reverse_iterator<_Iterator>::reference std::reverse_iterator<_Iterator>::operator*() const [with _Iterator = my_iterator; std::reverse_iterator<_Iterator>::reference = int&]':
/usr/include/c++/4.9/bits/stl_algo.h:3755:6:   required from '_Funct std::for_each(_IIter, _IIter, _Funct) [with _IIter = std::reverse_iterator<my_iterator>; _Funct = main()::<lambda(int)>]'
prog.cpp:30:86:   required from here
/usr/include/c++/4.9/bits/stl_iterator.h:164:9: error: invalid initialization of non-const reference of type 'std::reverse_iterator<my_iterator>::reference {aka int&}' from an rvalue of type 'int'
  return *--__tmp;
        ^

Success time: 0 mem

На страницах cppreference о reverse_iterator и for_each говорится, что оба нуждаются в BidirectionalIterator и InputIterator соответственно. Я думаю, что оба требования выполнены, однако stl по-прежнему присваивает ссылке разыменованное значение.

Почему stl for_each / reverse_iterator ожидает оператора T & * () на итераторе, который не должен быть OutputIterator?

PS: Прокомментированная строка может решить проблему, заявив, что ссылки должны храниться по значению, конечно, очень хакерски.


person Herbert    schedule 20.02.2015    source источник
comment
my_iterator не удовлетворяет требованиям итератора, одним из которых является то, что operator* возвращает ссылку.   -  person Igor Tandetnik    schedule 20.02.2015
comment
Верно это, я предполагаю, что это связано с тем, что ссылки быстрее, чем копии, при передаче значений итератора через все stl-api (или другие) средства, такие как std :: copy и т. Д.   -  person Herbert    schedule 20.02.2015


Ответы (2)


Требования к итераторам для всех итераторов перечислены в [iterator.iterators]:

введите описание изображения здесь

reference относится к typedef iterator_traits<my_iterator<..>>:

В следующих разделах a и b обозначают значения типа X или const X, difference_type и reference относятся к типам iterator_traits<X>::difference_type и iterator_traits<X>::reference соответственно, [..]

Поскольку в основном шаблоне iterator_traits по умолчанию используются typedef для типов, определенных в самом аргументе шаблона, мы говорим о reference typedef для my_iterator, который наследуется от базового std::iterator<...>, которое по умолчанию равно T&.
Однако ваш operator* возвращает int, что определенно не int&.

Раскомментирование строки подходит для InputIterators, поскольку int можно преобразовать в int:

введите описание изображения здесь

Однако он не работает для ForwardIterators - [forward.iterators] / 1:

Тип класса или указателя X удовлетворяет требованиям прямого итератора, если

- если X - изменяемый итератор, reference - ссылка на T; если X - константный итератор, reference - ссылка на const T,

person Columbo    schedule 20.02.2015

Не требует OutputIterator. Проблема в том, что ваш код нарушает базовое требование для всех итераторов ввода *: *r должен возвращать reference **. Ваш код определяет my_iterator::reference как int & (из-за аргумента шаблона по умолчанию std::iterator), но operator* возвращает int.

Допустимо, чтобы reference фактически не был ссылочным типом (istreambuf_iterator<charT>::reference, например, charT), но operator* должен возвращать reference. reverse_iterator полагается на это, поскольку он определяет свой reference член и, следовательно, возвращаемый тип его operator*, как reference своего обернутого итератора.

Согласно стандарту для прямых итераторов или более сильных reference должен быть ссылочным типом. Но сам стандарт заключается в том, что он вызывает vector<bool>::iterator итератор с произвольным доступом (его operator* должен возвращать прокси), и комитет, по-видимому, планирует еще немного солгать с _ 20_ предложение. Таким образом, хотя создание my_iterator::reference int означало бы, что технически это больше не двунаправленный итератор, на практике он, скорее всего, сработает. Надеюсь, с помощью Concepts мы сможем получить более точные и детализированные требования, чем те, которые у нас есть сейчас.


* В стандарте есть противоречие в отношении итераторов вывода. См. проблему 2437 LWG.

** Технически std::iterator_traits<It>::reference. Для типов классов iterator_traits по умолчанию подчиняется typedef элемента It::reference.

person T.C.    schedule 20.02.2015
comment
Ты дурак. Как только вы введете одну сноску, шлюзы будут открыты. Остановите это безумие! (1) --- (1) на самом деле не безумие. - person Yakk - Adam Nevraumont; 20.02.2015
comment
Если быть точным, в документе array_view говорится, что bounds_iterator удовлетворяет требованиям итератора с произвольным доступом, если иное не указано ниже. Поскольку ниже приведено объявление using reference = const index<Rank>;, bounds_iterator явно не итератор произвольного доступа, несмотря на удовлетворение некоторых других требований. Конечно, его категория указана как using iterator_category = random_access_iterator_tag;, поэтому передача bounds_iterator любой стандартной библиотечной функции, которая принимает итераторы, вызывает неопределенное поведение. Отличная работа. - person Casey; 20.02.2015