C++ STL 用法解释

C++ STL

vector 数组

• 声明：容器类型<变量类型> 名称

#include

vector<int> vec;

vector<char> vec;

vector<pair<int,int> > vec;

vector<node> vec;

struct node{...};
1
2
3
4
5
6
7
8
9
10
11

• 使用方法

vector 容器是支持随机访问的，即可以像数组一样用[ ]来取值。

---

string 字符串

使用：需要包含头文件

#include 
#include 
using namespace std;
int main(){
    string s1;
    string s2 = "c plus plus";
    string s3 = s2;
    string s4 (5, 's');
    return 0;
}
1
2
3
4
5
6
7
8
9
10

使用方法：

---

queue

queue 队列

• 声明：容器类型<变量类型> 名称

#include

queue<int> q;

queue<char> q;

queue<pair<int,int> > q;

queue<node> q;

struct node{...};
1
2
3
4
5
6
7
8
9
10
11

• 使用方法

​ queue 不支持随机访问，即不能像数组一样地任意取值。比如 queue 不可以用 clear()函数清空，清空queue必须一个一个弹出。同样，queue也并不支持遍历，无论是数组型遍历还是迭代器型遍历统统不支持，所以没有begin(),end()函数。

---

stack 栈

• 声明：容器类型<变量类型> 名称

#include

stack<int> stk;
stack<char> stk;
stack<pair<int,int> > stk;
stack<node> stk;
struct node{...};
1
2
3
4
5
6
7

• 使用方法

---

priority_queue 优先队列

​ 优先队列就是在普通队列的基础上，把其中的元素加以排序。其内部实现是一个二叉堆。所以优先队列其实就是把堆模板化，将所有入队的元素排成具有单调性的一队，方便调用。

大根堆

​ 大根堆就是把大的元素放在堆顶的堆。优先队列默认实现的就是大根堆，所以大根堆的声明直接按C++ STL 的声明规则声明即可。

#include

priority_queue<int> q;

priority_queue<string> q;

priority_queue<pair<int,int> > q;
1
2
3
4
5
6
7

​ C++ 中的 int , string 等类型可以直接比较大小，优先队列自然会帮我们实现。但是如果是我们自己定义的结构体，就需要进行重载运算符了。

小根堆

​ 大根堆是把大的元素放堆顶，小根堆就是把小的元素放到堆顶。

实现方式：

• 第一种是比较巧妙的，因为优先队列默认实现的是大根堆，所以我们可以把元素取反放进去，因为负数的绝对值越小越大，那么绝对值较小的元素就会被放在前面，我们在取出的时候再取个反，就瞒天过海地用大根堆实现了小根堆。

• 小根堆有自己的声明方式

  priority_queue<int,vector<int>,greater<int> >q;
  1

  注意，当我们声明的时候碰到两个"<“或者”>"放在一起的时候，一定要记得在中间加一个空格。这样编译器才不会把两个连在一起的符号判断成位运算的左移/右移。

使用方法

注意：priority_queue 取出队首元素是使用top ，而不是 front，这点一定要注意！！

---

deque 双端队列

​ deque 的意义是：双端队列。C++ STL 中的确有模拟队列的模板：#include中的queue 和priority_queue 。队列的性质是先进先出，即从队尾入队，从队首出队。而 deque 的特点则是双端进出，即处于双端队列中的元素既可以从队首进/出队，也可以从队尾进/出队。

即：deque 是一个支持在两端高效插入、删除元素的线性容器。

deque 模板存储在 C++ STL 的#include中。

• 用法

除了这些用法之外，deque 比 queue 更优秀的一个性质是它支持随机访问，即可以像数组下标一样取出其中的一个元素。 即：q[i]。

---

set

set 集合

​ set 容器的功用就是维护一个集合，其中的元素满足互异性。我们可以将其理解为一个数组。这个数组的元素是两两不同的。

​ 这个两两不同是指，如果这个set容器中已经包含了一个元素 i，那么无论我们后续再往里假如多少个 i ，这个 set 中还是只有一个元素 i，而不会出现一堆 i 的情况。

​ 但是，需要额外说明的是，刚刚说集合是有无序性的，但是 set 中的元素是默认排好序**（按升序排列）**的。（稍微说一句，set 容器自动有序和快速添加、删除的性质是由其内部实现：红黑树（平衡树的一种）。

• 声明：容器名<变量类型> 名称

#include

set<int> s;

set<char> s;

set<pair<int,int> > s;

set<node> s;

struct node{...};
1
2
3
4
5
6
7
8
9
10
11

• 使用方法

multiset 有序多重集合

​ multiset 的很多性质和使用方式和 set 容器差不了多少。而 multiset 容器在概念上与 set 容器不同的地方就是：set 的元素互不相同，而 multiset 的元素可以允许相同。

与set容器不太一样的地方

s.erase(k);
1

erase(k) 函数在 set 容器中表示删除集合中元素 k 。但在 multiset 容器中表示删除所有等于 k 的元素。

时间复杂度变成了O(tot+logn) ，其中 tot 表示要删除的元素的个数。

