一个随机访问迭代器的实现

博客园 - 木木ちゃん

无用的知识之：C语言中的 `struct` 的内存大小讨论 Lab 1: Utilities Lab 0: 准备工作 Chapter 1: Operating system interfaces 操作系统接口线性注意力机制学习笔记关于二分查找的简单思考 DWDP: 在NVL72上的高性能分布式权重数据并行 NCCL EP 论文解读 Megatron-LM-Moe 论文阅读笔记 (ISCA 2025) Chimera: Communication Fusion for Hybrid Parallelism in Large Language Models (Sigcomm'25) Stellar: 阿里新一代云AI RDMA网络 deepseek-v3.2-exp: 节前发版之打工人的悲鸣关于Leetcode 812题的简单思考减少KVCache tuple hash: 尝试在set/map中使用tuple google_test Linux相关配置+双系统安装记录 SkipList Conga：分布式拥塞感知与负载均衡数据中心(Sigcomm'14) Megatron-LM Efficient AI training system MiniOB Lab4: join tables & group by MiniOB Lab3 布隆过滤器：原理与leveldb中的实现第三章 SQL入门

一个随机访问迭代器的实现

木木ちゃん · 2026-09-19 · via 博客园 - 木木ちゃん

无用的知识：随机访问迭代器的实现

起因是刷Leetcode的时候发现了一道题目：1329. 将矩阵按对角线排序。正常的做法是很自然地开一个辅助 vector：

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        for (int k = 1; k < m + n; k++) {
            int min_j = std::max(0, n - k);
            int max_j = std::min(m + n - k, n);
            std::vector<int> tmp;
            tmp.reserve(max_j - min_j);
            for (int j = min_j; j < max_j; j++) {
                tmp.push_back(mat[j + k - n][j]);
            }
            std::ranges::sort(tmp);
            for (int j = min_j, l = 0; j < max_j; j++, l++) {
                mat[j + k - n][j] = tmp[l];
            }
        }
        return mat;
    }
};

但是突然想到：std::ranges::sort 是原地排序的。我们是否可以直接对 mat 的对角线进行原地排序呢？答案是可以的。这里我们就需要使用到 RandomAccessIterator 的自定义实现：利用它来实现一个对对角线的直接排序。这里我们需要用到：

Range 的实现
Iterator，尤其是 RandomAccessIterator 的实现
理解不同 Iterator 的 Constraints

`std::ranges::sort`

首先我们先了解 std::ranges::sort 函数。函数的定义如 cpp/algorithm/ranges/sort 中所示：

// Since C++20
template< ranges::random_access_range R, class Comp = ranges::less,
          class Proj = std::identity >
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
    sort( R&& r, Comp comp = {}, Proj proj = {} );

为了能够使用这个函数，我们就需要：

一个 ranges::random_access_range；
一个 ranges::random_access_iterator；
这个 ranges::random_access_iterator 满足 std::sortable constraint:
- 需要能够执行比较；
- 需要能够进行交换；
- （为了理解方便，上述的描述并不严谨，具体的请自行查看 std::sortable 的 concept 定义）

那么接下来我们就了解 random_access_* 相关的要求。

`random_access_*`

`random_access_iterator`

对于 random_access_iterator，我们需要自上而下地满足：

random_access_iterator
- bidirectional_iterator + 推导出 random_access_iterator_tag + totally_ordered + sized_sentinel_for + 一大串 requires 子句(1)
  - forward_iterator + 推导出 bidrectional_iterator_tag + 前缀--与后缀-- requires 子句(2)
    - input_iterator + 推导出 forward_iterator_tag + incrementable + sentinel_for
      - input_or_output_iterator + indirectly_readable(可以解引用读出来，不严谨地说) + 推导出 input_iterator_tag

那么我们就尝试去一层一层地实现这个 random_access_iterator。

实现 iterator 原型

首先我们需要先满足 iterator 的模板，使得它最终能推导出正确的tag。我们有：

template<class Category, class T, class Distance = ptrdiff_t,
           class Pointer = T*, class Reference = T&>
  struct iterator {
    typedef Category  iterator_category;
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
  };

