浅谈C++STL容器

引入

 STL(Standard template library)也称作标准模板库。是C++提供的一些功能强大的容器，可以一定程度上省去手写数据结构的麻烦。

目录

• #include<stack>
• #include<queue>
• #include<vector>
• #include<deque>
• #include<map>
• #include<set>

一.栈（stack）

介绍：

栈是最简单的STL容器，手写只需要用一个数组和一个指向栈顶的指针（但我还是喜欢用STL）

方法	描述	实例	时间复杂度
push	从栈顶入栈	st.push(x);	O(1)
pop	从栈顶出栈	st.pop();	O(1)
size	查询元素个数	int x=st.size();	O(1)
empty	查询是否为空	bool flag=st.empty();	O(1）

 此外，所有的STL容器都支持size和empty，之后不再赘述

特点：先进后出

二.队列（queue）

常见的队列分为两种，一种是循环队列（queue），一种是优先队列（priority_queue)；相比于栈，队列不易手写（普通的数组模拟循环队列会浪费空间），所以一般引入STL

1.队列：

方法	描述	实例	时间复杂度
push	从队首插入元素	q.push(x);	O(1)
pop	从队首删除元素	q.pop();	O(1)
front	访问队首元素	int x=q.front();	O(1)
back	访问队尾元素	int x=q.back();	O(1)

• 特点：先进先出
• 应用：BFS，SPFA等
• 常用写法：while(!q.empty())...

2.优先队列

默认是大根堆（队列内元素排序从大到小）

若需更复杂的操作需要重载运算符，详见我以前写的文章优先队列和重载运算符（点击查看）

优先队列的push和pop时间复杂度都是O(nlogn)，但访问队首的top为O(1)

三.无限长度数组（vector)

1.声明：vector<int> v;

2.遍历：for(int i=0;i<(int)v.size();i++)

注意：vector下标从0开始

方法	描述	实例	时间复杂度
clear	清空元素	v.clear();	O(n)
front/back	访问首/尾元素	int x=v.front();	O(1)
push_back/pop_back	删除首/尾元素	v.push_back(x);	O(1)
erase	删除一个元素	v.erase(x);	大概是O(n)

关于erase，返回的是删除的元素的迭代器地址的下一位，也不太常用（我也不太会）

迭代器声明：vector<int>::iterator it;(it是地址指针，名字随便起，*it表示it地址里面的元素）

应用：邻接表存图v[x].push_back(y);

四.双端队列（deque）

相当于queue和vector的结合体，可以增删元素，也可以以数组的下标形式访问

五.set

• 相当于一个有序的集合（没有重复元素）
• 大部分操作时间复杂度O(nlogn)
• mutiset就是有重复元素的set
• 用法：借鉴了大佬mrclr的博客-------------------传送门（点击查看）

六.map

• 可以看作一个下标和值都任意的数组
• 大部分操作时间复杂度O(nlogn)
• 同理有mutimap，具体可以看下面的用法
• 用法：借鉴了大佬mrclr的博客-------------------传送门（点击查看）

感谢阅读！