迭代器概念

  • 项目

概念是 C++20 的一项语言功能，可在编译时约束模板参数。 它们有助于防止模板实例化不正确，在可读表单中指定模板自变量要求，并提供更简洁的模板相关编译器错误。

请考虑以下示例，该示例定义了一个概念，用于防止使用不支持除法的类型实例化模板：

// requires /std:c++20 or later
#include <iostream>

// Definition of dividable concept which requires 
// that arguments a & b of type T support division
template <typename T>
concept dividable = requires (T a, T b)
{
    a / b;
};

// Apply the concept to a template.
// The template will only be instantiated if argument T supports division.
// This prevents the template from being instantiated with types that don't support division.
// This could have been applied to the parameter of a template function, but because
// most of the concepts in the <ranges> library are applied to classes, this form is demonstrated.
template <class T> requires dividable<T>
class DivideEmUp
{
public:
    T Divide(T x, T y)
    {
        return x / y;
    }
};

int main()
{
    DivideEmUp<int> dividerOfInts;
    std::cout << dividerOfInts.Divide(6, 3); // outputs 2
    // The following line will not compile because the template can't be instantiated 
    // with char* because char* can be divided
    DivideEmUp<char*> dividerOfCharPtrs; // compiler error: cannot deduce template arguments 
}

将编译器开关 /diagnostics:caret 传递给 Visual Studio 2022 版本 17.4 预览版 4 或更高版本时，概念 dividable<char*> 计算结果为 false 的错误将直接指向失败的表达式要求 (a / b)。

迭代器概念在命名空间 std 中定义，并在头文件 <iterator> 中声明。 它们用于范围适配器、视图等的声明。

迭代器有六种类别。 它们与范围概念下列出的范围类别直接相关。

以下迭代器概念按功能逐渐增强的顺序列出。 input_or_output_iterator 位于功能层次结构的最底部，contiguous_iterator 位于功能层次结构的最顶部。 层次结构中较高级别的迭代器通常可以代替较低级别的迭代器，但反之则不然。 例如，random_access_iterator 迭代器可以代替 forward_iterator 迭代器，但反之则不行。 例外情况是 input_iterator，由于它无法写入，因此无法由 output_iterator 代替。

迭代器层次结构的关系图。input_or_output_iterator是基础。input_iterator和output_iterator显示为炼油input_or_output_iterator。接下来forward_iterator并优化input_iterator和output_iterator。bidirectional_iterator优化forward_iterator。random_access_iterator优化bidirectional_iterator。最后，contiguous_iterator优化random_access_iterator

下表中，“多次遍历”是指迭代器是否可以多次重新访问同一元素。 例如，vector::iterator 是一个多次遍历迭代器，因为你可以创建迭代器的副本，读取集合中的元素，然后将迭代器还原到副本中的值，并再次重新访问相同的元素。 如果迭代器是单次遍历迭代器，则只能访问集合中的元素一次。

下表中，“示例类型”是指满足概念的集合/迭代器。

迭代器概念 说明 方向 读/写 多次遍历 示例类型
input_or_output_iteratorC++20 迭代器概念分类的基础。 前进 读/写 否 istream_iterator, ostream_iterator
output_iteratorC++20 指定可以写入的迭代器。 前进 写入 否 ostream, inserter
input_iteratorC++20 指定可以进行一次读取的迭代器。 前进 阅读 否 istream, istreambuf_iterator
forward_iteratorC++20 指定可以进行多次读取（可能可以写入）的迭代器。 前进 读/写 是 vector, list
bidirectional_iteratorC++20 指定可以向前和向后读取和写入的迭代器。 正向或反向 读/写 是 list、set、multiset、map 和 multimap。
random_access_iteratorC++20 指定可以按索引读取和写入的迭代器。 正向或反向 读/写 是 vector、 array、、 deque
contiguous_iteratorC++20 指定一个迭代器，其元素在内存中按顺序排列，大小相同，并且可以使用指针算术进行访问。 正向或反向 读/写 是 array， vector string.

其他迭代器概念包括：

迭代器概念 说明
sentinel_forC++20 指定类型是迭代器类型的 sentinel。
sized_sentinel_forC++20 指定迭代器及其 sentinel 可以相减（使用 -），以查找其常量时间方面的差异。

bidirectional_iterator

bidirectional_iterator 支持向前和向后读取和写入。