那么，会存在一种情况，我只想删除这些元素中的一个元素，怎么办呢？

可以妙用一下：

if( (it=s.find(a))!=s.end() )
	s.erase(it);
1
2

​ if 中的条件语句表示定义了一个指向一个 a 元素迭代器，如果这个迭代器不等于 s.end() ，就说明这个元素的确存在，就可以直接删除这个迭代器指向的元素了。

s.count(k);
1

​ count(k) 函数返回集合中元素 k 的个数。set 容器中并不存在这种操作。这是 multiset 独有的。

---

bitset 01 字符串

​ bitset 容器其实就是个 01 串。可以被看作是一个 bool l数组。它比 bool 数组更优秀的优点是：**节约空间，节约时间，支持基本的位运算。**在 bitset 容器中，8 位占一个字节，相比于 bool 数组 4 位一个字节的空间利用率要高很多。同时，n 位的 bitset 在执行一次位运算的复杂度可以被看作是 n/32 ，这都是 bool 数组所没有的优秀性质。

​ bitset 容器包含在 C++ 自带的 bitset 库中。

#include 
1

​ 因为 bitset 容器就是装 01 串的，所以不用在 < >中装数据类型，这和一般的 STL 容器不太一样。< >中装01 串的位数。

如：（声明一个 100000 位的 bitset）

bitset<100000> s;
1

常用操作

位运算操作在bitset中的实现

​ bitset容器还支持直接取值和直接赋值的操作：具体操作方式如下：

s[3]=1;

s[5]=0;
1
2
3

这里要注意：在 bitset 容器中，最低位为 0

---

unordered_set 无序set容器

​ unordered_set 是基于哈希表。哈希表是根据关键码值而进行直接访问的数据结构，通过相应的哈希函数(也称散列函数)处理关键字得到相应的关键码值，关键码值对应着一个特定位置，用该位置来存取相应的信息，这样就能以较快的速度获取关键字的信息。unordered_set 内部解决冲突采用的是----链地址法，当用冲突发生时把具有同一关键码的数据组成一个链表。

模板类定义在include

声明：

#incldue <unordered_set>

unordered_set<string> uset;
1
2
3

常用操作

​ 注意，此容器模板类中没有重载 [ ] 运算符，也没有提供 at() 成员方法。不仅如此，由于 unordered_set 容器内部存储的元素值不能被修改，因此无论使用那个迭代器方法获得的迭代器，都不能用于修改容器中元素的值。

map

map 映射容器

​ map 是“映射容器”，其存储的两个变量构成了一个键值到元素的映射关系。我们可以根据键值快速地找到这个映射出的数据。map 容器的内部实现是一棵红黑树（平衡树的一种）。

声明

​ map容器存在于 STL 模板库 #include 中。使用的时候需要先开这个库。

#include

map<int,char> mp;
1
2
3

这就建立了一个从一个整型变量到一个字符型变量的映射。

常用方法：

​ map 也是使用迭代器实现遍历的。如果我们要在遍历的时候查询键值（即前面的那个），可以用it->first来查询，那么，当然也可以用it->second查询对应值（后面那个）

map 和 pair 的关系

首先，map 构建的关系是映射，也就是说，如果我们想查询一个键值，那么只会返回唯一的一个对应值。但是如果使用 pair 的话，不仅不支持 O(log) 级别的查找，也不支持知一求一，因为 pair 的第一维可以有很多一样的，也就是说，可能会造成一个键值对应 n 多个对应值的情况。这显然不符合映射的概念。

multimap 有序多重映射容器

​ multimap 容器具有和 map 相同的特性，即 multimap 容器也用于存储 pair 类型的键值对（其中 K 表示键的类型，T 表示值的类型），其中各个键值对的键的值不能做修改；并且，该容器也会自行根据键的大小对存储的所有键值对做排序操作。和 map 容器的区别在于，multimap 容器中可以同时存储多（≥2）个键相同的键值对。

#include 
using namespace std;

multimap<string, string> mymultimap;
1
2
3
4

使用方法基本上和 map 容器类似，唯一的区别是 multimap 未提供 at() 成员方法， 也没有重载 [] 运算符。这意味着，map 容器中通过指定键获取指定指定键值对的方式，将不再适用于 multimap 容器。其实这很好理解，因为 multimap 容器中指定的键可能对应多个键值对，而不再是 1 个。

unordered_map 无序 map 容器

​ unordered_map 容器，直译过来就是"无序 map 容器"的意思。所谓“无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。unordered_map 容器和 map 容器一样，以键值对（pair类型）的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。

​ unordered_map 的底层采用哈希表的实现，查询的时间复杂度为是 O(1)。所以 unordered_map 内部就是无序的，数据是按散列函数插入到槽里面去的。unordered_map 属于关联式容器，采用 pair 保存key-value形式的数据。用法与map一致。

​ 引入：

#include 

using namespace std;

unordered_map<string, string> umap;
1
2
3
4
5

常用方法和 map 类似。

参考资料

史上最全的各种C++ STL容器全解析
STL教程：C++ STL快速入门（非常详细）