C++20 模板化算法：constexpr 迭代器的实现

作者

在 C++20 之前，几乎所有 STL 容器的迭代器都是运行时可用的；要在编译期使用迭代器进行算法，需要手动编写递归模板或者使用 constexpr 容器。然而，随着 C++20 对 constexpr 的大幅扩展，许多标准库容器也支持在编译期操作。本文将演示如何为一个简单的 constexpr 向量实现一个 constexpr 迭代器，并利用它在编译期执行算法，如计算元素和、查找最大值等。

1. constexpr 向量基础

我们首先定义一个最小化的 constexpr 向量模板，内部使用 std::array 来存储数据，提供基本的访问接口：

#include <array>
#include <cstddef>
#include <utility>

template <typename T, std::size_t N>
struct constexpr_vector {
    std::array<T, N> data{};

    constexpr constexpr_vector() = default;

    constexpr constexpr_vector(std::array<T, N> arr) : data{std::move(arr)} {}

    constexpr T& operator[](std::size_t idx) noexcept { return data[idx]; }
    constexpr const T& operator[](std::size_t idx) const noexcept { return data[idx]; }

    constexpr std::size_t size() const noexcept { return N; }
};

这个结构在编译期是完全可见的，且支持 operator[] 和 size()。

2. 设计 constexpr 迭代器

迭代器本质是对容器元素的引用。为了让迭代器在编译期可用，我们需要：

  1. 不包含运行时分支（例如 if 或 while）——使用递归模板实现循环。
  2. 提供 begin()、end() 返回迭代器对象。
  3. *实现 operator++、`operator、operator!=`** 等标准迭代器接口。

下面给出一个最小实现：

template <typename T, std::size_t N, std::size_t Index = 0>
struct constexpr_iterator {
    constexpr_iterator(const constexpr_vector<T, N>& vec) : vec_(vec) {}

    constexpr_iterator& operator++() {
        // 编译期递归到下一个索引
        return *this;
    }

    constexpr const T& operator*() const { return vec_[Index]; }

    constexpr bool operator!=(const constexpr_iterator& other) const {
        return Index != other.index_;
    }

    constexpr std::size_t index() const { return Index; }

private:
    const constexpr_vector<T, N>& vec_;
    static constexpr std::size_t index_ = Index;
};

但上述实现无法直接递归递增，因为 Index 是模板参数。更灵活的做法是使用包装结构 constexpr_index_iterator：

template <typename T, std::size_t N, std::size_t CurIdx>
struct constexpr_index_iterator {
    constexpr_index_iterator(const constexpr_vector<T, N>& vec) : vec_(vec) {}

    constexpr const T& operator*() const { return vec_[CurIdx]; }

    constexpr constexpr_index_iterator<T, N, CurIdx + 1> operator++() const {
        return constexpr_index_iterator<T, N, CurIdx + 1>(vec_);
    }

    constexpr bool operator!=(const constexpr_index_iterator<T, N, CurIdx + 1>& other) const {
        return CurIdx != other.index();
    }

    constexpr std::size_t index() const { return CurIdx; }

private:
    const constexpr_vector<T, N>& vec_;
};

template <typename T, std::size_t N>
constexpr auto constexpr_begin(const constexpr_vector<T, N>& vec) {
    return constexpr_index_iterator<T, N, 0>(vec);
}

template <typename T, std::size_t N>
constexpr auto constexpr_end(const constexpr_vector<T, N>& vec) {
    return constexpr_index_iterator<T, N, N>(vec);
}

现在我们拥有了可在编译期遍历的迭代器。

3. 编译期算法示例

3.1 求和

template <typename It>
constexpr auto sum(It begin, It end) {
    if (begin == end) return 0;
    return *begin + sum(++begin, end);
}

3.2 找最大值

template <typename It, typename T>
constexpr T max_element(It begin, It end, T current = T{}) {
    if (begin == end) return current;
    if (*begin > current) current = *begin;
    return max_element(++begin, end, current);
}

4. 实际使用

int main() {
    constexpr std::array<int, 5> arr = {1, 3, 5, 7, 9};
    constexpr constexpr_vector<int, 5> vec(arr);

    constexpr auto s = sum(constexpr_begin(vec), constexpr_end(vec));
    static_assert(s == 25, "Sum should be 25");

    constexpr auto maxv = max_element(constexpr_begin(vec), constexpr_end(vec), 0);
    static_assert(maxv == 9, "Max should be 9");

    return 0;
}

编译时，s 与 maxv 都会被计算，若不满足 static_assert 条件，编译会报错。这样我们就完成了一个完全在编译期工作的 constexpr 迭代器及其算法。

5. 进一步优化

  • 迭代器的移动语义：可以在 operator++ 返回 constexpr_index_iterator<T, N, CurIdx + 1> 并使用 auto 推导，以支持更广泛的 STL 算法。
  • 与标准容器互操作：如果需要在 constexpr 场景下使用 std::vector，可考虑 std::vector<T, std::allocator<T>> 的 constexpr 版本（C++23 起已部分支持）。
  • 模板元编程结合：利用 std::index_sequence 生成编译期索引序列，进一步简化迭代器实现。

6. 小结

通过上述方法，我们实现了一个简洁的 constexpr 迭代器，使得 STL 样式的算法能够在编译期执行。随着 C++ 标准的不断演进，越来越多的功能将被提升到 constexpr 范围内，编译期计算将成为编写高性能、可验证代码的重要手段。

发表评论