На что указывает точка?

Question

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

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