rend指向哪里？

Question

为了支持 STL 的半开范围概念，我们可以指向数组的末尾一位。假设我们有一个包含三个元素的向量。如果 std::vector::iterator 实现为指针（发布版本中通常是这种情况），则 begin 和 end 指向这些位置：

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

其中的点表示最后一个伪元素。既然不存在“一开始之前的事”这样的东西，那么 rend 到底会指向哪里呢？让我举例说明：

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

显然，这个说明是错误的，因为 rend 是一个非法指针。所以我猜想 std::vector::reverse_iterator 的实现永远不可能是指针，即使在发布版本中也是如此。

我说得对吗？那么实现reverse_iterator最有效的方法是什么？

Answer 1

rbegin 的结果指向与 end 相同（超过末尾），rend 的结果指向与 相同开始（第一项）。当反向迭代器被取消引用时，它返回对范围中前一项的引用。

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;}
};

因此，如果您使用 container.end() 初始化这样一个 reverse_iter<> 对象，则基本迭代器指向末尾的一个，但取消引用反向迭代器会给你最后一个元素。没有造成任何伤害。

Answer 4

std::reverse_iterator 接口包含一个 .base 成员函数，用于检索等于原始迭代器的迭代器。我怀疑他们通常做的只是缓存原始迭代器，并在operator*重载中偏移1。

Answer 5

其他答案很好地回答了这个问题。

但我也想知道这是否合法，因为只要它有效并符合标准，实现就可以在幕后做任何它喜欢的事情。如果它选择将迭代器实现为指针并选择取消引用，那么编译器有责任知道这将起作用。您自己无法以这种方式实现它，但在我看来，编译器作者拥有执行此操作的特殊许可，因为他们知道未定义的行为是什么，并且不会直接向您公开该行为，只需通过迭代器接口。