C++部分基础 与 STL 写在前面: 本文仅针对C++STL进行基础展开, 包含许多容器的基础用法 及 基础函数. 额外的, 若无特殊说明, 文中涉及到的复杂度, 默认为时间复杂度, 且是均摊意义上的. 复杂度中的 n n n默认为大小/长度,l o g log log默认为 l o g 2 log_2 log2?, 其余变量均认为与 n n n同阶.
1. 引用 and 模版 1). 引用 &: 类似指针. 可以理解为给某个变量起了别名.
特别的: 一旦引用某个变量后, 不可再修改(不同于指针).
2). 模版类 常规类变量定义方式: className variableName;
【总结|STL讲课讲义】模版类变量定义方式: className variableName;
3). 模版函数 常规函数调用方式: functionName(parameter…);
模版函数调用方式: functionName(parameter…);
2. string 字符串 常用函数

设字符串长度为 n n n.
string::npos: 定义在头文件内, 值为ULONG_MAX. 其中::称为作用域运算符.

函数名	作用	参数说明	复杂度	备注
size() / length()	得到字符串长度	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示字符串长度.
empty()	判断字符串是否为空	NULL	O ( 1 ) O(1) O(1)	返回值为bool类型. 为空返回 1 1 1, 否则返回 0 0 0
find(str)	查找某个字符串是否出现	传入一个字符串	O ( n 2 ) O(n^2) O(n2)	返回值为UL类型. 表示找查字符串str第一次在原串中出现的下标. 若找不到, 则返回string::npos.
c_str()	返回一个const char*类型字符串	NULL	O ( n ) O(n) O(n)	常用于以C语言方式输出string内容
pop_back()	删除最后一个字符	NULL	O ( 1 ) O(1) O(1)	NULL

关于find()函数, 很多人喜欢通过 判断返回值是否为 ? 1 -1 ?1来判断是否出现过该字符串, 这种写法可以做到正确的判断.
原因:? 1 -1 ?1是int类型, 当find()找不到时, 其返回值是unsigned long类型的最大值, 在二者比较时, 会隐式转化为UL进行比较, 两者的值的确是相同的(此处推荐以计算机存储数据的二进制补码形式去想). 什么? 在您的电脑上不相等? 那您的机器一定老有收藏价值了!

额外的, 通过str[index]来访问位于 i n d e x index index位置的字符.
可通过> < >= <= ==来比较字符串字典序等.
Tips: string也是支持迭代器的.
容器适配器 1. queue 单向队列 用于存放需要顺序执行的进程.
定义: queue<类型名> 变量名;
常用函数

函数名	作用	参数说明	复杂度	备注
size()	得到队列长度	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示队列中元素个数.
empty()	判断队列是否为空	NULL	O ( 1 ) O(1) O(1)	返回值为bool类型. 为空返回 1 1 1, 否则返回 0 0 0
push(val)	把元素存入队尾	传入要存入队列的值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
pop()	删除队首元素	NULL	O ( 1 ) O(1) O(1)	NULL
front()	得到队首元素	NULL	O ( 1 ) O(1) O(1)	只取出该元素, 并不会从队列中删除该元素. 需要用pop()函数手动删除.

2. stack 栈 用于存放需要递归执行的进程
定义: stack<类型名> 变量名;
常用函数

函数名	作用	参数说明	复杂度	备注
size()	得到栈大小	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示栈中元素个数.
empty()	判断栈是否为空	NULL	O ( 1 ) O(1) O(1)	返回值为bool类型. 为空返回 1 1 1, 否则返回 0 0 0
push(val)	把元素存入栈顶	传入要存入栈的值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
pop()	删除栈顶元素	NULL	O ( 1 ) O(1) O(1)	NULL
top()	得到栈顶元素	NULL	O ( 1 ) O(1) O(1)	只是取出该元素, 并不会从栈中删除该元素, 需要用pop()函数手动删除.

3. priority_queue 优先队列/堆 类似于普通队列, 但是会自动按照优先级从高到低排序队列内元素.
定义: priority_queue<类型名> 变量名;
常用函数

