思维之海

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

C++学习手册

In Views: Valine:

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

网络工具综合学习网站：Runoob。

References

C++Primer

面向对象程序设计（C++）（自主模式）

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

流 stream

iostream: istream+ostream.

  • istream：cin对象
    • 输入运算符>>
  • ostream：cout对象。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_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
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宏 = 常整数0。nullptr关键字代表值类型std::nullptr_t，语义上可理解为空指针。

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