命名空间
变体
操作

std::random_access_iterator

来自 cppreference.com
< cpp‎ | iterator
 
 
迭代器库
迭代器概念
random_access_iterator
(C++20)


迭代器原语
算法概念和实用程序
间接可调用概念
通用算法要求
(C++20)
(C++20)
(C++20)
实用程序
(C++20)
迭代器适配器
范围访问
(C++11)(C++14)
(C++14)(C++14)  
(C++11)(C++14)
(C++14)(C++14)  
(C++17)(C++20)
(C++17)
(C++17)
 
定义在头文件 <iterator>
template< class I >

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

        };
(自 C++20 起)

random_access_iterator 概念通过添加对使用 +=+-=- 运算符进行常数时间推进的支持、使用 - 进行常数时间距离计算以及使用下标 [] 进行数组表示法来改进 bidirectional_iterator

内容

[编辑] 迭代器概念确定

此概念的定义是通过一个仅供说明的别名模板 /*ITER_CONCEPT*/ 指定的。

为了确定 /*ITER_CONCEPT*/<I>,让 ITER_TRAITS<I> 表示 I 如果特化 std::iterator_traits<I> 是从主模板生成的,否则表示 std::iterator_traits<I>

  • 如果 ITER_TRAITS<I>::iterator_concept 有效并且命名了一个类型,则 /*ITER_CONCEPT*/<I> 表示该类型。
  • 否则,如果 ITER_TRAITS<I>::iterator_category 有效并且命名了一个类型,则 /*ITER_CONCEPT*/<I> 表示该类型。
  • 否则,如果 std::iterator_traits<I> 是从主模板生成的,则 /*ITER_CONCEPT*/<I> 表示 std::random_access_iterator_tag
  • 否则,/*ITER_CONCEPT*/<I> 不表示任何类型,并导致替换失败。

[编辑] 语义要求

ab 是类型为 I 的有效迭代器,使得 b 可从 a 访问,并设 n 是类型为 std::iter_difference_t<I> 的值,等于 b - astd::random_access_iterator<I> 仅在它包含的所有概念都建模时才建模,并且

  • (a += n) 等于 b.
  • std::addressof(a += n) 等于 std::addressof(a)[1]
  • (a + n) 等于 (a += n).
  • (a + n) 等于 (n + a).
  • 对于任何两个正整数 xy,如果 a + (x + y) 有效,则 a + (x + y) 等于 (a + x) + y.
  • a + 0 等于 a.
  • 如果 (a + (n - 1)) 有效,则 --b 等于 (a + (n - 1)).
  • (b += -n)(b -= n) 都等于 a.
  • std::addressof(b -= n) 等于 std::addressof(b)[1]
  • (b - n) 等于 (b -= n).
  • 如果 b 可解引用,则 a[n] 有效,且等于 *b.
  • bool(a <= b)true.
  • 每个必需的操作都具有恒定时间复杂度。

注意 std::addressof 返回的是迭代器对象的地址,而不是迭代器指向的对象的地址。即 operator+=operator-= 必须返回对 *this 的引用。

[编辑] 相等性保持

在标准库概念的 requires 表达式 中声明的表达式必须是 相等性保持 的(除非另有说明)。

[编辑] 隐式表达式变体

使用对某些常量左值操作数非修改的表达式的 requires 表达式 也要求 隐式表达式变体

[编辑] 备注

LegacyRandomAccessIterator 要求不同,random_access_iterator 概念不要求解引用返回左值。

[编辑] 示例

演示了通过 C++20 概念实现 std::distance 的一种可能方式。

#include <iterator>
 
namespace cxx20
{
    template<std::input_or_output_iterator Iter>
    constexpr std::iter_difference_t<Iter> distance(Iter first, Iter last)
    {
        if constexpr(std::random_access_iterator<Iter>)
            return last - first;
        else
        {
            std::iter_difference_t<Iter> result{};
            for (; first != last; ++first)
                ++result;
            return result;
        }
    }
}
 
int main()
{
    static constexpr auto il = {3, 1, 4};
 
    static_assert(std::random_access_iterator<decltype(il.begin())> &&
                  cxx20::distance(il.begin(), il.end()) == 3 &&
                  cxx20::distance(il.end(), il.begin()) == -3);
}

[编辑] 参见

指定 forward_iterator 是一个双向迭代器,支持向后移动
(概念) [编辑]
指定 random_access_iterator 是一个连续迭代器,引用内存中连续的元素
(概念) [编辑]