在 C++20 中，如何编写连续迭代器？

Question

C++20 具有对 std::contiguous_iterator_tag 的显式库支持。某些 STL 算法（例如 std::copy）可以在连续迭代器上执行得更好。但是，我不清楚 程序员 应该如何访问这个新功能。

让我们假设我们有一个完全符合 C++20 库的实现。我想编写最简单的连续迭代器。

#include <iterator>

class MyIterator {
    int *p_;
public:
    using value_type = int;
    using reference = int&;
    using pointer = int*;
    using difference_type = int;
    using iterator_category = std::contiguous_iterator_tag;
    int *operator->() const;
    int& operator*() const;
    int& operator[](int) const;
    MyIterator& operator++();
    MyIterator operator++(int);
    MyIterator& operator--();
    MyIterator operator--(int);
    MyIterator& operator+=(int);
    MyIterator& operator-=(int);
    friend auto operator<=>(MyIterator, MyIterator) = default;
    friend int operator-(MyIterator, MyIterator);
    friend MyIterator operator+(MyIterator, int);
    friend MyIterator operator-(MyIterator, int);
    friend MyIterator operator+(int, MyIterator);
};

namespace std {
    int *to_address(MyIterator it) {
        return it.operator->();
    }
}

static_assert(std::contiguous_iterator<MyIterator>);  // FAILS

这在 GCC/libstdc++ 和 MSVC/STL 上都失败了；但它应该吗？

为了我的下一次尝试，我专门研究了 pointer_traits<MyIterator>。 MyIterator 实际上不是指针，所以除了库需要的一个函数外，我没有在 pointer_traits 中放入任何东西。 This is my second attempt:

#include <iterator>

class MyIterator {
    ~~~
};

template<>
struct std::pointer_traits<MyIterator> {
    int *to_address(MyIterator it) {
        return it.operator->();
    }
};

static_assert(std::contiguous_iterator<MyIterator>);  // OK!

这就是我应该做的方式吗？感觉非常hacky。（需要说明的是：我的第一次失败尝试也感觉非常糟糕。）

我是不是漏掉了一些更简单的方法？

特别是，MyIterator 本身是否有任何方法可以保证它是连续的，只需使用可以在 class 正文中定义的成员和朋友以及其他内容？就像，如果 MyIterator 是在某个深度嵌套的命名空间中定义的，我不想为了打开 namespace std.

而一路突破到顶级命名空间

编辑添加：Glen Fernandes 告诉我是一种更简单的方法——我应该添加一个 element_type typedef，like this!（我可以删除 C++20 中的 iterator_traits' 大 5 typedef 中的 3 个。）这看起来更好！

#include <iterator>

class MyIterator {
    int *p_;
public:
    using value_type = int;
    using element_type = int;
    using iterator_category = std::contiguous_iterator_tag;
    int *operator->() const;
    int& operator*() const;
    int& operator[](int) const;
    MyIterator& operator++();
    MyIterator operator++(int);
    MyIterator& operator--();
    MyIterator operator--(int);
    MyIterator& operator+=(int);
    MyIterator& operator-=(int);
    friend auto operator<=>(MyIterator, MyIterator) = default;
    friend int operator-(MyIterator, MyIterator);
    friend MyIterator operator+(MyIterator, int);
    friend MyIterator operator-(MyIterator, int);
    friend MyIterator operator+(int, MyIterator);
};

static_assert(std::contiguous_iterator<MyIterator>);  // OK!

此外，我还看到了一些关于使用成员类型定义 iterator_concept 而不是 iterator_category 的内容。为什么我可能想要提供 MyIterator::iterator_concept？（我不是在这里要求完整的历史解释；只是一个简单的最佳实践指南“不忘记 iterator_concept”或“是的，提供它，因为它有助于 X”会很好。）

Answer 1

C++ 概念作为一种语言特性的主要好处之一是概念定义告诉您您需要提供什么。 std::contiguous_iterator is no different。是的，您可能需要深入研究 10 层以上的其他概念定义，才能深入了解您需要提供的基本术语。但是它们就在语言中。

也就是说，连续迭代器是随机访问迭代器：

