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::array | C++17 | 大部分操作 constexpr |
std::vector | C++20 | 完全 constexpr(瞬态分配) |
std::string | C++20 | 完全 constexpr(瞬态分配) |
std::pair | C++20 | constexpr |
std::tuple | C++20 | constexpr |
std::optional | C++20 | constexpr |
std::variant | C++20 | constexpr |
基本示例
#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 操作 | 不可用 | 可用 |
| 结果保留 | 只能保留不含动态内存的类型 | 任意类型 |
常见的编译期计算模式
// 模式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 算法
编译器支持情况
| 特性 | GCC | Clang | MSVC |
|---|---|---|---|
constexpr 算法(<algorithm>) | 10.0+ | 12.0+ | 19.28+ |
constexpr std::vector | 12.0+ | 15.0+ | 19.29+ |
constexpr std::string | 12.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 或标量类型保留。这些特性让编译期编程不再局限于模板元编程的递归套路,可以像写普通代码一样用循环、容器和算法来做编译期计算,代码更直观、更容易维护。