C++ STL 用法解释

C++ STL vector 数组

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

#include

vector<int> vec;

vector<char> vec;

vector<pair<int,int> > vec;

vector<node> vec;

struct node{...};

• 使用方法

用法	作用
vec.begin(),vec.end()	返回vector的首、尾迭代器
vec.front(),vec.back()	返回vector的首、尾元素
vec.push_back()	从vector末尾加入一个元素
vec.pop_back()	从vector末尾删除一个元素
vec.size()	返回vector当前的长度（大小）
vec.empty()	返回vector是否为空，1为空、0不为空
vec.clear()	清空vector

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;
}

使用方法：

方法	解释
string.c_str()	转换为 C 语言风格的字符串
cin>>string cout <	输入、输出，遇到空格就认为输入结束。
string[i]	访问第 i 个字符串
+ -	字符串的拼接
insert(pos, str)	可以在 string 字符串中指定的位置插入另一个字符串，pos 表示要插入的位置，也就是下标；str 表示要插入的字符串，它可以是 string 字符串，也可以是C风格的字符串。
earse(pos, len)	删除 string 中的一个子字符串，pos 表示要删除的子字符串的起始下标，len 表示要删除子字符串的长度。如果不指明 len 的话，那么直接删除从 pos 到字符串结束处的所有字符（此时 len = str.length - pos）
substr(pos, len)	从 string 字符串中提取子字符串，pos 为要提取的子字符串的起始下标，len 为要提取的子字符串的长度。
find(str, pos)	在 string 字符串中查找子字符串出现的位置，第一个参数为待查找的子字符串，它可以是 string 字符串，也可以是C风格的字符串。第二个参数为开始查找的位置（下标）；如果不指明，则从第0个字符开始查找。find() 函数最终返回的是子字符串第一次出现在字符串中的起始下标
rfind()	在字符串中查找子字符串， rfind() 函数则最多查找到第二个参数处
find_first_of()	查找子字符串和字符串共同具有的字符在字符串中首次出现的位置。

---

queue queue 队列

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

#include

queue<int> q;

queue<char> q;

queue<pair<int,int> > q;

queue<node> q;

struct node{...};

• 使用方法

用法	作用
q.front(),q.back()	返回queue的首、尾元素
q.push()	从queue末尾加入一个元素
q.pop()	从queue末尾删除一个元素
q.size()	返回queue当前的长度（大小）
q.empty()	返回queue是否为空，1为空、0不为空

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

---

stack 栈

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

#include

stack<int> stk;
stack<char> stk;
stack<pair<int,int> > stk;
stack<node> stk;
struct node{...};

• 使用方法

用法	作用
stk.top()	返回stack的栈顶元素
stk.push()	从stack栈顶加入一个元素
stk.pop()	从stack栈顶d出一个元素
stk.size()	返回stack当前的长度（大小）
stk.empty()	返回stack是否为空，1 为空、0 不为空

---

priority_queue 优先队列

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

大根堆

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

#include

priority_queue<int> q;

priority_queue<string> q;

priority_queue<pair<int,int> > q;

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

小根堆

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

实现方式：

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

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

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

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

使用方法

用法	作用
q.top()	返回 priority_queue 的首元素
q.push()	向 priority_queue 中加入一个元素
q.pop()	从 priority_queue 末尾删除一个元素
q.size()	返回 priority_queue 当前的长度（大小）
q.empty()	返回 priority_queue 是否为空，1为空、0不为空

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

---

deque 双端队列

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

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

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

• 用法

用法	作用
q.begin(),q.end()	返回deque的首、尾迭代器
q.front(),q.back()	返回deque的首、尾元素
q.push_back()	从队尾入队一个元素
q.pop_back()	从队尾出队一个元素
q.push_front()	从队头入队一个元素
q.pop_front()	从队头出队一个元素
q.clear()	清空队列

除了这些用法之外，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{...};

• 使用方法

