Хотя выглядит так, что random access iterator может как быть OutputIterator (т.е. можно делать *it = i;), так и не быть им (т.е. *it = i; делать нельзя).

Дока говорит, что

The type std::iterator_traits<It>::reference must be exactly
T& if It satisfies OutputIterator (It is mutable)
const T& otherwise (It is constant),

То есть operator* всегда возвращает ссылку, либо константную ссылку. И возвращение не ссылочного типа типо нарушение концепта? Или я туплю?

Random Access Iterator это надстройка над Bidirectional Iterator и он (RAI) не переопределяет поведение *. Тоесть * для Random Access Iterator ведет себя также как и для Bidirectional Iterator и должна возвращять ссылку на объект.

Уточнение: *it не обязан возвращать ссылку на объект который хранится в контейнере, и даже не обязан возвращать ссылку на объект этого-же типа. Должна возвращаться ссылка на чттото что можно привести к value_type (reference, convertible to value_type).

Но это значит что it::value_type и it::reference могут быть одного типа! Они же преобразуемы друг в друга!

Правда cppreference.com говорит что random access iterator -> BidirectionalIterator -> ForwardIterator -> InputIterator -> Iterator

То что вы описали отосится к InputIterator, но уже описания ForwardIterator говорит нам.

The type std::iterator_traits<It>::reference must be exactly
T& if It satisfies OutputIterator (It is mutable)
const T& otherwise (It is constant),

Что значит, что RandomAccessIterator должен возвращать ссылку или константную ссылку

это надстройка над Bidirectional Iterator и он (RAI) не переопределяет поведение

Лично я понимаю это так. Если мы ожидаем на вход нашей функции InputIterator, то нечто возвращаемое по *it вполне удовлетворяет простому условию

*i	reference, convertible to value_type

Контракт InputIterator здесь не нарушен.

Но если мы ожидаем на вход именно RandomInterator (или ForwardIterator), то нет гарантии, что *it возвращающий не ссылку будет работать тут корректно.

Поправьте, пожалуйста, если я где-то не прав.

неважно что вернул нам *it ссылку или сам тип value_type

Как это не важно ? Важно что возвращается именно ссылка. Тоесть это подрозумевает что нету временных объектов, нету копирующих конструкторов, и можно сохранить / передать ссылку и она будет рабочей даже если сам итератор уже разрушится

Хм, а где это сказанно? Именно дл inputiterator, для randomaccess необходимость ссылки для меня ясна. А вот для inputiterator не очень. Можно даже в станларт ткнуть, ну или в цппреференс на худой конец=)

http://en.cppreference.com/w/cpp/concept/InputIterator

*i - reference, convertible to value_type

Вот пример кода для которого reference работать будет а value - нет

template<class T>
class MyStorage
{
   T *lastVal;

   T& last() { return *lastVal; }
   T& find(K key)
   {
       Map::iterator it = map.find(key);
       lastVal = &(*it);
       return *lastVal;
   }
}

секция input.iterators

24.2.3