template<class I>
concept bidirectional_iterator =
    forward_iterator<I> &&
    derived_from<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
    requires(I i) {
        {--i} -> same_as<I&>;
        {i--} -> same_as<I>;
};

参数

I
要测试以了解它是否为 bidirectional_iterator 的迭代器。

备注

bidirectional_iterator 具有 forward_iterator 功能，但也可以向后循环访问。

可与 bidirectional_iterator 一起使用的一些容器示例包括 set、multiset、map、multimap、vector 和 list。

示例： bidirectional_iterator

以下示例使用 bidirectional_iterator 概念以表明 vector<int> 具有 bidirectional_iterator：

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    std::cout << std::boolalpha << std::bidirectional_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::contiguous_iterator<decltype(v)::iterator>; // outputs true
}

contiguous_iterator

指定一个迭代器，其元素在内存中按顺序排列，大小相同，并且可以使用指针算术进行访问。

template<class I>
    concept contiguous_iterator =
        random_access_iterator<I> &&
        derived_from<ITER_CONCEPT(I), contiguous_iterator_tag> &&
        is_lvalue_reference_v<iter_reference_t<I>> &&
        same_as<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&
        requires(const I& i) {
            { to_address(i) } -> same_as<add_pointer_t<iter_reference_t<I>>>;
        };

参数

I
要测试以了解它是否为 contiguous_iterator 的类型。

备注

可以通过指针算术来访问 contiguous_iterator，因为元素按顺序在内存中排列并且大小相同。 contiguous_iterator 的一些示例包括 array、vector 和 string。

示例： contiguous_iterator

以下示例使用 contiguous_iterator 概念以表明 vector<int> 具有 contiguous_iterator：

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector<int> has a contiguous_iterator
    std::cout << std::boolalpha << std::contiguous_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"
    
    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::contiguous_iterator<decltype(v)::iterator>; // outputs true
}

forward_iterator

具有 input_iterator 和 output_iterator 的功能。 支持对集合进行多次迭代。

template<class I>
    concept forward_iterator =
        input_iterator<I> &&
        derived_from<ITER_CONCEPT(I), forward_iterator_tag> &&
        incrementable<I> &&
        sentinel_for<I, I>;

参数

I
要测试以了解它是否为 forward_iterator 的迭代器。

备注

forward_iterator 只能向前移动。

可与 forward_iterator 一起使用的一些容器示例包括 vector、list、unordered_set、unordered_multiset、unordered_map 和 unordered_multimap。

示例： forward_iterator

以下示例使用 forward_iterator 概念以表明 vector<int> 具有 forward_iterator：

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector has a forward_iterator
    std::cout << std::boolalpha << std::forward_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::forward_iterator<decltype(v)::iterator>; // outputs true
}

input_iterator

input_iterator 是至少可以进行一次读取的迭代器。

template<class I>
concept input_iterator =
    input_or_output_iterator<I> &&
    indirectly_readable<I> &&
    requires { typename ITER_CONCEPT(I); } &&
    derived_from<ITER_CONCEPT(I), input_iterator_tag>;

参数

I
要测试以了解它是否为 input_iterator 的类型。

注解

对 input_iterator 多次调用 begin() 会导致未定义的行为。 仅对 input_iterator 建模的类型不是多次遍历。 例如，请考虑从标准输入 (cin) 读取。 在这种情况下，只能读取当前元素一次，并且无法重新读取已读取过的字符。 input_iterator 只能向前读取，无法向后读取。

示例： input_iterator

以下示例使用 input_iterator 概念以表明 istream_iterator 具有 input_iterator：

// requires /std:c++20 or later
#include <iostream>

int main()
{
    // Show that a istream_iterator has an input_iterator
    std::cout << std::boolalpha << std::input_iterator<std::istream_iterator<int>>; // outputs true
}

input_or_output_iterator

input_or_output_iterator 是迭代器概念分类的基础。 它支持取消引用和递增迭代器。 每个迭代器对 input_or_output_iterator 建模。

template<class I>
concept input_or_output_iterator =
    requires(I i) {
        { *i } -> can-reference;
    } &&
    weakly_incrementable<I>;

参数

I
要测试以了解它是否为 input_or_output_iterator 的类型。

备注

概念 can-reference 意味着类型 I 是引用、指针或可隐式转换为引用的类型。

示例： input_or_output_iterator

以下示例使用 input_or_output_iterator 概念以表明 vector<int> 具有 input_or_output_iterator：

// requires /std:c++20 or later
#include <iostream>