这样对于一个迭代器，我们首先要做到的是定义 iterator_category（也就是 tag），value_type，difference_type，pointer，reference。这样才能被类型系统正确地识别。我们有：

template <typename T>
class MatRandomAccessIterator {
public:
  // First, We manage some template parameters.
  using iterator_category = std::random_access_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T &;
};

实际上我们在此处只需要 using value_type = T; 和 using difference_type = std::ptrdiff_t; 来满足一些 concept 的要求。iterator_category 也需要显式给出，或通过特化 iterator_traits 提供；pointer、reference 在 C++20 下有些情况下可以推导得出。

实现 input_iterator 原型

template< class I >
    concept input_iterator =
        std::input_or_output_iterator<I> &&
        std::indirectly_readable<I> &&
        requires { typename /*ITER_CONCEPT*/<I>; } &&
        std::derived_from</*ITER_CONCEPT*/<I>, std::input_iterator_tag>;

接着我们需要实现 input_iterator 的原型。对于它，通过分析 concept，我们需要：

满足 iterator concept；
iterator_category 属于 input_iterator_tag；
indirectly_readable<I> 要求能够解引用，要求 *in 的值、引用与const 限定有效。
- 这里可以通过看 requires 子句中函数的参数要求。参数有 const 时，成员函数必须要有 const 限定符。
input_or_output_iterator 要求实现 weakly_incrementable，同时要求实现 difference_type：
- 前缀自增要求返回 T&。后缀自增不要求返回类型。
- 前后缀自增自减必须通过函数参数（防止重载决议二义性）来区分。前缀自增/自减返回 T&，没有参数。后缀自增/自减返回 T，参数为 int。

我们可以通过 static_assert(std::input_iterator<MatInputIterator<int>>) 来查看我们是否正确实现了一个 input_iterator。接下来我们需要实现具体的行为。对于一个二维矩阵的iterator，解引用时应该返回 value_type，也就是二维的一个值。这样我们就需要：

一个指向二维 vector 的指针；
坐标 (i,j) 来取出对应的值。

对于自增函数，我们直接同时增加 (i,j) 即可。我们进一步补充完善后如下：

template <typename T>
class MatInputIterator {
public:
  // First, We manage some template parameters.
  using iterator_category = std::input_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T &;

  value_type operator*() const {
    return (*_mat)[_i][_j];
  }
  MatInputIterator& operator++() {
    ++_i;
    ++_j;
    return *this;
  }
  void operator++(int);

private:
  std::vector<std::vector<T>> *_mat = nullptr;
  int _i = 0;
  int _j = 0;
};

实现 forward_iterator

template< class I >
    concept forward_iterator =
        std::input_iterator<I> &&
        std::derived_from</*ITER_CONCEPT*/<I>, std::forward_iterator_tag> &&
        std::incrementable<I> &&
        std::sentinel_for<I, I>;

forward_iterator 在 input_iterator 之上进一步要求了 std::incrementable<I> 和 std::sentinel_for<I, I>。简单来说：

前者强化了后缀自增，要求返回的类型为 I。
后者要求实现 == 重载。也就是所说的 (I == I) 和 (I != I) well defined. 注意参数都是 const 限定的。
- 但是C++20在重载了operator==后会自动覆写operator!=。

考虑到后缀自增，我们有：

template <typename T>
class MatForwardIterator {
public:
  // First, We manage some template parameters.
  using iterator_category = std::forward_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T &;

  value_type operator*() const {
    return (*_mat)[_i][_j];
  }
  MatForwardIterator& operator++() {
    ++_i;
    ++_j;
    return *this;
  }

  MatForwardIterator operator++(int) {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  // bool operator==(const MatForwardIterator &other) const;
  // Or we can use friend:
  friend bool operator==(const MatForwardIterator &a, const MatForwardIterator &b) {
    return a._i == b._i;
  }

private:
  std::vector<std::vector<T>> *_mat = nullptr;
  int _i = 0;
  int _j = 0;
};

实现 bidirectional_iterator

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

也就是要求实现前后缀自减。这个很容易。

template <typename T>
class MatBiDirectionalIterator {
public:
  // First, We manage some template parameters.
  using iterator_category = std::bidirectional_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T &;