谁的标签来自contiguous_iterator
其 reference_type 是对其 value_type 的左值引用（即：不是代理迭代器或生成器）。
为此，可以调用 standard library function std::to_address 将任何有效的迭代器（即使是不可取消引用的迭代器）转换为指向迭代器引用的元素或尾后一个指针的指针.

不幸的是，满足 #3 不能通过直接特化 std::to_address 来完成。你必须为你的迭代器类型使用 specialize pointer_traits::to_address 或者给你的迭代器一个 operator-> 重载。

后者更容易做到，尽管 operator-> 没有被 std::contiguous_iterator 要求，但对于这样的迭代器类型是有意义的：

class MyIterator
{
 ...
  int const *operator->() const;
};

仅供参考：如果您根据概念约束模板，而不是仅仅 static_assert 约束模板，大多数编译器会为您提供更有用的错误消息。像这样：

template<std::contiguous_iterator T>
void test(const T &t);

test(MyIterator{});

Answer 2

有两种支持方式std::to_address。一个是：

namespace std {

template<>
struct pointer_traits<I> {
    static X* to_address(const I& i) {
        // ...
    }
};

}

注意上面的static。

正如 Glen 向您指出的那样，第二种方法是简单地定义 I::operator-> 并确保 std::pointer_traits<I> 的主模板有效。这只需要 std::pointer_traits<I>::element_type 有效。

Nicol Bolas 的回答不正确，因为这不是您为用户定义类型定制 std::to_address 的方式。从 C++20 开始（因为 P0551），禁止在命名空间 std 中专门化函数模板，而您没有明确允许这样做。

您不能专攻std::to_address。不过，您可以提供 std::pointer_traits<I>::to_address，如果存在，std::to_address 将调用它。

Answer 3

我问题的最后一个版本似乎是最正确的。只有一点需要注意：

MyIterator::value_type 应该是 cv-unqualified 类型的指针，这样有人可以写 value_type x; x = *it;
MyIterator::element_type 应该是 cv-qualified 类型的指针，这样有人可以写 element_type *ptr = std::to_address(it);

所以对于 const 迭代器，element_type 不仅仅是 value_type 的同义词 — 它是 const value_type 的同义词！如果你不这样做，标准库中的东西就会爆炸。

Here's a Godbolt proof-of-concept. (It's not a complete ecosystem, in that really you'd want MyIterator to be implicitly convertible to MyConstIterator, and probably use templates to eliminate some of the repetition. I have a rambly blog post on that subject here.)

#include <iterator>

class MyIterator {
    int *p_;
public:
    using value_type = int;
    using element_type = int;
    using iterator_category = std::contiguous_iterator_tag;
    int *operator->() const;
    int& operator*() const;
    int& operator[](int) const;
    MyIterator& operator++();
    MyIterator operator++(int);
    MyIterator& operator--();
    MyIterator operator--(int);
    MyIterator& operator+=(int);
    MyIterator& operator-=(int);
    friend auto operator<=>(MyIterator, MyIterator) = default;
    friend int operator-(MyIterator, MyIterator);
    friend MyIterator operator+(MyIterator, int);
    friend MyIterator operator-(MyIterator, int);
    friend MyIterator operator+(int, MyIterator);
};

static_assert(std::contiguous_iterator<MyIterator>);  // OK!

class MyConstIterator {
    const int *p_;
public:
    using value_type = int;
    using element_type = const int;
    using iterator_category = std::contiguous_iterator_tag;
    const int *operator->() const;
    const int& operator*() const;
    const int& operator[](int) const;
    MyConstIterator& operator++();
    MyConstIterator operator++(int);
    MyConstIterator& operator--();
    MyConstIterator operator--(int);
    MyConstIterator& operator+=(int);
    MyConstIterator& operator-=(int);
    friend auto operator<=>(MyConstIterator, MyConstIterator) = default;
    friend int operator-(MyConstIterator, MyConstIterator);
    friend MyConstIterator operator+(MyConstIterator, int);
    friend MyConstIterator operator-(MyConstIterator, int);
    friend MyConstIterator operator+(int, MyConstIterator);
};

static_assert(std::contiguous_iterator<MyConstIterator>);  // OK!

在 C++20 中，如何编写连续迭代器？

In C++20, how do I write a contiguous iterator?

c++

stl

iterator

c++20

contiguous