标准库
底层数据类型
容器类型 |
容器名 |
底层数据类型 |
能否随机访问 |
使当前位置的迭代器失效 |
使后续的迭代器失效 |
|---|---|---|---|---|---|
顺序型容器 |
vector |
数组 |
是 |
是 |
是 |
顺序型容器 |
deque |
分散的储存块 |
是 |
是 |
是 |
顺序型容器 |
list |
双向链表 |
否 |
是 |
否 |
关联容器 |
set |
红黑树 |
否 |
是 |
否 |
关联器 |
multiset |
红黑树 |
否 |
是 |
否 |
关联容器 |
map |
红黑树 |
否 |
是 |
否 |
关联容器 |
multimap |
红黑树 |
否 |
是 |
否 |
容器适配器 |
stack |
||||
容器适配器 |
queue |
||||
容器适配器 |
priority_queue |
是 |
vector 相当于动态数组，当容量不够时会重新申请一块足够大的空间，然后将数据复制过去。因此，在大量插入数据前要使用 reserve 预留空间，否则性能较差
list 是一个单向链表，插入和删除节点非常方便，但是不允许随机访问
deque 是双端队列，底层是链表，但是链表的节点是可以容纳若干个元素的内存块。允许随机访问
关联容器的底层都是红黑树。其中 set 要求值唯一（和数学定义一样），而 map 要求键值唯一，multimap 和 multiset 允许出现重复的键值。而且元素是有序的。关联容器的插入和删除性能优于 vector 劣于 list。
容器适配器对存储的容器有要求。 stack 和队列需要顺序容器，队列要求容器允许前端插入，优先队列要求提供随机访问能力
stack 默认情况下使用双端队列，
由于 erease 或者 insert 会返回下一个有效的迭代器，因此在使用迭代器擦除或插入元素后可以使用迭代器接受返回值以得到下一个可用的迭代器
对于只会导致当前迭代器失效的容器而言，删除元素可以使用 erease(it++) 。尤其是对于关联容器而言其 erease 的方法返回值为 void
在使用迭代器的时候一定要注意迭代器失效的问题，例如：
for(int i = 0; i < arr.size(); ++i) {
arr.erase(arr.begin() + i);
}
就会导致迭代器越界出现段错误的问题
Vector容器的扩容原理（1.5倍扩容，扩容后迭代器失效）
迭代器
迭代器指向的是一个左闭右开的区间，这点在进行 erase、substr 等操作时一定要注意。区间的大小是 end - begin - 1。
迭代器可以配合以下情形：
函数 |
作用 |
|---|---|
remove |
将需要删除的元素 移动 到容器末尾，返回值为第一个需要删除的元素 |
count_if |
对容器内指定的值进行计数 |
一个常见的用法是：
arr.erase(remove(arr.begin(), arr.end(), val), arr.end());
字符串
字符串的构造函数如下：
构造函数 |
作用 |
|---|---|
string(const char*s) |
复制 s 的内容以初始化 string |
string(Iter begin, Iter end) |
复制 [begin, end) 中的内容以初始化 |
string(size_t n , char c) |
使用 n 个 c 初始化 |
string(const string& b, size_t start, size_t n) |
使用 b[start, start + n) 初始化 |
string(const char*s, size_t len) |
如果 len 大于 s 长度，多余的长度是随机内容 |
另外有一个用于表示字符串末尾的常量 std::npos，它的值通常为 uint 的最大值。
另外是一些查找函数，这些函数查找失败时返回 std::npos：
函数签名 |
作用 |
|---|---|
find(const string&str, size_t pos) |
从字符串的 pos 开始查找 str 第一次出现时的索引 |
find(const char*, size_t pos) |
|
find(const char* s, size_t pos, size_t n) |
从字符串的 pos 开始，查找 s 的前 n 个字符串 |
rfind |
与上面相似，只是是从后面开始查的 |
find_first_of(const char* s) |
查找 s 中 任一 字符在字符串中第一次出现的位置 |
find_last_of |
与上面相似，只是是从后面开始查的 |
find_first_not_of |
|
adjacent_find |
在指定范围内查找第一个连续相等的元素 |
如果 find 失败，则返回值为 end() 或者 rend()
重要
find_first_of 不是字符串查找函数，而是字符查找函数。但是它也可以接受字符串参数。。。
https://zh.cppreference.com/w/cpp/string/basic_string/find_first_of
常用的字符串处理函数有：
std::string::find |
字符串查找 |
std::string::replace(startPos, OldStr, NewStr) |
字符串替换 |
std::stoi |
字符串转数字 |
std::to_string() |
数字转字符串 |
boost::trim(字符串) |
去除空白字符 |
boost::join(容器, “;”) |
容器转字符串 |
boost::replace_all(操作字符串, 被替换字符串, 新字符串) |
字符串替换 |
boost::split(容器, 待分割的字符串, boost::is_any_of(由分界符构成的字符串)) |
字符串分割 |
boost::erase_all(修改串,需要删除的子串) |
字符串删除 |
fmt::format |
字符串格式化 |
std::string::find 查找失败的返回值是 std::string::npos
对于 boost 中的函数而言，使用 _copy 版本的函数代表着产生一个副本，否则则是在原字符串上修改
std 中的 replace 需要配合 find 使用:
s.find("world"); s = s.replace(startPos, OldStr, NewStr)
对于字符串格式化而言，更加推荐使用 fmt
此外，还有一些辅助函数：
boost::to_upper() |
转为大写 |
boost::to_lower() |
转为小写 |
boost::starts_with() |
判断开头 |
boost::ends_with() |
判断结尾 |
boost::contains() |
判断包含 |
以及一些谓词：
boost::is_space() |
空格 |
boost::is_digit() |
数字 |
参见字符串处理方式
本来是不想写的，因为一般情况下我直接就用 boost 了，但是昨天做题的时候系统输入的内容不是标准的，得自己解析，而且还只能用标准库。当时考试时比较紧张，一直没写出来，后来换 Python 了，今天做个笔记吧。
第一种是截取指定字符串，通常是配合 substr 和 find_first_of 使用的：
// data = "1,2,3,4,5"
while(data.length()) {
auto tracatePos = data.find_first_of(',');
if(tracatePos == string::npos) tracatePos = data.length();
auto tmp = data.substr(0, tracatePos);
arr1.push_back(stoi(tmp));
data.erase(0, tracatePos + 1);
}
string 的 substr 和 erase 实在指定 pos 之前截取的，所以后面使用 erase 的时候需要将 pos + 1
另外一种比较坑的情况是 erase 接受 int 参数，但是行为比较奇怪，往往没法得到正确的结果，正确的方式是使用迭代器
随机数
需要包含头文件 random
对于 Unix 系统而言，标准库提供了指向 /dev/random 的 random_device 用来提供真随机数：
void print(int n) {
for(int i = 0; i < n; ++i) { cout << '*'; }
cout << endl;
}
int main() {
random_device devcie;
for(int i = 0; i < 20; ++i) { print(devcie() % 10 + 1); }
return 0;
}
结果如下:
****
********
**********
******
***
*****
***
******
*****
**********
*******
******
********
*
******
*
*********
***
*****
**********
可见，整体还是比较随机的
如果操作系统内没有 random 设备，就回退到普通的伪随机数引擎。
标准库将随机数生成的工具分为两个部分：引擎和分发器。
引擎可以简单地将其理解为生成随机数的工具，分发器对生成的随机数进行处理，以生成随机的或符合二项分布的或符合泊松分布的随机数
既然说了引擎是生成随机数的工具，实际上引擎是可以直接被调用的。分发器有没有实际上无所谓
引擎 |
作用 |
|---|---|
default_random_engine |
生成结果为 uint 的伪随机数 |
linear_congruential_engine<> |
使用线性同余算法的伪随机数 |
mersenne_twister_engine<> |
使用梅森扭曲算法 |
分发器：
分发器 |
作用 |
|---|---|
uniform_int_distribution |
产生指定范围内的整数 |
uniform_real_distribution |
产生随机范围内的实数 |
bernoulli_distribution |
伯努利分布 |
poisson_distribution |
泊松分布 |
normal_distribution |
正态分布 |
discrete_distribution |
离散分布 |
例如我们使用正态分布：
default_random_engine eng;
normal_distribution<double> dis(1, 10);
for(int i = 0; i < 20; ++i) { print(dis(eng)); }
结果如下:
*******
*
********
*
*****
***
**********************
****
***********
********
**************
常用算法
首先是排序函数：
函数 |
作用 |
|---|---|
sort(begin, end) |
对 [begin, end) 范围内的元素进行排序 |
stable_sort |
稳定排序 |
partial_sort(begin,middle,end) |
从 [begin,end) 中选出 middle-begin 个最小元素放到 [begin, middle) 中 |
partial_sort_copy |
不改变原数组 |
nth_element(begin, nth, end) |
返回升序排序时应当位于 nth 位置的元素 |
sort 数据量大的时候使用快排，分段进行归并排序，分段后如果数据比较少，就用插入排序，如果递归太深，就用堆排序
合并函数
函数 |
作用 |
|---|---|
merge |
将两个有序序列合并成一个 |
inplace_merge(begin, middle, end) |
将有序序列 [begin, middle) 和 [middle, end) 合并成一个 |
二分查找：
函数 |
作用 |
|---|---|
lower_bound |
要求序列升序，查找范围内第一个不小于目标值的元素 |
upper_bound |
要求序列升序，查找范围内第一个大于目标值的元素 |
equel_range |
查找范围内第一个等于目标值的元素 |
binary_search |
查找范围内是否包含目标元素 |
另外是几个谓词：
函数 |
作用 |
|---|---|
all_of |
序列中的元素全部可以使谓词返回 true |
any_of |
|
none_of |
|
equal |
检查两个序列是否相等 |
几个辅助算法：
函数 |
作用 |
|---|---|
unique |
对 有序 序列去重，返回新序列的结束迭代器 |
min |
参数为两个值或者是 容器 |
max_element |
给出最大值的索引 |
next_permutation |
按照字典升序的方式对序列进行全排列，已经达到最大排列时返回 false |
pre_permutation |
按照字典降序的方式对序列进行全排列，已经达到最大排列时返回 false |
emplace_back |
在容器内添加一个元素并就地构造，因此略去了 push_back 构造临时对象的开销 |
shuffle |
洗牌算法，打乱序列的顺序，需要传入随机数引擎 |
常用算法
非修改序列操作
算法 |
作用 |
|---|---|
adjacent_find |
查找两个相邻（Adjacent）的等价（Identical）元素 |
all_of |
(C++11) 检测在给定范围中是否所有元素都满足给定的条件 |
any_of |
(C++11) 检测在给定范围中是否存在元素满足给定条件 |
count |
返回值等价于给定值的元素的个数 |
count_if |
返回值满足给定条件的元素的个数 |
equal |
返回两个范围是否相等 |
find |
返回第一个值等价于给定值的元素 |
find_end |
查找范围 A 中与范围 B 等价的子范围最后出现的位置 |
find_first_of |
查找范围 A 中第一个与范围 B 中任一元素等价的元素的位置 |
find_if |
返回第一个值满足给定条件的元素 |
find_if_not |
(C++11) 返回第一个值不满足给定条件的元素 |
for_each |
对范围中的每个元素调用指定函数 |
mismatch |
返回两个范围中第一个元素不等价的位置 |
none_of |
(C++11) 检测在给定范围中是否不存在元素满足给定的条件 |
search |
在范围 A 中查找第一个与范围 B 等价的子范围的位置 |
search_n |
在给定范围中查找第一个连续 n 个元素都等价于给定值的子范围的位置 |
修改序列操作
算法 |
说明 |
|---|---|
copy |
将一个范围中的元素拷贝到新的位置处 |
copy_backward |
将一个范围中的元素按逆序拷贝到新的位置处 |
copy_if |
(C++11) 将一个范围中满足给定条件的元素拷贝到新的位置处 |
copy_n |
(C++11) 拷贝 n 个元素到新的位置处 |
fill |
将一个范围的元素赋值为给定值 |
fill_n |
将某个位置开始的 n 个元素赋值为给定值 |
generate |
将一个函数的执行结果保存到指定范围的元素中，用于批量赋值范围中的元素 |
generate_n |
将一个函数的执行结果保存到指定位置开始的 n 个元素中 |
iter_swap |
交换两个迭代器（Iterator）指向的元素 |
move |
(C++11) 将一个范围中的元素移动到新的位置处 |
move_backward |
(C++11) 将一个范围中的元素按逆序移动到新的位置处 |
random_shuffle |
随机打乱指定范围中的元素的位置 |
remove |
将一个范围中值等价于给定值的元素删除 |
remove_if |
将一个范围中值满足给定条件的元素删除 |
remove_copy |
拷贝一个范围的元素，将其中值等价于给定值的元素删除 |
remove_copy_if |
拷贝一个范围的元素，将其中值满足给定条件的元素删除 |
replace |
将一个范围中值等价于给定值的元素赋值为新的值 |
replace_copy |
拷贝一个范围的元素，将其中值等价于给定值的元素赋值为新的值 |
replace_copy_if |
拷贝一个范围的元素，将其中值满足给定条件的元素赋值为新的值 |
replace_if |
将一个范围中值满足给定条件的元素赋值为新的值 |
reverse |
反转排序指定范围中的元素 |
reverse_copy |
拷贝指定范围的反转排序结果 |
rotate |
循环移动指定范围中的元素 |
rotate_copy |
拷贝指定范围的循环移动结果 |
shuffle |
(C++11) 用指定的随机数引擎随机打乱指定范围中的元素的位置 |
swap |
交换两个对象的值 |
swap_ranges |
交换两个范围的元素 |
transform |
对指定范围中的每个元素调用某个函数以改变元素的值 |
unique |
删除指定范围中的所有连续重复元素，仅仅留下每组等值元素中的第一个元素。 |
unique_copy |
拷贝指定范围的唯一化（参考上述的 unique）结果 |
划分
算法 |
作用 |
|---|---|
is_partitioned |
(C++11) 检测某个范围是否按指定谓词（Predicate）划分过 |
partition |
将某个范围划分为两组 |
partition_copy |
(C++11) 拷贝指定范围的划分结果 |
partition_point |
(C++11) 返回被划分范围的划分点 |
stable_partition |
稳定划分，两组元素各维持相对顺序 |
排序
算法 |
作用 |
|---|---|
is_sorted |
(C++11) 检测指定范围是否已排序 |
is_sorted_until |
(C++11) 返回最大已排序子范围 |
nth_element |
部份排序指定范围中的元素，使得范围按给定位置处的元素划分 |
partial_sort |
部份排序 |
partial_sort_copy |
拷贝部分排序的结果 |
sort |
排序（快速排序） |
stable_sort |
稳定排序 |
二分法查找（用于已划分/已排序的序列）
算法 |
作用 |
|---|---|
binary_search |
判断范围中是否存在值等价于给定值的元素 |
equal_range |
返回范围中值等于给定值的元素组成的子范围 |
lower_bound |
返回指向范围中第一个值大于或等于给定值的元素的迭代器 |
upper_bound |
返回指向范围中第一个值大于给定值的元素的迭代器 |
合并（用于已排序的序列）
算法 |
作用 |
|---|---|
includes |
判断一个集合是否是另一个集合的子集 |
inplace_merge |
就绪合并 |
merge |
合并 |
set_difference |
获得两个集合的差集 |
set_intersection |
获得两个集合的交集 |
set_symmetric_difference |
获得两个集合的对称差 |
set_union |
获得两个集合的并集 |
堆
算法 |
作用 |
|---|---|
is_heap |
检测给定范围是否满足堆结构 |
is_heap_until |
(C++11) 检测给定范围中满足堆结构的最大子范围 |
make_heap |
用给定范围构造出一个堆 |
pop_heap |
从一个堆中删除最大的元素 |
push_heap |
向堆中增加一个元素 |
sort_heap |
将满足堆结构的范围排序 |
最大/最小值
算法 |
作用 |
|---|---|
is_permutation |
(C++11) 判断一个序列是否是另一个序列的一种排序 |
max |
返回两个元素中值最大的元素 |
max_element |
返回给定范围中值最大的元素 |
min |
返回两个元素中值最小的元素 |
min_element |
返回给定范围中值最小的元素 |
minmax |
(C++11) 返回两个元素中值最大及最小的元素 |
minmax_element |
(C++11) 返回给定范围中值最大及最小的元素 |
其他
算法 |
作用 |
|---|---|
lexicographical_compare |
比较两个序列的字典序 |
next_permutation |
返回给定范围中的元素组成的下一个按字典序的排列 |
prev_permutation |
返回给定范围中的元素组成的上一个按字典序的排列 |