  value_type operator*() const {
    return (*_mat)[_i][_j];
  }
  MatBiDirectionalIterator& operator++() {
    ++_i;
    ++_j;
    return *this;
  }

  MatBiDirectionalIterator operator++(int) {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  // Or we can use member:
  // bool operator==(const MatBiDirectionalIterator &other) const;
  friend bool operator==(const MatBiDirectionalIterator &a, const MatBiDirectionalIterator &b) {
    return a._i == b._i;
  }

  MatBiDirectionalIterator& operator--() {
    --_i;
    --_j;
    return *this;
  }

  MatBiDirectionalIterator operator--(int) {
    auto tmp = *this;
    --(*this);
    return tmp;
  }

private:
  std::vector<std::vector<T>> *_mat = nullptr;
  int _i = 0;
  int _j = 0;
};

实现 random_access_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>>;
        };

首先是 totally_ordered<I>。他要求我们需要有对 ==,!=,<,>,<=,>= 函数的重载。
接着是 sized_sentinel_for<I, I>。他要求我们有 std::sentinel_for<I, I>（也就是 I==I，I!=I，两者皆为 const 定义），以及要求我们定义两个I类型的对象相减，得到一个 iterator 的 difference_type。
最后要求分别实现 +=, +, -=, -, [] 重载，要求返回 I&, I, I, I&, I, 与operator*()完全相同的返回类型。

因此我们至少需要实现 <=>，==，+=, +, -=, -（两种不同的）, []（必须是成员函数）。

template <typename T>
class MatRandomAccessIterator {
public:
  // First, We manage some template parameters.
  using iterator_category = std::random_access_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T &;

  // meet the requirements of input_iterator.
  value_type operator*() const {
    return (*_mat)[_i][_j];
  }

  MatRandomAccessIterator& operator++() {
    ++_i;
    ++_j;
    return *this;
  }

  // meet the requirements of forward_iterator.
  MatRandomAccessIterator operator++(int) {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }

  // Or we can use member:
  // bool operator==(const MatRandomAccessIterator &other) const;
  friend bool operator==(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    return a._i == b._i;
  }

  // meet the requirements of bidirectional_iterator.
  MatRandomAccessIterator& operator--() {
    --_i;
    --_j;
    return *this;
  }

  MatRandomAccessIterator operator--(int) {
    auto tmp = *this;
    --(*this);
    return tmp;
  }
  
  // Meet the requirements of random_access_iterator.
  friend auto operator<=>(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    // Only need one since _i and _j are changing simultaneously on a diagnol.
    return a._i <=> b._i;
  }

  friend difference_type operator-(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    return a._i - b._i;
  }

  friend MatRandomAccessIterator& operator+=(MatRandomAccessIterator &a, const difference_type n) {
    a._i += n;
    a._j += n;
    return a;
  }

  friend MatRandomAccessIterator operator+(const MatRandomAccessIterator &a, const difference_type n) {
    return MatRandomAccessIterator(a._mat, a._i + n, a._j + n);
  }

  friend MatRandomAccessIterator operator+(const difference_type n, const MatRandomAccessIterator &a) {
    return MatRandomAccessIterator(a._mat, a._i + n, a._j + n);
  }

  friend MatRandomAccessIterator& operator-=(MatRandomAccessIterator &a, const difference_type n) {
    a._i -= n;
    a._j -= n;
    return a;
  }

  friend MatRandomAccessIterator operator-(const MatRandomAccessIterator &a, const difference_type n) {
    return MatRandomAccessIterator(a._mat, a._i - n, a._j - n);
  }