用法	作用
s.empty();	empty() 函数返回当前集合是否为空，是返回1，否则返回0.
s.size();	size() 函数返回当前集合的元素个数。
s.clear();	clear() 函数清空当前集合。
s.begin(),s.end();	begin() 函数和 end()函数返回集合的首尾迭代器，begin() 函数返回的指针指向的的确是集合的第一个元素。但 end() 返回的指针却指向了集合最后一个元素后面一个元素。左闭右开
s.insert(k);	insert(k) 函数表示向集合中加入元素 k。
s.erase(k);	erase(k) 函数表示删除集合中元素 k。
s.find(k);	find(k) 函数返回集合中指向元素 k 的迭代器。如果不存在这个元素，就返回 s.end() ，这个性质可以用来判断集合中有没有这个元素。
s.lower_bound(),s.upper_bound();	其中 lower_bound 返回集合中第一个大于等于关键字的元素。upper_bound 返回集合中第一个严格大于关键字的元素。
s.equal_range();	这个东西返回一个pair（内置二元组），分别表示第一个大于等于关键字的元素，第一个严格大于关键字的元素，也就是把前面的两个函数和在一起。如果有一个元素找不到的话，就会返回s.end()。

multiset 有序多重集合

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

与set容器不太一样的地方

s.erase(k);

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

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

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

可以妙用一下：

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

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

s.count(k);

​ 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 

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

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

bitset<100000> s;

常用 *** 作

函数	用法
s.count();	count，数数的意思。它的作用是数出 1 的个数。即 s.count() 返回 s 中有多少个 1.
s.any(); s.none();	any，任何的意思。none ，啥也没有的意思。这两个函数是在检查 bitset 容器中全 0的情况。 如果，bitset 中全都为 0 ，那么 s.any() 返回 false，s.none() 返回 true。 反之，假如 bitset 中至少有一个1，即哪怕有一个1，那么s.any() 返回true，s.none() 返回 false.
s.set(); s.set(u,v);	set() 函数的作用是把 bitset 全部置为1. 特别地，set() 函数里面可以传参数。set(u,v) 的意思是把 bitset 中的第 u 位变成 v , v∈0/1v,v∈0/1 。
s.reset(); s.reset(k);	reset() 函数将 bitset 的所有位置为 0 。而 reset() 函数只传一个参数，表示把这一位改成 0 。
s.flip(); s.flip(k);	flip() 函数的作用是将整个 bitset 容器按位取反。同上，其传进的参数表示把其中一位取反。

位运算 *** 作在bitset中的实现

符号	解释
~	按位取反
&	按位与
`	`
^	按位异或
<< >>	左/右移
==/！=	比较两个 bitset 是否相等

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

s[3]=1;

s[5]=0;

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

---

unordered_set 无序set容器

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

模板类定义在include

声明：

#incldue <unordered_set>

unordered_set<string> uset;

常用 *** 作

成员方法	功能
begin()	返回指向容器中第一个元素的正向迭代器。
end()	返回指向容器中最后一个元素之后位置的正向迭代器。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前容器中存有元素的个数。
max_size()	返回容器所能容纳元素的最大个数，不同的 *** 作系统，其返回值亦不相同。
count(key)	在容器中查找值为 key 的元素的个数。
equal_range(key)	返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中值为 key 的元素所在的范围。
insert()	向容器中添加新元素。
emplace()	向容器中添加新元素，效率比 insert() 方法高。
emplace_hint()	向容器中添加新元素，效率比 insert() 方法高。
erase()	删除指定元素。
clear()	清空容器，即删除容器中存储的所有元素。
swap()	交换 2 个 unordered_map 容器存储的元素，前提是必须保证这 2 个容器的类型完全相等。

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

map map 映射容器

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

声明

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

#include

map<int,char> mp;

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

常用方法：

函数	用法
begin()	返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
find(key)	在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key)	返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key)	返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 map 容器中存有键值对的个数。
max_size()	返回 map 容器所能容纳键值对的最大个数，不同的 *** 作系统，其返回值亦不相同。
operator[]	map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。
at(key)	找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
insert()	向 map 容器中插入键值对。
erase()	删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。
swap()	交换 2 个 map 容器中存储的键值对，这意味着， *** 作的 2 个键值对的类型必须相同。
clear()	清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
emplace()	在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
emplace_hint()	在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
count(key)	在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

​ 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;

使用方法基本上和 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;

常用方法和 map 类似。

参考资料

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