Где это означает?

Чтобы поддерживать STL-представление полуоткрытых диапазонов, нам разрешено указывать один-на-конец массива. Предположим, что у нас есть вектор трех элементов. Если std::vector::iterator реализуется как указатель, как это обычно бывает в релиз-сборках, то begin и end указывают на следующие местоположения:

    +---+---+---+....
    |   |   |   |   .
    +---+---+---+....
      ^           ^
    begin        end

В тех случаях, когда точки обозначают псевдоэлемент, прошедший один конец. Так как нет такой вещи, как одно-до-начала, где именно rend указывает? Позвольте мне проиллюстрировать:

    +---+---+---+....
    |   |   |   |   .
    +---+---+---+....
  ^           ^
rend       rbegin

Ясно, что иллюстрация неверна, потому что rend является незаконным указателем. Поэтому я предполагаю, что реализация std::vector::reverse_iterator никогда не может быть указателем, даже в версиях.

Я прав? Каким будет наиболее эффективный способ реализации reverse_iterator тогда?

Ответы

Ответ 1

Существует разница между тем, на что логически указывает reverse_iterator и тем, на что указывает содержащийся в нем итератор. Логически, rbegin итератор, который указывает на последний элемент последовательности, а rend - итератор, который указывает на один элемент перед началом. Но это обычно реализуется с помощью базового итератора, который указывает на следующее местоположение после местоположения, на которое указывает обратный итератор. Что-то вроде этого:

template<class Iter>
class reverse_iter
{
    Iter base;
public:
    explicit reverse_iter(Iter it) : base(it) {}

    reference operator*() const {
        Iter tmp = base;
        --tmp;
        return *tmp;
    }

    reverse_iter& operator++() {--base; return *this;}
};

Таким образом, если вы инициализируете такой объект reverse_iter<> с container.end(), базовый итератор будет указывать один за концом, но разыменование обратного итератора даст вам последний элемент. Никто не пострадал.

Ответ 2

Поскольку вам не разрешено разыменовывать итератор, который указывает за пределами контейнера, на самом деле не имеет значения, к чему указывает rend(). Это не должно быть легальным значением указателя, это может быть любое значение, которое имеет конкретное значение для типа контейнера/итератора.

Ответ 3

Результат rbegin указывает на то же, что и end (один за концом), а результат rend совпадает с begin (первый элемент). Когда обратный итератор разыменовывается, он возвращает ссылку на предыдущий элемент в диапазоне.

Ответ 4

Интерфейс std::reverse_iterator включает в себя функцию члена .base, которая возвращает итератор, равный оригиналу. Я подозреваю, что то, что они обычно делают, это просто кеш оригинального итератора и смещение на 1 в перегрузке оператора.

Ответ 5

Другие ответы хорошо отвечают на вопрос.

Но я также задаюсь вопросом, будет ли это законно в любом случае, поскольку, по-видимому, реализация может делать все, что ему нравится, за кулисами, пока это работает и соответствует стандартам. Если он хочет реализовать итератор в качестве указателя и выбирает разыменовывание, то тогда компиляторы должны знать, что это сработает. Вы бы не смогли реализовать его таким образом самостоятельно, но мне кажется, что у автора компилятора есть специальная лицензия, чтобы сделать это, поскольку они знают, каково поведение undefined, и не подвергайте это поведение вам напрямую, только через интерфейс итератора.