  value_type operator[](const difference_type n) const {
    return (*_mat)[_i + n][_j + n];
  }

private:
  std::vector<std::vector<T>> *_mat = nullptr;
  int _i = 0;
  int _j = 0;
};

这样我们就实现了一个合理的 random_access_iterator，编译期 static_assert(std::random_access_iterator<MatRandomAccessIterator<int>>) 不会报错。

`random_access_range`

template< class T >
concept random_access_range =
    ranges::bidirectional_range<T> && std::random_access_iterator<ranges::iterator_t<T>>;

接着我们需要实现一个 random_access_range。为了方便起见，我们直接使用 ranges::begin() 和 ranges::end() 都具有相同的类型。这样根据要求，我们就需要 begin() 和 end() 都返回 random_access_iterator。这样我们有：

template <typename T>
class DiagnolRange {
public:
  using iterator = MatRandomAccessIterator<T>;
  iterator begin();
  iterator end();
};

在编译期是通过的。进一步我们将对角线遍历的算法放进去，每一个对角线 k 作为一个range。实现的算法细节此处忽略。这样我们需要增加一个 MatRandomAccessIterator 的初始化函数。同时，为了进一步满足 random_access_iterator 中，semi_regular 要求 default_initializable，因此需要再显式声明一个默认构造函数。因此我们有：

template <typename T>
class MatRandomAccessIterator {
public:
  // First, We manage some template parameters.
  using iterator_category = std::random_access_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T &;

  // The constructor with default constructor to meet semiregular.
  using mat = std::vector<std::vector<T>>;
  MatRandomAccessIterator() = default;
  explicit MatRandomAccessIterator(mat *mat, int i, int j): _mat(mat), _i(i), _j(j) {}

  value_type operator*() const {
    return (*_mat)[_i][_j];
  }

  MatRandomAccessIterator& operator++() {
    ++_i;
    ++_j;
    return *this;
  }

  MatRandomAccessIterator operator++(int) {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  // Or we can use member:
  // bool operator==(const MatRandomAccessIterator &other) const;
  friend bool operator==(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    return a._i == b._i;
  }

  MatRandomAccessIterator& operator--() {
    --_i;
    --_j;
    return *this;
  }

  MatRandomAccessIterator operator--(int) {
    auto tmp = *this;
    --(*this);
    return tmp;
  }

  friend auto operator<=>(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    // Only need one since _i and _j are changing simultaneously on a diagnol.
    return a._i <=> b._i;
  }

  friend difference_type operator-(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    return a._i - b._i;
  }

  friend MatRandomAccessIterator& operator+=(MatRandomAccessIterator &a, const difference_type n) {
    a._i += n;
    a._j += n;
    return a;
  }

  friend MatRandomAccessIterator operator+(const MatRandomAccessIterator &a, const difference_type n) {
    return MatRandomAccessIterator(a._mat, a._i + n, a._j + n);
  }

  friend MatRandomAccessIterator operator+(const difference_type n, const MatRandomAccessIterator &a) {
    return MatRandomAccessIterator(a._mat, a._i + n, a._j + n);
  }

  friend MatRandomAccessIterator& operator-=(MatRandomAccessIterator &a, const difference_type n) {
    a._i -= n;
    a._j -= n;
    return a;
  }

  friend MatRandomAccessIterator operator-(const MatRandomAccessIterator &a, const difference_type n) {
    return MatRandomAccessIterator(a._mat, a._i - n, a._j - n);
  }

  value_type operator[](const difference_type n) const {
    return (*_mat)[_i + n][_j + n];
  }

private:
  std::vector<std::vector<T>> *_mat = nullptr;
  int _i = 0;
  int _j = 0;
};

template <typename T>
class DiagnolRange {
public:
  using Iterator = MatRandomAccessIterator<T>;

  DiagnolRange(std::vector<std::vector<T>> &mat, int k) : _mat(&mat) {
    int m = mat.size();
    int n = mat[0].size();

    _start_j = std::max(0, n - k);
    _end_j = std::min(m + n - k, n);
    _start_i = _start_j + k - n;
    _end_i = _end_j + k - n;
  }