int main()
{
    // Show that a vector has an input_or_output_iterator
    std::cout << std::boolalpha << std::input_or_output_iterator<std::vector<int>::iterator> << '\n'; // outputs true

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::input_or_output_iterator<decltype(v)::iterator>; // outputs true
}

output_iterator

output_iterator 是可以写入的迭代器。

template<class I, class T>
concept output_iterator =
    input_or_output_iterator<I> &&
    indirectly_writable<I, T> &&
    requires(I i, T&& t) {
        *i++ = std::forward<T>(t);
    };

参数

I
要测试以了解它是否为 output_iterator 的类型。

T
要写入的值的类型。

注解

output_iterator 是单次遍历。 也就是说，它只能写入同一元素一次。

示例： output_iterator

以下示例使用 output_iterator 概念以表明 vector<int> 具有 output_iterator：

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector<int> has an output_iterator
    std::cout << std::boolalpha << std::output_iterator<std::vector<int>::iterator, int> << "\n"; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2,3,4,5};
    std::cout << std::boolalpha << std::output_iterator<decltype(v)::iterator, int>; // outputs true
}

random_access_iterator

random_access_iterator 可以按索引读取或写入。

template<class I>
concept random_access_iterator =
    bidirectional_iterator<I> &&
    derived_from<ITER_CONCEPT(I), random_access_iterator_tag> &&
    totally_ordered<I> &&
    sized_sentinel_for<I, I> &&
    requires(I i, const I j, const iter_difference_t<I> n) {
        { i += n } -> same_as<I&>;
        { j + n } -> same_as<I>;
        { n + j } -> same_as<I>;
        { i -= n } -> same_as<I&>;
        { j - n } -> same_as<I>;
        { j[n] } -> same_as<iter_reference_t<I>>;
    };

参数

I
要测试以了解它是否为 random_access_iterator 的类型。

备注

random_access_iterator 具有 input_iterator、output_iterator、forward_iterator和 bidirectional_iterator 功能。

random_access_iterator 的一些示例包括 vector、array 和 deque。

示例： random_access_iterator

以下示例显示 vector<int> 具有 random_access_iterator：

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector<int> has a random_access_iterator
    std::cout << std::boolalpha << std::random_access_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::random_access_iterator<decltype(v)::iterator>; // outputs true
}

sentinel_for

指定类型是迭代器的 sentinel。

template<class S, class I>
concept sentinel_for =
    semiregular<S> &&
    input_or_output_iterator<I> &&
    weakly-equality-comparable-with <S, I>;

参数

I
迭代器类型。

S
要测试以了解它是否为 I 的 sentinel 的类型。

备注

Sentinel 是一种类型，可以与迭代器进行比较，以确定迭代器是否已到达末尾。 此概念确定类型是否是 input_or_output_iterator 类型（其中包括 input_iterator、output_iterator、forward_iterator、bidirectional_iterator、random_access_iterator 和 contiguous_iterator）之一的 sentinel。

示例： sentinel_for

以下示例使用 sentinel_for 概念以表明 vector<int>::iterator 是 vector<int> 的 sentinel：

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {0, 1, 2};
    std::vector<int>::iterator i = v.begin();
    // show that vector<int>::iterator is a sentinel for vector<int>
    std::cout << std::boolalpha << std::sentinel_for<std::vector<int>::iterator, decltype(i)>; // outputs true
}

sized_sentinel_for

测试迭代器及其 sentinel 是否可以相减（使用 -），以查找其常量时间方面的差异。

template<class S, class I>
concept sized_sentinel_for =
    sentinel_for<S, I> &&
    !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> &&
    requires(const I& i, const S& s) {
        {s - i} -> same_as<iter_difference_t<I>>;
        {i - s} -> same_as<iter_difference_t<I>>;
    };

参数

I
迭代器类型。

S
要测试的 sentinel 类型。

备注

示例： sized_sentinel_for

以下示例使用 sized_sentinel_for 概念来验证是否可以从常量时间的向量迭代器中减去 vector<int> 的 sentinel：

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 3 };
    std::vector<int>::iterator i = v.begin();
    std::vector<int>::iterator end = v.end();
    // use the sized_sentinel_for concept to verify that i can be subtracted from end in constant time
    std::cout << std::boolalpha << std::sized_sentinel_for<decltype(end), decltype(i)> << "\n"; // outputs true
    std::cout << end - i; // outputs 3
}

另请参阅

范围概念
范围适配器
视图类