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)
如果参数是字母或数字,该函数返回trueisalpha(c)
如果参数是字母,该函数返回trueisdigit(c)
如果参数是数字,该函数返回trueislower(c)
如果参数是小写字母,该函数返回trueisupper(c)
如果参数是大写字母,该函数返回trueisxdigit(c)
如果参数是十六进制的数字,即0~9、a~f、A~F,该函数返回truetolower(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->intstoll(s)
// string->long longstoi(s, 0, 16)
/stoll(s, 0, 16)
// 把s看成16进制,支持2-36进制stoull(s)
// string->unsigned long longstod(s)
// string->doublestold(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;
};
auto cmp = [](Node a, Node b) { return a.y < b.y; };
priority_queue<Node, vector<Node>, decltype(cmp)> q(cmp);
自定义比较运算符的priority_queue(y大根堆)。
<set>
struct Node {
int x, y;
};
auto cmp = [](Node a, Node b) { return a.y < b.y; };
set<Node, decltype(cmp)> st(cmp);
自定义比较运算符的set(y从小到大)。
st.erase(x)
删除multiset中所有的x。st.extract(x)
删除multiset中的一个x。