  // Define the begin and the end.
  Iterator begin() {
    return Iterator(_mat, _start_i, _start_j);
  }
  Iterator end() {
    return Iterator(_mat, _end_i, _end_j);
  }

private:
  std::vector<std::vector<T>> *_mat;
  int _start_j;
  int _end_j;
  int _start_i;
  int _end_i;
};

这样符合对角线的random_access_range就成功造出来了。

`std::sortable`

最后，我们需要满足 std::sortable，也就意味着我们需要满足原地交换的功能。因此我们的 operator* 和 operator[] 就不能返回 value_type，而必须是 reference。因此我们有：

template <typename T>
class MatRandomAccessIterator {
public:
  // First, We manage some template parameters.
  using iterator_category = std::random_access_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T &;

  // Unnecessary helper types.
  using mat = std::vector<std::vector<T>>;

  MatRandomAccessIterator() = default;
  explicit MatRandomAccessIterator(mat *mat, int i, int j): _mat(mat), _i(i), _j(j) {}

  reference operator*() const {
    return (*_mat)[_i][_j];
  }

  MatRandomAccessIterator& operator++() {
    ++_i;
    ++_j;
    return *this;
  }

  MatRandomAccessIterator operator++(int) {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  // Or we can use member:
  // bool operator==(const MatRandomAccessIterator &other) const;
  friend bool operator==(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    return a._i == b._i;
  }

  MatRandomAccessIterator& operator--() {
    --_i;
    --_j;
    return *this;
  }

  MatRandomAccessIterator operator--(int) {
    auto tmp = *this;
    --(*this);
    return tmp;
  }

  friend auto operator<=>(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    // Only need one since _i and _j are changing simultaneously on a diagnol.
    return a._i <=> b._i;
  }

  friend difference_type operator-(const MatRandomAccessIterator &a, const MatRandomAccessIterator &b) {
    return a._i - b._i;
  }

  friend MatRandomAccessIterator& operator+=(MatRandomAccessIterator &a, const difference_type n) {
    a._i += n;
    a._j += n;
    return a;
  }

  friend MatRandomAccessIterator operator+(const MatRandomAccessIterator &a, const difference_type n) {
    return MatRandomAccessIterator(a._mat, a._i + n, a._j + n);
  }

  friend MatRandomAccessIterator operator+(const difference_type n, const MatRandomAccessIterator &a) {
    return MatRandomAccessIterator(a._mat, a._i + n, a._j + n);
  }

  friend MatRandomAccessIterator& operator-=(MatRandomAccessIterator &a, const difference_type n) {
    a._i -= n;
    a._j -= n;
    return a;
  }

  friend MatRandomAccessIterator operator-(const MatRandomAccessIterator &a, const difference_type n) {
    return MatRandomAccessIterator(a._mat, a._i - n, a._j - n);
  }

  reference operator[](const difference_type n) const {
    return (*_mat)[_i + n][_j + n];
  }

private:
  std::vector<std::vector<T>> *_mat = nullptr;
  int _i = 0;
  int _j = 0;
};

template <typename T>
class DiagnolRange {
public:
  using Iterator = MatRandomAccessIterator<T>;

  DiagnolRange(std::vector<std::vector<T>> &mat, int k) : _mat(&mat) {
    int m = mat.size();
    int n = mat[0].size();

    _start_j = std::max(0, n - k);
    _end_j = std::min(m + n - k, n);
    _start_i = _start_j + k - n;
    _end_i = _end_j + k - n;
  }