函数名	作用	参数说明	复杂度	备注
size()	得到堆大小	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示堆中元素个数.
empty()	判断堆是否为空	NULL	O ( 1 ) O(1) O(1)	返回值为bool类型. 为空返回 1 1 1, 否则返回 0 0 0
push(val)	把元素存入堆中	传入要存入堆的值	O ( l o g n ) O(logn) O(logn)	若传入变量, 相当于是以值传递的形式进行存储.
pop()	删除堆顶元素	NULL	O ( l o g n ) O(logn) O(logn)	NULL
top()	得到堆顶元素	NULL	O ( 1 ) O(1) O(1)	只取出该元素, 并不会从堆中删除该元素. 需要用pop()函数手动删除.

顺序容器 0. 迭代器 0). 迭代器用法 ? 迭代器的定义: 容器类名::iterator 变量名;
? 迭代器的访问: *迭代器变量

可以把迭代器看作指针, 只不过针对于STL, 起了个不一样的名字.

1). 双向迭代器 可以双向移动的迭代器. 对于当前迭代器而言, 每次只能移动到其前一个迭代器, 或后一个迭代器.
2). 随机访问迭代器 随机访问迭代器是可以随机访问容器中的元素的双向迭代器. 对于当前迭代器而言, 可以向前, 向后移动任意多个迭代器.
3). 容器中迭代器的获取方式 支持迭代器的容器可以通过begin(), end()函数分别得到首尾迭代器,
特别的, 部分类函数也会以迭代器作为返回值.

函数名	作用	复杂度	备注
begin()	得到首迭代器	O ( 1 ) O(1) O(1)	NULL
end()	得到尾迭代器	O ( 1 ) O(1) O(1)	该函数所返回的尾迭代器, 实质是指向容器内尾元素的后一个位置. 该位置不应该被访问到, 否则会出错.

我们可以通过迭代器遍历 [ b e g i n , e n d ) [begin, end) [begin,end)来遍历整个容器.
特别的, 通常情况下, 请使用前缀运算符来移动迭代器, 这样可以避免临时变量的产生, 从而加快程序运行速度.

1. vector 可变长数组 顺序容器的一种, 迭代器类型为随机访问迭代器.
定义: vector<类型名> 变量名;
常用函数

函数名	作用	参数说明	复杂度	备注
size()	得到数组长度	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示数组中元素个数.
push_back(val)	向数组末端添加元素	传入要存入数组的值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
pop_back()	删除数组末端元素.	NULL	O ( 1 ) O(1) O(1)	NULL
clear()	清空整个数组	NULL	O ( n ) O(n) O(n)	NULL

额外的, 同于普通数组, 我们也可以通过[]来访问数组中元素, 下标从 0 0 0开始.

常见错误: vector并不同于常规的静态数组, 其内部的空间必须先开辟, 后使用.

2. deque 双向队列 顺序容器的一种, 迭代器类型为随机访问迭代器.
可以看作是一个支持双向操作的vector. (虽然叫双向队列, 但或许叫"双向数组"更贴切一些).
定义: deque<类型名> 变量名;
常用函数

函数名	作用	参数说明	复杂度	备注
size()	得到数组长度	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示数组中元素个数.
push_back(val)	向数组末端添加元素	传入要存入数组的值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
pop_back()	删除数组末端元素.	NULL	O ( 1 ) O(1) O(1)	NULL
push_front(val)	向数组首端添加元素	传入要存入数组的值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
pop_front()	删除数组首端元素.	NULL	O ( 1 ) O(1) O(1)	NULL
clear()	清空整个数组	NULL	O ( n ) O(n) O(n)	NULL

额外的: 同样可以通过[]来访问数组中元素, 下标从 0 0 0开始.

常见错误: 双向队列的存储方式并不是直觉上的在内存中线性依次存储, 有可能数组尾端的元素在内存地址较小的位置. 因此在访问迭代器时, 谨防越界.

3. list 双向链表 顺序容器的一种, 迭代器类型为双向迭代器.
定义: list<类型名> 变量名;
常用函数

