『C++』标准模板库(STL)之容器篇
鄙人认为 C++ 相比 C 最大的更新就是内置的 STL 了,里面封装了一堆好用的容器,而不用关心其内部实现的原理和具体代码,十分方便快捷,除了容器外还有一堆算法,这个在下一篇会讲
本文仅记录我认为比较常用的容器,例如 pair
这种比较鸡肋的就不记录了
注意:使用 STL 必须要定义命名空间,例如
using namespace std;
Vector
vector
直译为“向量”,但是一般当成可变长的数组用
众所周知,C/C++ 中的数组一旦定义就无法改变长度,而 vector
就可以解决这个问题,但是代价也是明显的:运行速度更慢
记得使用 #include <vector>
来引入头文件
定义
1 | vector<typename> name; |
以上定义相当于定义了一个一维数组 name[size]
,但是 size
不确定,其长度可以根据需要而变化。其中 typename
可以是任何基本类型,例如 int
、 double
、char
、结构体等,也可以套娃 STL 标准容器,例如 vector
、 queue
等
访问
使用下标
这就像是访问传统的数组一样,非常方便,例:
1 | vector<int> v; |
注意:
- 不能越界,不然会报错
- 这种方法仅限于访问,不能通过它来修改
使用迭代器
可以将迭代器(iterator
)理解为一种类似指针的变量。其定义为:vector<typename>::iterator it;
,例:
1 | vector<int>::iterator it= v.begin(); |
常用方法
push_back(x)
:在后面添加一个元素x
,时间复杂度为 O(1)size()
: 用来获得元素的个数pop_back()
:弹出尾元素,时间复杂度为 O(1)clear()
:清空所有元素,时间复杂度为 O(n)insert(it,x)
:在迭代器it
处插入一个元素x
,时间复杂度为 O(n)erase()
:删除元素,使用erase(it)
删除迭代器it
处的元素(时间复杂度为 O(1)),或使用erase(first,last)
删除左闭右开区间[first,last)
内的所有元素(时间复杂度为 O(last-first))
Stack
stack
翻译为栈,是一种“后进先出”的容器,只能通过 top()
和 pop()
来访问栈顶元素
记得使用 #include <stack>
来引入头文件
定义
1 | stack<typename> name; |
类似地,typename
可以是任何基本类型或者容器,name
是栈的名字
常用方法
push(x)
:将x
压入栈,时间复杂度为 O(1)top()
:获得栈顶元素(但不删除),时间复杂度为 O(1)pop()
:弹出栈顶元素,时间复杂度为 O(1)empty()
:检测是否为空,空返回true
,否则返回false
,时间复杂度为 O(1)size()
:返回元素个数,时间复杂度为 O(1)
Queue
queue
翻译为队列,是一种“先进先出”的容器,只能通过函数 front()
来访问队首元素,或通过函数 back()
来访问队尾元素
记得使用 #include <queue>
来引入头文件
定义
1 | queue<typename> name; |
其中,typename
可以是任何基本类型或者容器,name
为队列的名字
常用方法
push(x)
:将x
入队,时间复杂度为 O(1)front()
:获取队首元素,时间复杂度为 O(1)back()
:获取队尾元素,时间复杂度为 O(1)pop()
:让队首元素出队,时间复杂度为 O(1)empty()
:检测是否为空,空返回true
,否则返回false
,时间复杂度为 O(1)size()
:返回元素个数,时间复杂度为 O(1)
priority_queue
STL 中还有两种容器与队列有关,分别是双端队列(deque
)和优先队列(priority_queue
)
但是用的最多的还是优先队列,简单的说就是可以同时帮你在内部排序的队列
基本定义式与一般队列相似,但如果要指定排序方向,则需要复杂一点,请看下面的两个实例
1 | priority_queue<int> q; |
第二种定义方式的尖括号内多出了 2 个参数:一个是 vector<int>
, 表示的是承载底层数据结构——堆(heap
)的容器,其类型要与第 1 个参数一致;另一个是 less<int>
,是对第 1 个参数的比较类, less<int>
表示数字越大的优先级越大(大根堆),而如果用 greater<int>
则表示数字越小的优先级越大(小根堆)
一定要记得 less
是大在前, greater
是小在前
而默认的就是大在前,所以这两个定义其实是一样的
它的方法与 queue
大同小异,但是也有不同:
push()
方法的时间复杂度提升为 ,毕竟内部要排序- 没有了
front()
和back()
方法,只能通过top()
或pop()
访问队首元素
Map
map
翻译为映射,是STL中的常用容器。其实,数组就是一种映射,比如:int a[100];
就是定义了一个 int
到 int
的映射。而 a[5]=25;
就是把 5 映射到 25。数组总是将 int
类型映射到其它基本类型(称为数组的基类型),这同时也带来了一个问题,有时候我们希望把 string
映射成一个 int
,数组就不方便了。这时就可以使用 map
,map
可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器)
记得使用 #include <map>
来引入头文件
定义
1 | map<typename1,typename2> name; |
其中,typename1
是映射前的类型(键 key
),typename2
是映射后的类型(值 value
),name
为映射的名字
访问
和 vector 类似,有下标和迭代器两种方法
使用下标
通过下标访问就像普通的数组元素访问,例如先定义 map<char,int> mp
,然后就可以通过 mp['c']
的方式来访问它对应的元素,如 mp['c']=124
与 vector 不同,你可以用这种方法直接添加键值对
使用迭代器
通过迭代器访问,先作如下定义:map<typename1,typename2>::iterator it;
因为 map 的每一对映射都有两个 typename
,所以,我们使用 it->first
来访问键,而使用 it->second
来访问值
常用方法
find(key)
:返回键为key
的映射的迭代器,时间复杂度为 O( )size()
:获得映射的对数,时间复杂度为 O(1)clear()
:清空所有映射,时间复杂度为 O(n)erase()
:与 vector 中的相同:删除元素,使用erase(it)
删除迭代器it
指向的元素(时间复杂度为 O(1)),或使用erase(first,last)
删除左闭右开区间[first,last)
内的所有元素(时间复杂度为 O(last-first)),但是还多了一个用法:erase(key)
,时间复杂度为 O( )
Set
set
翻译为集合,是一个内部自动有序且不含重复元素的容器。set
最主要的作用就是自动去重并按升序排序,因此遇到需要去重但是又不方便直接开数组的情况。set
中的元素是唯一的,其内部采用“红黑树”实现
记得使用 #include <map>
来引入头文件
定义
方法一
基础模板
1 | set<typename> name; |
其中,typename
可以是任何基本类型或者容器,name
是集合的名字
当然有些时候会定义 set 数组,例如:set<int> st[100];
,这样 st[0]~st[99]
中的每一个元素都是一个 set 容器
方法二
直接通过花括号枚举我们要传入set
的值
1 | set<string> st{"good", "bad", "medium"}; |
方法三
从其他结构导入元素
1 | set<string> st{"good", "bad", "medium"}; |
1 | int myints[] = {75,23,65,42,13}; |
访问
set 只能通过迭代器访问。即先定义一个迭代器:set<typename>::iterator it;
然后使用 *it
来访问 set 中的元素,例:
1 | for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it) |
注意 set 不支持 *(it+i)
或 it < st.end()
的访问方式(实际上除了 vector 和 string 之外的 STL 容器都不支持)
常用方法
-
insert(x)
-
find(value)
:返回对应值为value
的迭代器,时间复杂度为 O( ) -
size()
:获得元素个数,时间复杂度为 O(1) -
clear()
:清空所有元素,时间复杂度为 O(n) -
erase()
:与 map 相同,有三种用法
erase(it)
,删除迭代器it
指向的元素(时间复杂度为 O(1)),erase(first,last)
, 删除左闭右开区间[first,last)
内的所有元素(时间复杂度为 O(last-first))erase(value)
,时间复杂度为 O( )
String
在 C 中,一般使用字符数组 char str[]
来存放字符串,但是操作麻烦,容易出错。C++ 在 STL 中加入了 string
类型,对字符串常用的需求功能进行了封装,使得操作起来更加方便,且不必担心内存是否足够、字符串的长度等问题
定义
1 | string name; |
其中 name
是字符串变量的名字
当然,你也可以当场就初始化,例如:
1 | string str="abcd" |
访问
使用下标
就像普通字符数组一样操作,非常方便
1 | string str= "abcd" ; |
使用迭代器
先定义 string 迭代器 string::iterator it
,然后就可以通过 *it
来访问 string 里的每一个字符了,例:
1 | string str="abcdefg"; |
输入输出
如果要读入或者输出整个字符串,一般只能用 cin
和 cout
,如果非要用printf
输出 string
,则需要用 c_str()
方法将 string 转换成字符数组,例如:
1 | string str; |
运算
string 可以使用 +
来连接两个字符串,大小比较也是可以使用的
常用方法
-
length()
和size()
:求长度,时间复杂度为 O(1)(?),二者完全相同 -
clear()
:清空,时间复杂度为 O(1) (鄙人疑惑:为什么不是 O(n)) -
substr(pos,len)
:返回从pos
号位置开始、长度为len
的子串,时间复杂度为 O(n) -
insert ()
:有多种写法,时间复杂度都是 O(n)
insert(pos,string)
:在pos
号位置插入字符串string
insert(it,it2,it3)
:it
为原字符串的欲插入位置,it2
和it3
为待插入字符串的首尾迭代器(左闭右开区间)
-
erase()
:erase(it)
,删除迭代器it
指向的元素(时间复杂度为 O(1)),erase(first,last)
, 删除左闭右开区间[first,last)
内的所有元素(时间复杂度为 O(last-first))erase(pos,length)
,从pos
位置开始删length
个字符(时间复杂度为 O(length))
-
find()
:两种写法,时间复杂度都是 O(n*m)
str.find(str2)
,当str2
是str
的子串时,返回其在str
中第一次出现的位置;否则返回string::npos
。string::npos
是一个常数,其本身的值等于 -1,但由于是unsigned int
类型,因此,也可以认为是unsigned int
类型的最大值str.find(str2,pos)
,是从str
的pos
号位开始匹配str2
,返回值同上
-
replace()
:两种写法,时间复杂度都是 O(str.length)
str.replace(pos,len,str2)
:表示把str
从pos
号位开始、长度为len
的子串替换为str2
str.replace(it1,it2,str2)
:表示把str
的迭代器it1
~it2
范围内(左闭右开区间)的子串替换为str2