constexpr 算法与容器操作 ​

什么是 constexpr 算法与容器 ​

C++20 对标准库做了大规模的 constexpr 化改造。超过 100 个 <algorithm> 中的算法被标记为 constexpr,std::vector 和 std::string 的大部分成员函数也变成了 constexpr。这意味着你可以在编译期对容器进行排序、查找、变换、累加等操作。

配合 C++20 的 constexpr 动态内存分配(瞬态分配),编译期可以像运行期一样自由地使用标准库容器和算法。

constexpr 化的标准库算法 ​

C++20 中变为 constexpr 的主要算法分类:

分类代表算法
非修改序列操作find、count、all_of、any_of、none_of、for_each、search
修改序列操作copy、fill、transform、replace、remove、unique、reverse
排序操作sort、stable_sort、partial_sort、nth_element
二分查找lower_bound、upper_bound、binary_search、equal_range
集合操作merge、set_union、set_intersection、set_difference
堆操作push_heap、pop_heap、make_heap、sort_heap
最值操作min、max、minmax、min_element、max_element
排列操作next_permutation、prev_permutation、is_permutation
数值操作accumulate、inner_product、adjacent_difference、iota

constexpr 化的容器 ​

容器/类型constexpr 支持版本说明
std::arrayC++17大部分操作 constexpr
std::vectorC++20完全 constexpr(瞬态分配)
std::stringC++20完全 constexpr(瞬态分配)
std::pairC++20constexpr
std::tupleC++20constexpr
std::optionalC++20constexpr
std::variantC++20constexpr

基本示例 ​

cpp
#include <iostream>
#include <vector>
#include <string>
#include <array>
#include <algorithm>
#include <numeric>

// ============================
// 示例1:编译期排序
// ============================

constexpr auto compile_time_sort() {
    std::array<int, 8> arr = {5, 3, 8, 1, 9, 2, 7, 4};
    std::sort(arr.begin(), arr.end());  // 编译期排序
    return arr;
}

constexpr auto sort_descending() {
    std::array<int, 6> arr = {42, 17, 93, 5, 68, 31};
    std::sort(arr.begin(), arr.end(), std::greater<>{});  // 降序
    return arr;
}

void sort_demo() {
    constexpr auto sorted = compile_time_sort();
    // 编译期验证排序结果
    static_assert(sorted[0] == 1);
    static_assert(sorted[7] == 9);

    std::cout << "升序: ";
    for (int v : sorted) std::cout << v << " ";
    std::cout << std::endl;

    constexpr auto desc = sort_descending();
    static_assert(desc[0] == 93);
    std::cout << "降序: ";
    for (int v : desc) std::cout << v << " ";
    std::cout << std::endl;
}

// ============================
// 示例2:编译期查找与计数
// ============================

constexpr int find_first_even(const std::array<int, 8>& arr) {
    // 编译期查找第一个偶数
    auto it = std::find_if(arr.begin(), arr.end(),
                           [](int x) { return x % 2 == 0; });
    if (it != arr.end()) return *it;
    return -1;
}

constexpr int count_positive(const std::array<int, 6>& arr) {
    // 编译期计数正数个数
    return std::count_if(arr.begin(), arr.end(),
                         [](int x) { return x > 0; });
}

void find_count_demo() {
    constexpr std::array<int, 8> data = {3, 7, 2, 9, 4, 1, 8, 6};
    constexpr int first_even = find_first_even(data);
    static_assert(first_even == 2);
    std::cout << "第一个偶数: " << first_even << std::endl;

    constexpr std::array<int, 6> mixed = {-3, 5, -1, 7, 0, 2};
    constexpr int pos_count = count_positive(mixed);
    static_assert(pos_count == 3);
    std::cout << "正数个数: " << pos_count << std::endl;
}

// ============================
// 示例3:编译期 vector 操作
// ============================

// 编译期用 vector 做中间计算
constexpr int vector_sort_and_median() {
    std::vector<int> v = {15, 3, 8, 42, 1, 27, 9};
    std::sort(v.begin(), v.end());  // 编译期排序 vector
    return v[v.size() / 2];        // 返回中位数
}

constexpr int vector_remove_duplicates() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    std::sort(v.begin(), v.end());
    // 移除相邻重复元素
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    return static_cast<int>(v.size());  // 不重复元素的个数
}

constexpr auto vector_transform() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst(src.size());

    // 编译期变换:每个元素平方
    std::transform(src.begin(), src.end(), dst.begin(),
                   [](int x) { return x * x; });

    // 编译期累加
    int sum = std::accumulate(dst.begin(), dst.end(), 0);
    return sum;  // 1 + 4 + 9 + 16 + 25 = 55
}

