思维之海

——在云端,寻找我的星匙。

C++学习手册

本手册主要选取C++中实用性最大的部分,浅尝辄止。

网络工具综合学习网站:Runoob

References

C++Primer

面向对象程序设计(C++)(自主模式)

C/C++ 面试基础知识总结

流 stream

iostream: istream+ostream.

  • istreamcin对象
    • 输入运算符>>
  • ostreamcout对象。cerr(错误、警告),clog(一般信息)
    • 输出运算符<<

namespace命名空间$\rightarrow$作用域运算符:::,如std::cin

不定流

1
2
3
while(std::cin>>value){
...
}

cin返回cin输入流),除非遇到文件结束符Ctrl+Z)、输入错误,返回false

注释

//:行注释

/* ... */:注释界定符(不可嵌套)

编译

语法错误 syntax error

常见:

  • main函数参数列表忘写int main{} (中招)
  • 某个函数漏掉}进而导致不匹配
  • endl后使用冒号而不是分号

类型错误 type error

  • 老版编译器auto不识别

声明错误 declaration error

emmm

模板 STL4C++

顺序容器

vector 向量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> V;
vector<int> V(7); // 默认值初始化;int默认值为0
vector<int> V(7, 1); // 自定义初始化,7个1
vector<int> V{1,2,3}; // C++11全自定义初始化,[1, 2, 3]
vector<int>::iterator it; // 新建迭代器

V.push_back(t); // 在尾部插入元素
V[i]; // 索引元素,类似数组
V.pop_back(); // 弹出尾部元素
V.erase(pos); // 删去指定位置元素
V.erase(pos1, pos2); // 删去指定范围[pos1, pos2)元素
V.clear(); // 清空
V.insert(it, x) // 插入

// 以下为顺序容器通用操作
V.empty(); // 判断是否为空
V.size(); // 返回数组大小
V.resize(); // 设置容器大小
V.begin(); V.end(); // 迭代器,分别指向首尾,类似指针
V.cbegin(); V.cend(); // 常量迭代器,const.属性
V.rbegin(); V.rend(); // reversed,反向迭代器,指向尾首
V.crbegin(); V.crend(); // 常量反向迭代器
V.assign(A.cbegin(), A.cend()); // 赋值操作,类似延后构造
V.assign(n, t);
swap(A, B); // 交换
reverse(A.begin(), A.end()); // 反转

自定义比较函数cmp:(以优先队列为例)

1
2
3
4
5
6
7
8
struct cmp {
bool operator ()(int x, int y){
return x > y; // x 小的优先级高
//也可以写成其他方式,如:return p[x] > p[y]; 表示 p[i] 小的优先级高
}
};
priority_queue<int, vector<int>, cmp>q;//定义方法
//其中,第二个参数为容器类型。第三个参数为比较函数。

string 字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string S;

S[i]; // 索引元素,类似数组
S[i] = tolower(S[i]); // 转为小写;需要循环
S[i] = toupper(S[i]); // 转为大写
S.append("123"); // 追加字符串
S.erase(pos, len);// 删除子串,位置[pos, pos+len)
S.size(); S.length(); // 长度,O(1)
S.replace(11, 3, "5th"); // 从位置11开始删除3个字符并插入"5th"
S.replace(it1, it2, str2); // 把S的迭代器[it1, it2)范围的子串替换为str2
s1 = S.substr(0, 3), // [0,3)子串
S.find("b",5); // 下标5开始,查找字符串b,返回b在s中的下标
S.rfind("b"); // 反向查找
S.find_first_of(ele); // 返回ele字符串中任意字符在s中第一次出现的下标位置,该函数的返回值是被搜索字符串的第 1 个字符第 1 次出现的下标(位置)
S.find_last_of(ele); // 返回值是被搜索字符串的最后 1 个字符的下标(位置)
S.find_first_not_of(ele); //查找S中与ele第一个不匹配的位置
S.find_last_not_of(ele);
to_string(A); // 将任何基本型转换为string
stoi(s, p, b); // 将string 转换为 int, p默认为0(保存指针), b默认为10(进制)
stod(s); // 将string 转换为 double
stoll(s); // 将string 转换为 long long

deque 双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
deque<int> DQ;

DQ.push_front(ele); // 头部插入
DQ.push_back(ele); // 尾部插入
DQ.insert(it, ele); // 在it迭代器位置之前插入元素
DQ.insert(it, num, ele); // 插入num个ele
DQ.insert(it, first, last); // 插入迭代器[first, last)所指内元素
DQ.erase(it); // 删除某个元素
DQ.erase(first, last); // 删除迭代器[first, last)所指内元素
DQ.pop_front(); // 头部删除
DQ.pop_back(); // 尾部删除
DQ.at(pos); // 索引
DQ.front(); // 首元素的引用
DQ.back(); // 尾元素的引用

list 双向链表

1
2
3
4
5
list<int> L;