函数名	作用	参数说明	复杂度	备注
size()	得到链表长度	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示链表中元素个数.
push_back(val)	向链表末端添加元素	传入要存入数组的值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
pop_back()	删除链表末端元素.	NULL	O ( 1 ) O(1) O(1)	NULL
push_front(val)	向链表首端添加元素	传入要存入数组的值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
pop_front()	删除链表首端元素.	NULL	O ( 1 ) O(1) O(1)	NULL
insert(it, val)	向链表指定迭代器之前插入元素	传入 迭代器 及 元素值	O ( 1 ) O(1) O(1)	若传入变量, 相当于是以值传递的形式进行存储.
erase(it)	删除链表指定迭代器位置的元素	传入 迭代器	O ( 1 ) O(1) O(1)	NULL
clear()	清空整个链表	NULL	O ( n ) O(n) O(n)	NULL
front()	得到链表首元素	NULL	O ( 1 ) O(1) O(1)	得到的实质上是首元素的引用
back()	得到链表尾元素	NULL	O ( 1 ) O(1) O(1)	得到的实质上是尾元素的引用
sort()	将链表排序	NULL	O ( n l o g n ) O(nlogn) O(nlogn)	NULL
unique()	将有序链表去重	NULL	O ( n ) O(n) O(n)	会自动删除尾部多余的元素
merge(list)	合并两个有序链表	传入需要被合并的链表	O ( n ) O(n) O(n)	会自动清空被合并的链表
reverse()	将链表内元素翻转	NULL	O ( n ) O(n) O(n)	NULL

特别的, 在c++11标准前, size()函数的实现复杂度为 O ( 1 )/O ( n ) O(1) \ / \ O(n) O(1) / O(n).

list并不作为ACM的重点考察, 但是其内部的许多函数均在等头文件内均有通用形式.

关联容器 1. set / multiset 集合 / 可重集合 关联容器的一种, 迭代器类型为双向迭代器.
集合会对其内部元素自动排序, 默认按照less规则排序. 底层实现为红黑树.
定义: set<类型名> 变量名; , multiset<类型名> 变量名;
常用函数(部分函数set与multiset中不同, 标有*的部分应在multiset中特殊注意)

函数名	作用	参数说明	复杂度	备注
size()	得到集合大小	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示集合中元素个数.
clear()	清空整个集合	NULL	O ( n ) O(n) O(n)	NULL
insert(val)	向集合中插入元素	NULL	O ( l o g n ) O(logn) O(logn)	若传入变量, 相当于是以值传递的形式进行存储.
erase(val)	删除集合中等于传入值的元素	传入元素值	O ( l o g n ) O(logn) O(logn)	*会删除全部值为val的元素!
erase(it)	删除集合中位于该迭代器位置的元素	传入迭代器	O ( 1 ) O(1) O(1)	*常用于删除multiset中的单个重复元素.
find(val)	查询集合中是否有等于传入值的元素.	传入元素值	O ( l o g n ) O(logn) O(logn)	*会返回第一个符合条件的迭代器. 若找不到, 则返回end迭代器
count(val)	查询集合中等于传入值的元素个数	传入元素值	O ( l o g n ) O(logn) O(logn)	*返回UL类型. 在set中, 结果只会是 0 / 1 0/1 0/1
lower_bound(val)	查询集合中第一个大于等于传入值的元素	传入元素值	O ( l o g n ) O(logn) O(logn)	返回迭代器. 若找不到则返回end迭代器.
upper_bound(val)	查询集合中第一个严格大于传入值的元素	传入元素值	O ( l o g n ) O(logn) O(logn)	返回迭代器. 若找不到则返回end迭代器.

0. pair 对组 / 二元组 不属于关联容器.
作用: 把两种类型结合成一种新类型.

当然, 结构体可以做的更为广泛. 你可以把pair理解为一个仅有两种类型的结构体.

定义: pair variableName;
访问: 通过 变量名.first访问第一个类型, 变量名.second访问第二个类型. (会返回它们的引用)

相当于一个结构体内部两个变量依次叫first second.

特别的: 可以通过函数make_pair(parameter1, parameter2)得到一个pair类型.
2. map / multimap 映射 / 可重映射 (字典) 关联容器的一种, 迭代器类型为双向迭代器.
映射同样会对其内部元素按照 k e y key key值自动排序, 默认按照less规则排序. 底层实现同样为红黑树.
映射内存储一个二元组pair, pair的 f i r s t first first称为 m a p map map的 k e y key key值,s e c o n d second second称为 m a p map map的 v a l u e value value值,
定义: map<类型名, 类型名> 变量名;
常用函数 (函数参数是针对于 k e y key key值而言, 标有*的部分应在multimap中特殊注意)

