c++ 奇技淫巧

编译器版本： gcc 15.2.0

C++ 标准： c++14

前言

本文介绍了 C++ 中一些有趣/神奇的函数，虽然不一定用的到就是了。

STL，lambda，随机化，chrono 均有另开文章。

__builtin

以 __builtin 开头的函数均为编译器内置函数，效率极高。

位操作

__builtin_clz 计算前导 \(0\) 个数（\(32\) 位），\(0\) 是未定义行为。
__builtin_ctz 计算尾随 \(0\) 个数（\(32\) 位），\(0\) 是未定义行为。
__builtin_popcount 计算 \(1\) 的个数（\(32\) 位）。
__builtin_parity \(1\) 的个数为奇数则返回 \(1\)，偶数则返回 \(0\)。

上面函数结尾加 ll 即 \(64\) 位版本，例如 __builtin_clzll。

内存操作

__builtin_expect(expr, value) 告诉编译器 expr 最可能为 value，用于分支预测。
__builtin_prefetch(addr, rw, locality) 提前加载内存到缓存，rw 为 \(0\) 表示读，为 \(1\) 表示写；locality 为缓存层级。
__builtin_memcpy 同 memcpy 函数。
__builtin_memset 同 memset 函数。
__builtin_memmove 同 memmove 函数。

数学

__builtin_abs 绝对值。
__builtin_sqrt 平方根。
__builtin_add_overflow,__builtin_mul_overflow 等，检查溢出，返回 bool。

强制内联

__attribute__((always_inline)) 不管优化级别，都尽量内联。

1
2
3

inline __attribute__((always_inline)) int add(int a, int b) {
    return a + b;
}

分支预测

C++14 只有上文的 __builtin_expect。

1
2
3

if (__builtin_expect(x > 0, 1)) {
  // x > 0 更可能
}

C++20 新增了 [[likely]] 和 [[unlikely]]，用于分支预测。

if (x > 0) [[likely]] {
    // 这里分支更可能被执行
} else [[unlikely]] {
    // 不常执行
}

constexpr

constexpr 在 C++11 引入，表示一个变量为常量表达式，必须在编译期求值。

相较于 const 的仅保证只读，不保证编译期计算，它的速度会更快。

algorithm

这个库东西很多，这里只列举好用但大家不一定都知道的。

排列

partial_sort(first,middle,last) 只排序前几项，即保证 \([first,middle)\) 是最小且有序的，复杂度 \(O(n\log k)\)。
nth_element(first, nth, last) 找到第 \(n\) 小的元素，保证小于等于 \(nth\) 的元素都在 \(nth\) 的左边，大于等于 \(nth\) 的元素都在 \(nth\) 的右边，复杂度 \(O(n)\)。
is_sorted(first,last) 判断是否有序，复杂度 \(O(n)\)。
next_permutation(first,last) 产生下一个字典序排列，复杂度 \(O(n)\)。（CSP-S 2025 初赛）
prev_permutation(first,last) 产生上一个字典序排列，复杂度 \(O(n)\)。（CSP-S 2025 初赛）

查找

find(first, last, value) 返回指向第一个等于 value 的元素的迭代器，如果找不到，返回 last，复杂度 \(O(n)\)。
find_if(first, last, pred) 返回指向第一个满足 pred 的元素的迭代器，如果找不到，返回 last，复杂度 \(O(n)\)。
count(first, last, value) 返回 value 在区间 \([first, last)\) 中出现的次数，复杂度 \(O(n)\)。
count_if(first, last, pred) 返回 pred 判定为真的元素在区间 \([first, last)\) 中出现的次数，复杂度 \(O(n)\)。
binary_search(first, last, value) 判断 value 是否在区间 \([first, last)\) 中，复杂度 \(O(log n)\)（必须有序）。
equal_range(first, last, value) 返回一个 pair 表示一个区间 \([lower_bound, upper_bound)\) 满足区间内的元素等于 value，复杂度 \(O(log n)\)（必须有序）。
minmax(a,b) 返回一个 pair 表示 a 和 b 的最小值和最大值。
minmax_element(first, last) 返回一个 pair 表示区间 \([first, last)\) 中的最小值和最大值，复杂度 \(O(n)\)。

修改