// 支持deque的以上同名操作
L.clear(); // 清空
L1.merge(L2, greater<int>());//合并后升序排列,实际上默认就是升序

forward_list 单向链表

只支持单向顺序访问。

1
2
3
4
5
forward_list<int> FL;

// forward_list不支持pop_back(), vector和string不支持pop_front()
FL.max_size(); // 返回最大支持容量,forward_list不支持size操作
FL.empty();

array 固定数组

1
2
3
4
array<int, 100> A;
array<double,100> A {}; // 初始化为100个0.0
array<double,5> A {0.5, 1.0}; // 部分初始化: {0.5, 1.0, 0.0, 0.0, 0.0}
A.fill(3.1415926); // 设定所有元素为某值

stack

stack/queue/priority_queue 均是顺序容器适配器。

1
2
3
4
5
6
7
stack<int> S; // 以deque为底层容器

S.push(i); // 压入元素,O(1)
S.emplace(inits); //构造并压入元素,inits必须是可供构造元素的数据
S.top(); // 读取栈顶,O(1)
S.pop(); // 弹出元素,无返回值,O(1)
S.empty(); S.size(); // O(1)

queue 队列

1
2
3
4
5
6
7
queue<int> Q; // 以deque为底层容器

Q.push(i); // 压入元素,O(1)
Q.emplace(inits); //构造并压入元素,inits必须是可供构造元素的数据
Q.front(); Q.back(); // 读取队首/尾,O(1)
Q.pop(); // 弹出元素,无返回值,O(1)
Q.empty(); Q.size(); //O(1)

priority_queue 优先队列

即完全二叉堆。

1
2
3
4
5
6
7
8
priority_queue<int> PQ;  // 以vector为底层容器,默认大根堆less<int>
priority_queue<int, vector<int>, greater<int>> PQ; // 小根堆

PQ.push(i); // 压入元素,O(logN)
PQ.emplace(inits); //构造并压入元素,inits必须是可供构造元素的数据
PQ.top(); // 读取最高优先级元素,O(1)
PQ.pop(); // 弹出元素,无返回值,O(logN)
PQ.empty(); PQ.size(); // O(1)

关联容器

map 映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
map<string, int> M;

M["top"] = 1; // 赋值添加元素
M.at(key); // 另一种访问方式
M.find(key); // O(logN),返回迭代器
if(M.find(key) != M.end()); // 判断是否存在
M.insert( make_pair(key, value) ); // 新建对并插入
M.insert( pair<Tk, Tv>(key, value) );
M.insert( {key, value} );
map<string, int>::iterator it = M.find(key); // 查找失败返回end()
if(M.find(a) == M.end()) // 若没找到
M.erase(key); // 删去键所指定的对,O(logN)
M.erase(it); // 删去迭代器指定的对,O(1)
M.size(); // O(1)
M.clear(); // O(N)

multimap 映射(可重复)

1
multimap<string, int> M;

pair

1
2
3
4
5
6
7
8
9
#include <utility>

pair<T1, T2> p;
pair<T1, T2> p(v1, v2);
make_pair(v1, v2);

it->first; it->second; // 通过first和secnod来引用值,it迭代器指向一个pair
p1 < p2; //如果p1.first<p2.first或者!(p2.first < p1.first)&& p1.second<p2.second,则返回true
p1 == p2 //p1.first == p2.first && p1.second == p2.second

pair可以看作如下结构体:

1
2
3
4
struct pair{
typeName1 first;
typeName2 second;
};

无序容器

set 集合

