На что указывает раздирание?

Question

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

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

Где точки обозначают одно прошедшееконец псевдоэлемента.Поскольку не существует понятия «один до начала», на что именно указывает rend?Позвольте мне проиллюстрировать:

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

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

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

Answer 1

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

Answer 2

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

Answer 3

Существует разница между тем, на что логически указывает 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(), базовый итератор будет указывать на один конец, но разыменование обратного итератора даст вам последний элемент.Никакого вреда не сделано.

Answer 4

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

Answer 5

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

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