copy(first,last,out) 复制元素到另一个容器，复杂度 \(O(n)\)。
move(first,last,out) 移动元素到另一个容器，复杂度 \(O(n)\)。
fill(first,last,value) 用指定值填充区间，复杂度 \(O(n)\)。
rotate(first, middle, last) 将区间 \([first,last)\) 变为 \([middle, last) + [first, middle)\)，复杂度 \(O(n)\)。
replace(first, last, old_value, new_value) 用 new_value 替换 old_value，复杂度 \(O(n)\)。

随机化

shuffle(first, last, rng) 将区间 \([first,last)\) 随机化，复杂度 \(O(n)\)（请不要再用 random_shuffle）。

numeric

这个库提供了一些数值计算的函数。

accumulate(first, last, init) 累加区间 \([first,last)\)，init 为初始值，复杂度 \(O(n)\)。
inner_product(first1, last1, first2, init) 计算两个区间 \([first1,last1)\) 和 \([first2,last2)\) 的内积，init 为初始值，复杂度 \(O(n)\)。
partial_sum(first, last, out) 计算区间 \([first,last)\) 的前缀和，结果存入 out，复杂度 \(O(n)\)。
adjacent_difference(first, last, out) 计算区间 \([first,last)\) 的相邻差，结果存入 out，复杂度 \(O(n)\)。
iota(first, last, value) 用 value 填充区间 \([first,last)\)，复杂度 \(O(n)\)。

initializer_list

C++11 引入的一种新的数据结构，支持用大括号初始化列表，注意定义后不能修改。

常与 STL 容器一起使用：

std::vector<int> v = {1, 2, 3};
std::list<int> l = {1, 2, 3};
std::set<int> s = {1, 2, 3};
std::max({1, 2, 3});

或者用于循环：

1
2
3

for (int i : {1, 2, 3}) {
  // 循环体
}

iterator

C++11 引入的一些迭代器相关的函数。

distance(first, last) 返回迭代器之间的距离，复杂度 \(O(1)\)。
advance(it, n) 移动迭代器 it 指向的位置 n 步，复杂度 依赖迭代器类型。
next(it, n) 返回迭代器 it 指向的位置 n 步后的迭代器，复杂度 依赖迭代器类型。
prev(it, n) 返回迭代器 it 指向的位置 n 步前的迭代器，复杂度 依赖迭代器类型。

时间复杂度：

对于 vector，deque 和 array 等，支持 直接跳跃，复杂度 \(O(1)\)。
对于 list，map 和 set 等，时间复杂度 \(O(n)\)。
对于单向迭代器，例如 forward_list，istream_iterator 等，时间复杂度 \(O(n)\)，且只支持单向移动。

nullptr

C++11 引入的 nullptr 关键字，用于表示空指针。

主要区别于 NULL，因为 NULL 被实现为 #define NULL 0。

decltype

C++11 引入的 decltype 关键字，用于获取表达式的类型。

// decltype(expression) var;
int x = 10;
double y = 2.5;
decltype(x) a = x; // int
decltype(y) b = y; // double
decltype(x+y) c = x+y; // double, because (x+y) is a double expression

auto

C++11 引入的 auto 关键字，用于自动推导类型。

类型推导

必须初始化，否则无法推导类型。

1
2
3

auto x = 10; // int
auto y = 2.5; // double
auto z = "hello"; // const char*

注意默认去掉引用和 const。

int a = 10;
const int b = 20;

auto c = a;        // int
auto d = &a;       // int*
auto e = &b;       // const int*
auto& f = a;       // int&，引用类型必须显示加 &

1
2
3

auto add(int a,int b){
  return a+b; // 返回值类型自动推导
}

循环

vector<int> v = {1,2,3,4,5};
for (auto x : v) {
  // 循环体
}

for (auto& x : v) { // 如果要修改元素
  // 循环体
}

结构化绑定

C++17 引入，但 C++14 可用，应该会报 warning。

auto [x, y] = make_pair(1, 2);

map<string, int> mp = {{"a", 1}, {"b", 2}};
for (auto [key, value] : mp) {
  // 循环体
}

if / switch 初始化

1
2
3

if (auto it = mp.find(key); it != mp.end()) {
    cout << it->second;
}

C++20

模板参数中使用 auto：

template<auto N>
void print() {
    cout << N << endl;
}

print<42>();  // N 被推导为 int