尽管是“无序容器”,仍然可以$O(logn)$查找。(set中的元素自动递增排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
set<int> S: // map 和 set 底层都基于红黑树
set <T, greater <T> > st; // 降序排列

S.insert(ele); // O(logN)
S.find(ele); // O(logN),返回迭代器
S.erase(ele); // O(logN)
S.erase(it); // O(1),迭代器删除
S.size(); // O(1)
S.clear(); // O(N)
S.begin(); S.end(); // 迭代器
for(set<int>::iterator it = S.begin(); it != S.end(); ++it){ } // 遍历
pair<itr, itr> s.equal_range(T e); //返回键值等于e的元素区间;
int s.count(T e); //返回键值为e的元素的个数;
itr s.upper_bound(T e); //返回大于e的第一个元素位置;
itr s.lower_bound(T e); //返回大于等于e的第一个元素位置;

multiset 集合(可重复)

1
2
3
4
5
6
set<int> S: // map 和 set 底层都基于红黑树

S.insert(ele);
S.erase(ele);
S.size();
S.begin(); S.end(); // 迭代器

bitset 位图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bitset <int n> b; //n为二进制位数(位图的大小)
bitset <int n> b(unsigned num);
bitset <int n> b(string s); //s为字符串形式的二进制位

b[3] = 1; b[0] = true; // 赋值 / 读取
int b.size(); //返回位数
int b.count(); //返回为1的位数个数
bool b.any(); //返回是否有为1的位
bool b.none(); //范围是否没有为1的位
bitset b.set(); //全部位赋值为1
bitset b.set(int p); //将p位赋值为1
bitset b.set(int p, bool num); //将p位设置为num
bitset b.reset(); //全部位赋值为0
bitset b.reset(int p);
bitset b.flip(); //全部取反
bitset b.flip(int p);
unsigned long b.to_ulong(); //返回为ulong,超出报错
unsigned long long b.to_ullong(); //返回为ull,超出报错
string b.to_string(); //返回为string

不定长的bitset,请使用(奇葩的)vector<bool>

哈希容器

当不需要元素排序时,尽量使用基于Hash算法的哈希容器获得更好的查找性能。C++11引入了哈希容器。

unordered_map / unordered_set

仅仅是底层实现不同,通用外部方法封装与map / set一致。例子如下:

1
2
3
4
5
6
unordered_map<string, int> um {
{"Dijkstra", 1972}, {"Scott", 1976},
{"Wilkes", 1967} , {"Hamming", 1968}
};
um["Ritchie"] = 1983;
for(auto x : um) cout << "i" << x.first << "," << x.second << "}";

哈希容器还包括:unordered_multimap / unordered_multiset

自定义哈希函数

1
2
3
4
5
6
#include<functional>
int x;
int HASH = hash<int>() x; // 内置hash类只能对内置类型如int/string/vector等进行哈希值计算

hash<int> H; // hash数据结构重载了()运算符
int HASH = H(x);

对于自定义类型,需要提供自定义的Hash函数。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Type{
int x; string y;
bool operator == (const Type& a) const{ // 重载==,提供判断碰撞的方法
return x == a.x && y = a.y;
}
}
struct HashFunc{ // 函数类,通过"()"重载来当函数使用
std::size_t operator(){const Type &o} const{ // size_t约等于unsigned
return ((hash<int>() (o.x) ^ (hash<string>() (o.y) << 1)) >> 1);
// 通过移位+异或(XOR)获得哈希值
}
}
int main(){
unordered_map<Tpye, string, HashFunc> testHash ={
{ {1, "1"}, "one"},
{ {2, "2"}, "two"},
{ {3, "3"}, "three"}
};
for(const auto& kv : testHash)
cout << kv.first.x << "," << kv.first.y << " - " << kv.second <<endl;
}

STL容器-输出封装(vector/set

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){ // vector输出流
for(int i = 0; i < v.size(); i++)
os<<v[i]<<" ";
return os;
}

template<typename T>
ostream& operator<<(ostream& os, const set<T>& v){ // set输出流
for(typename set<T>::iterator it = v.begin(); it != v.end(); i++)
os<<*it<<" ";
return os;
}

使用方法:

1
2
3
4
vector<int> a; a.push_back(1); a.push_back(2); a.push_back(3);
cout << a; // 输出:1 2 3
set<string> b; b.insert("1"); b.inset("2"); b.insert("3");
cout << b; // 输出:1 2 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_boundupper_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为初始值;
op1op2为可选的广义加法/乘法
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
2
3
4
5
6
7
8
9
10
11
template <typename T>
T func(T a){
T b;
// ...
return b;
}
template <typename T1, typename T2>
struct Map{
T1 key; T2 value;
// ...
}

类型推导 auto

1
2
3
4
5
for (auto i: S) // 简约遍历法
cout<<i<<endl;

for (auto& i: S) // 需要修改时,引用
vis(i);

这种写法中,for循环会从头到尾遍历一遍S容器,将其中的值取出。需要注意的是,如果要修改元素的值的话,应该声明成引用auto& i

需要注意的是,auto关键字是类型推断而不是动态类型,用auto声明的变量必须初始化,并且确定类型后就不能更改。

匿名函数 lambda

函数式编程在需要的地方定义函数,而不是提前定义好才能用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 指明返回类型
auto add = [](int a, int b) -> int { return a + b; };
// 自动推断返回类型
auto multiply = [](int a, int b) { return a * b; };

int sum = add(2, 5); // 输出:7
int product = multiply(2, 5); // 输出:10

// 函数变量
std::function<void(int)> add = [&total](int x) {total += x;};
for_each(begin(list), end(list), add);
// auto自动推导
auto add2 = [&total](int x) {total += x;};
for_each(begin(list), end(list), add2);

// 作为参数的匿名函数
struct TS{int a, b;} tss[105];
sort(tss, tss+100, [](const TS& t1, const TS& t2){
return t1.a != t2.a ? t1.a < t2.a : t1.b < t2.b;
});

int total;
vector<int> list{1,2,3};
for_each(list.begin(), list.end(), [&total](int x) { // 匿名函数,捕捉total
total += x; // 计算累积和
});

空指针 nullptr

NULL宏 = 常整数0nullptr关键字代表值类型std::nullptr_t,语义上可理解为空指针。

1
2
char *p = nullptr;
if(p) // 可以转换为bool的false