网络工具综合学习网站:Runoob。
References
流 stream
iostream
: istream
+ostream
.
istream
:cin
对象- 输入运算符
>>
- 输入运算符
ostream
:cout
对象。cerr
(错误、警告),clog
(一般信息)- 输出运算符
<<
- 输出运算符
namespace
命名空间$\rightarrow$作用域运算符:::
,如std::cin
不定流
1 | while(std::cin>>value){ |
cin
返回cin
(输入流),除非遇到文件结束符(Ctrl+Z
)、输入错误,返回false
注释
//
:行注释
/* ... */
:注释界定符(不可嵌套)
编译
语法错误 syntax error
常见:
- main函数参数列表忘写
int main{}
(中招) - 某个函数漏掉
}
进而导致不匹配 endl
后使用冒号而不是分号
类型错误 type error
- 老版编译器
auto
不识别
声明错误 declaration error
emmm
模板 STL4C++
顺序容器
vector
向量
1 | vector<int> V; |
自定义比较函数cmp
:(以优先队列为例)
1 | struct cmp { |
string
字符串
1 | string S; |
deque
双端队列
1 | deque<int> DQ; |
list
双向链表
1 | list<int> L; |
forward_list
单向链表
只支持单向顺序访问。
1 | forward_list<int> FL; |
array
固定数组
1 | array<int, 100> A; |
stack
栈
stack/queue/priority_queue 均是顺序容器适配器。
1 | stack<int> S; // 以deque为底层容器 |
queue
队列
1 | queue<int> Q; // 以deque为底层容器 |
priority_queue
优先队列
即完全二叉堆。
1 | priority_queue<int> PQ; // 以vector为底层容器,默认大根堆less<int> |
关联容器
map
映射
1 | map<string, int> M; |
multimap
映射(可重复)
1 | multimap<string, int> M; |
pair
对
1 |
|
pair可以看作如下结构体:
1 | struct pair{ |
无序容器
set
集合
尽管是“无序容器”,仍然可以$O(logn)$查找。(
set
中的元素自动递增排序)
1 | set<int> S: // map 和 set 底层都基于红黑树 |
multiset
集合(可重复)
1 | set<int> S: // map 和 set 底层都基于红黑树 |
bitset
位图
1 | bitset <int n> b; //n为二进制位数(位图的大小) |
不定长的
bitset
,请使用(奇葩的)vector<bool>
。
哈希容器
当不需要元素排序时,尽量使用基于Hash算法的哈希容器获得更好的查找性能。C++11引入了哈希容器。
unordered_map
/ unordered_set
仅仅是底层实现不同,通用外部方法封装与map
/ set
一致。例子如下:
1 | unordered_map<string, int> um { |
哈希容器还包括:
unordered_multimap
/unordered_multiset
。
自定义哈希函数
1 |
|
对于自定义类型,需要提供自定义的Hash函数。例如:
1 | struct Type{ |
STL容器-输出封装(vector
/set
)
1 | template<typename T> |
使用方法:
1 | vector<int> a; a.push_back(1); a.push_back(2); a.push_back(3); |
C++算法库
操作
算法 | 作用 |
---|---|
swap(a, b) |
交换 |
for_each(beg, end, func) |
对 [beg, end) 中的每个元素均调用func 函数 |
next_permutation(beg, end, cmp) |
下一个排列;就地;参数为迭代器[beg, end) |
prev_permutation(beg, end, cmp) |
上一个排列 |
fill(a, a + n, x) / fill_n(a, n, x) |
更新;将a数组中前n项设为数字x |
memset(a,b,n) |
设置;b可为0 / -1 / 0x3f (Inf.);前n项设为数字b(char型初始化函数) |
unique(beg, end, cmp) |
唯一化 |
reverse(beg, end) |
反转;参数为迭代器[beg, end) |
rotate(beg, mid, end) |
旋转;操作后变为[mid, end)+[beg, mid) ;返回旋转前beg元素的新位置 |
equal(beg1, end1, beg2) |
判断两个序列是否全等 |
copy(beg, end, dest) / copy_n(beg, n, dest) |
复制 |
copy_if(beg, end, dest, func) |
选择性复制;满足func 返回true |
merge(beg1, end1, beg2, end2, dest, cmp) |
有序归并 |
inplace_merge(beg, mid, end, cmp) |
就地有序归并 |
replace(beg, end, old_e, new_e) |
选择性替换 |
replace_if(beg, end, func, new_e) |
根据func 选择性替换 |
set_union(beg, end, beg2, end2, dest, cmp) |
求并 |
set_intersection(beg, end, beg2, end2, dest, cmp) |
求交 |
set_difference(beg, end, beg2, end2, dest, cmp) |
求差;减去第二个序列中的元素 |
set_symmetric_difference(beg, end, beg2, end2, dest, cmp) |
求对称差;所有只出现在一个序列中的元素 |
substr(beg, end) |
返回[beg, end) 子串 |
搜索
算法 | 作用 |
---|---|
find(beg, end, e) |
查找元素e |
find_if(beg, end, func) |
按条件查找;使得func 返回true |
find_if_not(beg, end, func) |
按条件查找不满足的项;使得func 返回false |
count(beg, end, e) |
统计;在[beg, end) 内等于e 的元素个数 |
count_if(beg, end, func) |
统计;在[beg, end) 内使func 返回true 的元素 |
__builtin_popcount(x) |
1 计数;计算x 的二进制中1 的个数 |
all_of(beg, end, func) |
是否[beg, end) 全部命中;返回bool 型 |
any_of(beg, end, func) |
任意命中 |
none_of(beg, end, func) |
无一命中 |
binary_search(beg, end, e, cmp) |
二分查找;返回bool |
lower_bound(a, a+a.size(), x, cmp) |
下界;查找 $\leq x$ 的第一个位置;cmp 可选;返回一个迭代器 |
upper_bound(a, a+a.size(), x, cmp) |
上界;查找 $>x$ 的第一个位置 |
equal_range(beg, end, e, cmp) |
返回pair 对(A, B) ;分别是 lower_bound 和upper_bound 的返回值 |
min_element(beg, end, func) |
最小值;区间[beg, end) ;func 比较器是可选参数 |
max_element(beg, end, func) |
最大值 |
排序
算法 | 作用 |
---|---|
sort(beg, end, cmp) |
排序;默认升序less ($<$);内置 greater / less_equal / greater_equal |
stable_sort(beg, end, cmp) |
稳定排序 |
is_sorted(beg, end, cmp) |
判断有序性 |
partial_sort(beg, beg+k, end, cmp) |
部分排序;比如求前 k 大元素 将序列中前k小元素按顺序置于前k个位置 其他元素不保证顺序。O(nlogk) |
nth_element(beg, nth, end, cmp) |
nth 必须为迭代器,初始指向首位,最后返回所求位置;比如求第 n 大元素;并且会按照该元素划分 |
partition(beg, end, func) |
快速划分;返回分割点 |
stable_partition(beg, end, func) |
稳定划分 |
is_partitioned(beg, end, func) |
如果序列已被划分为[满足 / 不满足] ;则返回true |
partition_copy(beg, end, dest1, dest2, func) |
将满足func 的元素拷贝到dest1 ;其他拷贝到dest2 |
partition_point(beg, end, func) |
求分割点;返回前段的end()处 |
数学
算法 | 作用 |
---|---|
min(a, b, cmp) / min(seq, cmp) |
最小值;seq 是一个序列 |
max(a, b, cmp) / max(seq, cmp) |
最大值 |
min_element(beg, end, cmp) / max_element(beg, end, cmp) |
序列最大/最大元素(返回迭代器) |
__gcd(a,b) |
最大公约数 |
lexicographical_compare(beg1, end1, beg2, end2, cmp) |
字典序比较 |
accumulate(beg, end, init, op) |
序列求和;init 为初值op 可自定义二元运算返回 init 的类型 |
inner_product(beg1, end1, beg2, init, op1, op2) |
内积;init 为初始值;op1 和op2 为可选的广义加法/乘法 |
partial_sum(beg, end, dest, op) |
计算后缀数组; 每一个新元素等于其前缀的累计和 |
iota(beg, end, e) |
将每一项分别设为[e, e+1, ...] |
sqrt(x) / cbrt(x) |
开方 / 立方根 |
exp(x) |
e指数 |
pow(x, y) |
x^y幂 |
log(x) |
ln对数 |
log10(x) |
lg对数 |
abs(x) / fabs(d) |
绝对值 / 浮点绝对值 |
sin(x) / cos(x) / tan(x) / atan(x) |
三角函数 |
ceil(x) / floor(x) |
向上/下取整 |
C++特殊语法
模板 template
1 | template <typename T> |
类型推导 auto
1 | for (auto i: S) // 简约遍历法 |
这种写法中,for
循环会从头到尾遍历一遍S
容器,将其中的值取出。需要注意的是,如果要修改元素的值的话,应该声明成引用auto& i
。
需要注意的是,auto
关键字是类型推断而不是动态类型,用auto
声明的变量必须初始化,并且确定类型后就不能更改。
匿名函数 lambda
函数式编程在需要的地方定义函数,而不是提前定义好才能用。
1 | // 指明返回类型 |
空指针 nullptr
NULL
宏 = 常整数0
。nullptr
关键字代表值类型std::nullptr_t
,语义上可理解为空指针。
1 | char *p = nullptr; |