void vector_demo() {
    constexpr int median = vector_sort_and_median();
    static_assert(median == 9);
    std::cout << "中位数: " << median << std::endl;

    constexpr int unique_count = vector_remove_duplicates();
    static_assert(unique_count == 7);
    std::cout << "不重复元素数: " << unique_count << std::endl;

    constexpr int sum_of_squares = vector_transform();
    static_assert(sum_of_squares == 55);
    std::cout << "平方和: " << sum_of_squares << std::endl;
}

// ============================
// 示例4:编译期字符串操作
// ============================

constexpr bool is_palindrome(std::string_view sv) {
    std::string s(sv);
    std::string reversed(sv);
    std::reverse(reversed.begin(), reversed.end());
    return s == reversed;
}

constexpr std::size_t count_words(std::string_view text) {
    if (text.empty()) return 0;

    std::size_t count = 0;
    bool in_word = false;

    for (char c : text) {
        if (c == ' ' || c == '\t' || c == '\n') {
            in_word = false;
        } else if (!in_word) {
            in_word = true;
            count++;
        }
    }
    return count;
}

constexpr auto to_uppercase() {
    std::string s = "hello world";
    std::transform(s.begin(), s.end(), s.begin(),
                   [](unsigned char c) -> char {
                       if (c >= 'a' && c <= 'z') return c - 32;
                       return c;
                   });

    // 返回长度和第一个字符(string 不能逃逸到运行期)
    return std::pair{s.size(), s[0]};
}

void string_demo() {
    constexpr bool pal1 = is_palindrome("racecar");
    constexpr bool pal2 = is_palindrome("hello");
    static_assert(pal1 && !pal2);
    std::cout << "racecar 是回文: " << std::boolalpha << pal1 << std::endl;

    constexpr auto words = count_words("The quick brown fox");
    static_assert(words == 4);
    std::cout << "单词数: " << words << std::endl;

    constexpr auto result = to_uppercase();
    static_assert(result.first == 11);
    static_assert(result.second == 'H');
    std::cout << "大写转换: 长度=" << result.first
              << " 首字母=" << result.second << std::endl;
}

// ============================
// 示例5:编译期生成查找表
// ============================

// 编译期用 vector 和算法生成素数表
template<std::size_t N>
constexpr auto sieve_of_eratosthenes() {
    // 用 vector 做筛法
    std::vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (std::size_t i = 2; i * i <= N; ++i) {
        if (is_prime[i]) {
            for (std::size_t j = i * i; j <= N; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 收集素数到 vector
    std::vector<int> primes;
    for (std::size_t i = 2; i <= N; ++i) {
        if (is_prime[i]) primes.push_back(static_cast<int>(i));
    }

    // 转成固定大小的 array
    std::array<int, 25> result{};  // 100 以内有 25 个素数
    for (std::size_t i = 0; i < primes.size() && i < result.size(); ++i) {
        result[i] = primes[i];
    }
    return result;
}

// 编译期生成 ASCII 字符类型表
constexpr auto make_char_type_table() {
    // 0=其他, 1=数字, 2=大写字母, 3=小写字母, 4=空白
    std::array<int, 128> table{};

    for (int c = '0'; c <= '9'; ++c) table[c] = 1;
    for (int c = 'A'; c <= 'Z'; ++c) table[c] = 2;
    for (int c = 'a'; c <= 'z'; ++c) table[c] = 3;
    table[' '] = 4;
    table['\t'] = 4;
    table['\n'] = 4;
    table['\r'] = 4;

    return table;
}

void lookup_table_demo() {
    constexpr auto primes = sieve_of_eratosthenes<100>();
    static_assert(primes[0] == 2);
    static_assert(primes[1] == 3);
    static_assert(primes[2] == 5);

    std::cout << "100以内的素数: ";
    for (int p : primes) {
        if (p > 0) std::cout << p << " ";
    }
    std::cout << std::endl;

    constexpr auto char_table = make_char_type_table();
    static_assert(char_table['A'] == 2);
    static_assert(char_table['a'] == 3);
    static_assert(char_table['5'] == 1);
    static_assert(char_table[' '] == 4);
    std::cout << "字符类型表: 'A'=" << char_table['A']
              << " '5'=" << char_table['5']
              << " ' '=" << char_table[' '] << std::endl;
}

// ============================
// 示例6:编译期 all_of / any_of / none_of
// ============================

constexpr bool check_all_positive() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    return std::all_of(arr.begin(), arr.end(),
                       [](int x) { return x > 0; });
}

constexpr bool check_any_negative() {
    std::array<int, 5> arr = {1, -2, 3, 4, 5};
    return std::any_of(arr.begin(), arr.end(),
                       [](int x) { return x < 0; });
}

constexpr bool check_none_zero() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    return std::none_of(arr.begin(), arr.end(),
                        [](int x) { return x == 0; });
}

void predicate_demo() {
    static_assert(check_all_positive());
    static_assert(check_any_negative());
    static_assert(check_none_zero());
    std::cout << "全部正数: " << std::boolalpha << check_all_positive() << std::endl;
    std::cout << "存在负数: " << check_any_negative() << std::endl;
    std::cout << "没有零: " << check_none_zero() << std::endl;
}

int main() {
    std::cout << "=== 编译期排序 ===" << std::endl;
    sort_demo();

    std::cout << "\n=== 编译期查找与计数 ===" << std::endl;
    find_count_demo();

    std::cout << "\n=== 编译期 vector ===" << std::endl;
    vector_demo();

    std::cout << "\n=== 编译期字符串 ===" << std::endl;
    string_demo();

    std::cout << "\n=== 编译期查找表 ===" << std::endl;
    lookup_table_demo();

    std::cout << "\n=== 编译期谓词 ===" << std::endl;
    predicate_demo();

    return 0;
}

编译期 vs 运行期使用的区别 ​

方面编译期(constexpr 上下文)运行期
vector/string可用,但内存必须在表达式内释放正常使用
array可以作为 constexpr 变量保留正常使用
算法所有 constexpr 算法可用所有算法可用
并行执行策略不可用可用(par、par_unseq 等)
IO 操作不可用可用
结果保留只能保留不含动态内存的类型任意类型

常见的编译期计算模式 ​

cpp
// 模式1:用 vector 计算,转为 array 保留
template<std::size_t N>
constexpr auto compute_table() {
    std::vector<int> temp;
    // ... 用 vector 做复杂计算 ...
    std::array<int, N> result{};
    // 把结果拷贝到 array
    return result;
}

// 模式2:用 vector 计算,返回标量结果
constexpr int compute_value() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    return std::accumulate(v.begin(), v.end(), 0);
}

