为什么编写反向迭代器会影响迭代器是否为随机访问迭代器？

Question

我想写一个带有随机访问迭代器的容器：

#include <cstddef>
#include <iterator>
#include <concepts>

namespace foo
{
    struct container
    {
        struct iter
        {
            using difference_type = std::ptrdiff_t;
            using pointer = int*;
            using reference = int&;
            using value_type = int;
            using iterator_category = ::std::random_access_iterator_tag;

            iter& operator++();
            iter operator++(int);
            iter& operator--();
            iter operator--(int);

            iter operator+(difference_type) const;
            iter operator-(difference_type) const;
            iter& operator+=(difference_type);
            iter& operator-=(difference_type);
            bool operator==(const iter&) const;
            bool operator!=(const iter&) const;
            bool operator<(const iter&) const;
            bool operator>(const iter&) const;
            bool operator<=(const iter&) const;
            bool operator>=(const iter&) const;
            difference_type operator-(const iter&) const;

            int& operator*() const;
            int& operator[](difference_type) const;
        };

        // code for reverse iterator, now it is comment out

        /* using riter = std::reverse_iterator<iter>;

        iter end();
        riter rbegin()
        {
            return std::reverse_iterator(this->end());
        }
        */
    };

    inline container::iter operator+(container::iter::difference_type, const container::iter&);
}

int main(void)
{
    static_assert(std::random_access_iterator<foo::container::iter>, "");
    return 0;
}

然后我用g++-11 -std=c++20编译，可以编译成功

但是如果我想为这个容器写一个反向迭代器，也就是取消注释那些反向迭代器的代码，就会出现编译错误：

<source>:55:2: error: static_assert failed ""
        static_assert(std::random_access_iterator<foo::container::iter>, "");
        ^                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:55:21: note: because 'foo::container::iter' does not satisfy 'random_access_iterator'
        static_assert(std::random_access_iterator<foo::container::iter>, "");
                           ^
/opt/compiler-explorer/gcc-11.2.0/lib/gcc/x86_64-linux-gnu/11.2.0/../../../../include/c++/11.2.0/bits/iterator_concepts.h:669:8: note: because '__n + __j' would be invalid: invalid operands to binary expression ('const iter_difference_t<foo::container::iter>' (aka 'const long') and 'const foo::container::iter')
        { __n +  __j } -> same_as<_Iter>;
              ^
1 error generated.

我也使用 Clang 13，但得到了相同的结果。那么迭代器应该怎么写才正确呢？

Answer 1

仅仅因为您给迭代器一个 random_access_iterator_tag 类别并不能使它成为随机访问迭代器。

您必须提供所有操作。

编译器错误告诉您表达式 3 + iter_var 无效（其中 iter_var 是您的迭代器之一）。

Remy 提供的 link 列出了“必须工作”的操作。

Answer 2

这里的谜团是为什么添加几行代码 不改变 foo::container::iter 的定义会导致 static_assert 失败。

这是因为 std::reverse_iterator 的构造函数的实现在注释函数的主体中评估 concept std::random_access_iterator 以确定要创建哪种反向迭代器。

发生这种情况时，operator+(difference_type, iter) 尚未声明，因为 它在您的代码中更靠后 ，因此您的 container::iter 最初无法满足概念。

稍后，您声明所需的 operator+，如果不是标准的以下部分，您的类型现在将满足 concept std::random_access_iterator：[temp.constr.atomic]

... If, at different points in the program, the satisfaction result is different for identical atomic constraints and template arguments, the program is ill-formed, no diagnostic required.

在您的代码的不同点，concept std::random_access_iterator 有不同的满意结果！所以你的代码格式错误，不需要诊断。（GCC 确实诊断了这个 - clang 只是给你它第一次评估这个概念时的错误信息，这就是你感到困惑的原因）。

您可以通过在使用 std::reverse_iterator 之前移动您的 operator+ 声明来解决此问题。例如：

struct container {
    struct iter {
        // all your methods, as before
        
        friend iter operator+(difference_type, iter);
    }

    using riter = std::reverse_iterator<iter>;

    iter end();
    riter rbegin();
}

为什么编写反向迭代器会影响迭代器是否为随机访问迭代器？

Why writing reverse iterator can affect whether an iterator is random-access-iterator or not?

c++

iterator

stl