C++ reference

__builtin

  • __builtin_clz(x) 返回x的二进制前导0的个数。
  • __builtin_ctz(x) 返回x的二进制末尾0的个数。
  • __builtin_popcount(x) 返回x的二进制中1的个数。

以上函数的long long版本：

  • __builtin_clzll

  • __builtin_ctzll

  • __builtin_popcountll

  • __lg(x)$=\lfloor \log_2 x \rfloor$，__lg(0) 未定义

  • lsb(x) = ctz(x), msb(x) = __lg(x), minp2(x) = x <= 1 ? 1 : 1 « (msb(x - 1) + 1)

// alternatives
int __lg32(int x) { return 31 - __builtin_clz(x); }
int __lg64(ll x) { return 63 - __builtin_clzll(x); }

// C++20
bit_ceil(x)     // >= x 的最小的2的整数幂
bit_floor(x)    // <= x 的最大的2的整数幂
bit_width(x)    // 表示 x 所需的最小位数（bit_width(0) = 0，与 python bit_length() 行为一致）
countl_zero(x)  // 前导0个数
countl_one(x)   // 前导1个数
countr_zero(x)  // 末尾0个数
countr_one(x)   // 末尾1个数
popcount(x)     // 1个数

<cmath>

  • ceil(x) x向上取整
  • floor(x) x向下取整
  • fmod(x, y) x / y的浮点数余数
  • pow(x, y) x的y次幂
  • exp(x) e的x次幂
  • sqrt(x) x的平方根
  • cbrt(x) x的立方根
  • log(x) x以e为底的对数
  • log10(x) x以10为底的对数
  • log2(x) x以2为底的对数
  • atan2(y, x) y/x的反正切值，即点(x, y)与x轴正方向的夹角(返回值范围$[-\pi, \pi)$),atan2(0, 0) = 0
  • hypot(x, y) 返回直角三角形斜边的长度：$\sqrt{x^2 +y^2}$)

<random>

  • mt19937 rng(time(0)); 初始化随机数生成器
  • rng() 返回一个随机的unsigned int值(0 ~ 4294967295)
  • mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 快速更新种子（适合对拍）

<cctype>

  • isalnum(c) 如果参数是字母或数字，该函数返回true
  • isalpha(c) 如果参数是字母，该函数返回true
  • isdigit(c) 如果参数是数字，该函数返回true
  • islower(c) 如果参数是小写字母，该函数返回true
  • isupper(c) 如果参数是大写字母，该函数返回true
  • isxdigit(c) 如果参数是十六进制的数字，即0～9、a~f、A~F，该函数返回true
  • tolower(c) 如果参数是大写字符，则返回其小写，否则返回该参数
  • toupper(c) 如果参数是小写字母，则返回其大写，否则返回该参数

<algorithm>

  • max_element(a, a + n) 返回序列中最大值的地址。
  • min_element(a, a + n) 返回序列中最小值的地址。
  • minmax_element(a, a + n) 返回一个pair(min_element, max_element)。
  • nth_element(a, a + k, a + n) 将第k大元素放到它该放的位置上，左边元素都小于它，右边元素都大于它。O(n)。
  • count(a, a + n, x) 返回序列中x的出现次数。
  • fill(a, a + n, x) 将序列中的元素全部初始化为x。
  • copy(a, a + n, b) 将序列a中的n个元素复制到b中。
  • reverse(a, a + n) 翻转一个n个元素的序列。
  • rotate(a, a + k, a + n) 旋转一个n个元素的序列，即a=a[k:]+a[:k]。
  • shuffle(a, a + n, rng) 随机打乱一个n个元素的序列。
  • unique(a, a + n) 去除序列中相邻的重复元素，返回去重后的尾地址。
  • next_permutation(a, a + n)
  • prev_permutation(a, a + n) 把序列看作一个排列，求这些元素构成的全排列中，字典序排在下一个/上一个的排列，并直接在序列上更新。 若不存在字典序更靠后/靠前的排列，则返回false（但此时也会更新），否则返回true。 next_permutation({4, 3, 2, 1}) = {1, 2, 3, 4}
  • binary_search(a, a + n, x) 查找有序序列中是否存在元素x，找到返回1，否则返回0。
  • lower_bound(a, a + n, x) 返回有序序列中能插入x的最小地址。
  • upper_bound(a, a + n, x) 返回有序序列中能插入x的最大地址。

<numeric>

  • accumulate(a, a + n, 0) 返回数组a中元素的和。
  • partial_sum(a, a + n, sum) // sum[0] = a[0], sum[i] = sum[i - 1] + a[i] 计算数组a中元素的前缀和存入数组sum中（支持原地更新）。
  • adjacent_difference(a, a + n, diff) // diff[0] = a[0], diff[i] = a[i] - a[i - 1] 计算数组a中元素的差分存入数组diff中（支持原地更新）。
  • iota(a, a + n + 1, 0) 相当于for (…) a[i] = i;

<string>

  • s.find(s1) / s.rfind(s1) 返回字符串s1在s中第一次/最后一次出现的位置，如果没有找到，则返回-1。
  • s.starts_with("prefix") / s.ends_with("suffix") (C++20) 返回字符串是否包含某个前缀/后缀。
  • s.substr(i, len) 返回字符串s中下标从i开始长度为len的子串。
  • s.c_str() 返回字符串s的C风格字符指针。
  • stoi(s) // string->int
  • stoll(s) // string->long long
  • stoi(s, 0, 16) / stoll(s, 0, 16) // 把s看成16进制，支持2-36进制
  • stoull(s) // string->unsigned long long
  • stod(s) // string->double
  • stold(s) // string->long double 把字符串s转换成数值。
  • to_string(x) 把数值x转换为字符串。

<bitset>

  • ~s：对s按位取反
  • &, |, ^：按位与、或、异或
  • <<, >>：左移、右移
  • ==, !=：比较两个bitset是否相等
  • s[k]：s的第k位（最低位是第0位）。
  • s.count() 返回s中有多少位为1。
  • s.any() / s.none() 若s所有位都为0，则s.any()返回false，s.none()返回true。 若s至少一位为1，则s.any()返回true，s.none()返回false。
  • s.set() / s.reset() / s.flip() 把s的所有位变为1 / 变为0 / 取反。
  • s.to_string() / s.to_ulong() / s.to_ullong() 返回s的字符串/unsigned long/unsigned long long表示。

<queue>

struct Node {
    int x, y;
    double val;
    bool operator < (const Node &b) const { return val < b.val; }
};
priority_queue<Node> q;

自定义比较运算符的priority_queue（val从大到小）。

struct cmp {
    bool operator () (const Node &x, const Node &y) { return x.val > y.val; }
};
priority_queue<Node, vector<Node>, cmp> q;

自定义比较运算符的priority_queue（val从小到大）。

<set>

struct Node {
    int id, val;
    friend bool operator < (const Node &x, const Node &y) {
        return x.val < y.val;
    }
};
set<Node> st;

自定义比较运算符的set（val从小到大）。

struct cmp {
    bool operator () (const Node &x, const Node &y) { return x.val > y.val; }
};
set<Node, cmp> st;

自定义比较运算符的set（val从大到小）。

  • st.erase(x) 删除multiset中所有的x。
  • st.erase(st.find(x)) 删除multiset中的一个x。