  // Define the begin and the end.
  Iterator begin() {
    return Iterator(_mat, _start_i, _start_j);
  }
  Iterator end() {
    return Iterator(_mat, _end_i, _end_j);
  }

private:
  std::vector<std::vector<T>> *_mat;
  int _start_j;
  int _end_j;
  int _start_i;
  int _end_i;
};

这样我们就实现了全部的，可以用于 std::ranges::sort 的自定义随机访问迭代器与随机访问范围～

BenchMark

最后我们给出一个 Benchmark。结果如下：

原地Iteration的结果并没有比开辟一个临时数组的结果要好。我们尝试用 valgrind 来看模拟缓存行，看一下原因。

valgrind --tool=cachegrind --branch-sim=yes ./build/main --benchmark_filter=BM_SortIter/1024/1024
valgrind --tool=cachegrind --branch-sim=yes ./build/main --benchmark_filter=BM_SortTmp/1024/1024

首先是 SortIter:

----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
BM_SortIter/1024/1024     909470 us       909417 us            1
==2032== 
==2032== I   refs:      186,979,274
==2032== I1  misses:          8,151
==2032== LLi misses:          4,069
==2032== I1  miss rate:        0.00%
==2032== LLi miss rate:        0.00%
==2032== 
==2032== D   refs:       50,233,453  (37,559,572 rd   + 12,673,881 wr)
==2032== D1  misses:      6,356,376  ( 5,969,042 rd   +    387,334 wr)
==2032== LLd misses:        481,208  (   214,356 rd   +    266,852 wr)
==2032== D1  miss rate:        12.7% (      15.9%     +        3.1%  )
==2032== LLd miss rate:         1.0% (       0.6%     +        2.1%  )
==2032== 
==2032== LL refs:         6,364,527  ( 5,977,193 rd   +    387,334 wr)
==2032== LL misses:         485,277  (   218,425 rd   +    266,852 wr)
==2032== LL miss rate:          0.2% (       0.1%     +        2.1%  )
==2032== 
==2032== Branches:       19,548,141  (19,521,821 cond +     26,320 ind)
==2032== Mispredicts:     4,415,619  ( 4,414,737 cond +        882 ind)
==2032== Mispred rate:         22.6% (      22.6%     +        3.4%   )

然后是 SortTmp:

---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
BM_SortTmp/1024/1024     604312 us       604230 us            1
==2036== 
==2036== I   refs:      126,778,999
==2036== I1  misses:          8,159
==2036== LLi misses:          4,068
==2036== I1  miss rate:        0.01%
==2036== LLi miss rate:        0.00%
==2036== 
==2036== D   refs:       38,670,574  (24,859,524 rd   + 13,811,050 wr)
==2036== D1  misses:      3,406,017  ( 2,041,076 rd   +  1,364,941 wr)
==2036== LLd misses:        481,207  (   214,331 rd   +    266,876 wr)
==2036== D1  miss rate:         8.8% (       8.2%     +        9.9%  )
==2036== LLd miss rate:         1.2% (       0.9%     +        1.9%  )
==2036== 
==2036== LL refs:         3,414,176  ( 2,049,235 rd   +  1,364,941 wr)
==2036== LL misses:         485,275  (   218,399 rd   +    266,876 wr)
==2036== LL miss rate:          0.3% (       0.1%     +        1.9%  )
==2036== 
==2036== Branches:       22,688,280  (22,658,460 cond +     29,820 ind)
==2036== Mispredicts:     4,419,585  ( 4,418,703 cond +        882 ind)
==2036== Mispred rate:         19.5% (      19.5%     +        3.0%   )

我们可以看到：真正的延迟大概率出现在自定义迭代器的指令数目与访问次数上。自定义迭代器需要在排序函数中多次访问三层指针(_mat, _mat->data, _mat->data 的第 i 行，对应元素)，并且实现原地交换。并且在排序过程中，临时数组的缓存命中率更高，而原地交换版本跨行访问，缓存局部性更低。因此效果反而不如临时数组更好。

𝒲𝑒 𝓌𝒽𝑜 𝒸𝓊𝓉 𝓂𝑒𝓇𝑒 𝓈𝓉𝑜𝓃𝑒𝓈 𝓂𝓊𝓈𝓉 𝒶𝓁𝓌𝒶𝓎𝓈 𝒷𝑒 𝑒𝓃𝓋𝒾𝓈𝒾𝑜𝓃𝒾𝓃𝑔 𝒸𝒶𝓉𝒽𝑒𝒹𝓇𝒶𝓁𝓈.

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - 木木ちゃん

无用的知识：随机访问迭代器的实现

std::ranges::sort

random_access_*

random_access_iterator

实现 iterator 原型

实现 input_iterator 原型

实现 forward_iterator

实现 bidirectional_iterator

实现 random_access_iterator

random_access_range

std::sortable

BenchMark

`std::ranges::sort`

`random_access_*`

`random_access_iterator`

`random_access_range`

`std::sortable`