函数名	作用	参数说明	复杂度	备注
size()	得到映射大小	NULL	O ( 1 ) O(1) O(1)	返回值为UL类型, 表示映射中元素个数.
clear()	清空整个映射	NULL	O ( n ) O(n) O(n)	NULL
insert(val)	向映射中插入元素	NULL	O ( l o g n ) O(logn) O(logn)	插入的应是一个 ( k e y , v a l u e ) (key, value) (key,value)二元组
erase(val)	删除映射中等于传入值的元素	传入元素值	O ( l o g n ) O(logn) O(logn)	*会删除全部值为val的元素!
erase(it)	删除映射中位于该迭代器位置的元素	传入迭代器	O ( 1 ) O(1) O(1)	*常用于删除multimap中的单个重复元素.
find(val)	查询映射中是否有等于传入值的元素.	传入元素值	O ( l o g n ) O(logn) O(logn)	*会返回第一个符合条件的迭代器. 若找不到, 则返回end迭代器
count(val)	查询映射中等于传入值的元素个数	传入元素值	O ( l o g n ) O(logn) O(logn)	*返回UL类型. 在map中, 结果只会是 0 / 1 0/1 0/1
lower_bound(val)	查询映射中第一个大于等于传入值的元素	传入元素值	O ( l o g n ) O(logn) O(logn)	返回迭代器. 若找不到则返回end迭代器.
upper_bound(val)	查询映射中第一个严格大于传入值的元素	传入元素值	O ( l o g n ) O(logn) O(logn)	返回迭代器. 若找不到则返回end迭代器.

额外的, 在map中, 我们可以使用[key]来完成访问 v a l val val, 复杂度为 O ( l o g n ) O(logn) O(logn).
但在multimap中, 由于元素可重复, 我们只能通过 f i n d find find函数找到迭代器后, 再进行访问.
当使用[key]访问map时, 若映射中不存在该 k e y key key值, 则会自动添加该 k e y key key值至map中.

END

推荐阅读

• 

  什么是碱性岩
• 

  洛阳奥斯卡影院6月13号放映什么电影？洛阳奥斯卡影院今日放映表
• 

  京东“京银计划” 是什么 怎么参与？
• 

  共栅极放大电路分析,场效应管共栅极放大电路
• 

  2022年三伏天时间表？
• 

  活珠子不适合哪些人吃
• 

  m当前“最接近完美”的五款手机，别看价格贵，用三年毫无压力
• 

  上海电商有哪些 什么是电商上海，什么是电商上海人
• 

  家用茶具多少钱的合适 – 高档茶盘图片价格表
• 

  冰箱不结冰是怎么回事？原因分析与解决方法
• 

  热水器不烧水怎么办,是因为这些原因
• 

  增加注册资本后股东的股权比例
• 

  白发傅筹第几集知道身世
• 

  CPB水前肌底精华好不好？CPB水前肌底精华怎么用
• 

  兄弟T310如何清零废墨？
• 

  炒杜仲与生杜仲的区别 炒杜仲与生杜仲的不同之处
• 

  《侠客风云传前传》激活方法及特权简单介绍
• 

  取暖器品牌排名？哪个比较好的？
• 

  中风|女性中风有奇特症状？盘点易被女性忽视的11个中风症状！
• 

  减肥可以吃红枣吗

• 历年真题|2018CCPC桂林站 G. Greatest Common Divisor (gcd 差分 质因数分解)
• 算法|2020年10月份蓝桥杯省赛B组C++题解
• Codeforces|Codeforces940F Machine Learning (带修莫队)
• Codeforces|Codeforces126B Password (KMP)
• 总结|关于c++中的临时变量
• 竞赛习题|蓝桥杯第十二届个人省赛C/C++B组（欢迎大家在底部评论留下自己疑问）
• 蓝桥杯|2018年蓝桥杯省赛 C++ B组
• 算法练习|2022年蓝桥杯（第十三届蓝桥杯大赛软件赛省赛C/C++大学B组真题（考后回顾））
• 题解|第十三届蓝桥杯大赛软件赛省赛B组(个人思路)