// 模式3:用 string 处理,返回 bool 或数值
constexpr bool validate_string(std::string_view input) {
    std::string s(input);
    // ... 字符串处理和验证 ...
    return true;
}

适用场景 ​

  • 编译期数据排序和查找(查找表、配置表)
  • 编译期字符串解析和验证
  • 编译期数学计算(素数筛、阶乘表、组合数表)
  • 编译期数据变换和过滤
  • 用 static_assert 验证算法正确性
  • 零运行期开销的查找表生成

常见问题 ​

所有标准算法都是 constexpr 的吗?

大部分是,但不是全部。接受执行策略参数的并行版本不是 constexpr 的(因为多线程不能在编译期使用)。部分数值算法在 C++20 中变为 constexpr。

编译期排序和运行期排序的复杂度一样吗?

时间复杂度相同(都是 O(N log N)),但编译期的"时间"是编译时间,不是运行时间。大量编译期计算会增加编译时间。

std::map 和 std::set 可以在编译期使用吗?

C++20 中不能。std::map 和 std::set 的成员函数还没有被标记为 constexpr。可以用排序的 std::array 或 std::vector + 二分查找来替代。

Ranges 库的算法也是 constexpr 的吗?

是的。std::ranges 命名空间下的大部分算法在 C++20 中也是 constexpr 的。

编译期计算会增加编译时间吗?

会。复杂的编译期计算(比如对大数组排序)会显著增加编译时间。但换来的是零运行期开销。

注意事项 ​

  • vector 和 string 在编译期使用时遵循瞬态分配规则
  • 编译期计算的结果要保留到运行期,必须转成不含动态内存的类型
  • 大量编译期计算会增加编译时间
  • 并行执行策略在编译期不可用
  • 不同编译器对 constexpr 算法的支持程度可能不同
  • Ranges 算法在某些编译器上的 constexpr 性能可能不如传统 std 算法

编译器支持情况 ​

特性GCCClangMSVC
constexpr 算法(<algorithm>)10.0+12.0+19.28+
constexpr std::vector12.0+15.0+19.29+
constexpr std::string12.0+15.0+19.29+
constexpr std::array(大部分操作)8.0+5.0+19.14+
constexpr 数值算法(<numeric>)10.0+12.0+19.28+

总结 ​

C++20 将超过 100 个标准算法标记为 constexpr,同时让 std::vector 和 std::string 支持编译期使用。这意味着排序、查找、变换、累加等操作都可以在编译期完成。编译期使用动态容器遵循瞬态分配规则——内存必须在同一常量表达式内释放。常见模式是用 vector 做中间计算,结果转成 std::array 或标量类型保留。这些特性让编译期编程不再局限于模板元编程的递归套路,可以像写普通代码一样用循环、容器和算法来做编译期计算,代码更直观、更容易维护。