C++标准模板库STL最全总结收藏方便使用 _总结

敢说敢作敢为，无怨无恨无悔。这篇文章主要讲述C++标准模板库STL最全总结收藏方便使用相关的知识，希望能为你提供帮助。
vector

vector翻译为向量，在这里称为“变长数组”更贴切些，在考试题中，往往会遇到只用普通数组会超内存的情况，这时使用vector会让问题解决便捷许多。另外，vector 还可以使用邻接表的方式储存图。
定义引入

#include < vector>

定义一个 vector

vector < type> name; //此处的type除了可以为基本类型int,double,char等外还可以为node(结构体)

当 type 为 vector 时，就有一点二维数组的感觉了

vector< vector< int> > name; //> > 之间要加空格，否则一些c++11之前标准的编译器会把它当做移位操作

【C++标准模板库STL最全总结收藏方便使用】定义一个vector数组

vector< type> Arrayname[arraysize]; //例如 vector< int> vi[100];

访问方式
下标访问
迭代器访问

//第一种 vector< int> ::iterator it = vi.begin(); for(int i = 0; i < 5; i++) printf("%d ",*(it + i)); //第二种 //vector的迭代器不支持it < vi.end()写法，因此循环条件只能用it != vi.end() for(vector< int> ::iterator it = vi.begin(); it != vi.end(); it++) printf("%d ", *it);

在常用 STL 容器中，只有在 vector 和 string 中，才允许使用 vi.begin()+3 这种迭代器加上整数的写法。
常用函数push_back(x) 在 vector 后面添加一个元素x，时间复杂度为O(1)
pop_back()删除尾元素，时间复杂度为O(1)
size()获得 vector 中元素的个数，时间复杂度为O(1)
clear()清空 vector 中所有的元素，时间复杂度为O(N)
insert(it,x)用来向 vector 的任意迭代器 it 处插入一个元素 x，时间复杂度为 O(N)
erase(it)删除迭代器为 it 处的元素
erase(first,last)删除[first,last) 左闭右开内的所有元素
常见用途
vector翻译为向量，在这里称为“变长数组”更贴切些，在考试题中，往往会遇到只用普通数组会超内存的情况，这时使用vector会让问题解决便捷许多。另外，vector 还可以使用邻接表的方式储存图。
vector 本身可以作为数组使用，而且在一些元素个数不确定的场合可以很好的节省空间。
有些场合需要根据一些条件把部分数据输出在同一行，数据中间用空格隔开。由于输出数据的个数是不确定的，为了更方便地输出最后一个满足条件的数据后面不输出额外的空格，可以先用 vector 记录所有需要输出的数据，然后一次性输出。
set
set翻译为集合，是一个内部自动有序且不含重复元素的容器。在考试中，有可能出现需要去掉重复元素的情况，而且有可能因为这些元素比较大或者类型不是int型而不能直接开散列表，在这种情况下就可以使用set来保留元素本身而不考虑它的个数。而且加入set之后可以实现自动排序，因此熟练使用set可以在做某些题时减少思维量。定义引入

#include < set>

其定义的写法其实和vector基本是一样的，或者说其实大部分STL都是这样定义的。这里的typename依然可以是任何基本类型，例如 int,double,char,结构体等，或者是STL标准容器，例如vector,set,queue等

set< type> name;

set数组的定义和vector相同

set< type> Arrayname[arraySize]; //每一个都是一个set容器

?

访问方式set只能通过迭代器 iterator 访问

//由于除了 vector 和 string 之外的 STL 容器都不支持 *(it+i) 的访问方式，因此只能按照如下方式来枚举 for(set< int> ::iterator it = st.begin(); it != st.end(); it++) printf("%d",*it);

常用函数insert(x)将x插入到set容器中，并且自动递增排序和去重，时间复杂度O(logN)，N为set内的元素个数
find(value)返回set中值为value的迭代器，时间复杂度O(logN)，N为set内的元素个数

set< int> st; for(int i = 1; i< =3; i++) st.insert(i); set< int> ::iterator it = st.find(2); //在set中查找2，返回其迭代器 printf("%d\\n",*it); //输出2

erase(it)删除迭代器为it的元素，时间复杂度为O(1),可以结合find()函数来使用

set< int> st; for(int i = 1; i< =3; i++) st.insert(i); st.erase(st.find(1)); //利用find函数找到1，然后用erase函数删除它

erase(first,last)删除一个区间内的所有元素，同vector一样，也是左闭右开
size()获取set内元素的个数，时间复杂度为O(1)
clear()用来清空set中的所有元素，复杂度为O(N),其中N为set内元素的个数
常见用途

set翻译为集合，是一个内部自动有序且不含重复元素的容器。在考试中，有可能出现需要去掉重复元素的情况，而且有可能因为这些元素比较大或者类型不是int型而不能直接开散列表，在这种情况下就可以使用set来保留元素本身而不考虑它的个数。而且加入set之后可以实现自动排序，因此熟练使用set可以在做某些题时减少思维量。
set主要用途是自动去重并按照升序排序，因此碰到需要去重但是却不方便直接开数组的情况，可以尝试用set解决。
set中元素是唯一的，如果需要处理不唯一的情况，则需要使用multiset
string 定义引入

#include < string>

定义

string str = "123";

访问方式
通过下标访问，如果是读入或者是输出整个字符串，只能用cin或者是cout，如果非要用printf输出整个字符串，可以使用c_str()将string类型转为字符数组进行输出。
通过迭代器访问

for(string::iterator it = str.begin(); it!=str.end(); it++) printf("%c",*it);

常用函数operator+-直接使用+将两个字符串直接拼接起来
compare operator直接使用 == ,!=,< ,< =,> ,> =比较大小，比较规则是字典序
length()/size()length()返回字符串的长度，即存放的字符数，时间复杂度是O(1)。size()与length()基本相同
insert(pos,string)在 pos 号位置插入字符串 string，时间复杂度为O(N)
insert(it,it2,it3)it2和it3为待插入字符串的首尾迭代器，用来表示串[it2,it3)将被插在it的位置上
erase(it)删除迭代器为it的元素，时间复杂度为O(N)
erase(first,last)删除一个区间内的所有元素，时间复杂度为O(N)
erase(pos,length)其中pos为需要开始删除的起始位置，length为删除的字符个数
clear()用于清空string中的数据，时间复杂度为O(1)
substr(pos,len)返回从pos号位开始，长度为len的子串，时间复杂度为O(len)
string::npos是一个常数，其本身的值为-1，但由于是unsigned_int类型，因此实际上也可以认为是unsigned_int类型的最大值。string::npos 用以作为find函数失配时的返回值,所以可以认为string::npos可以等于-1或者4294967295
str.find(str2)当str2是str的子串时，返回其在str中第一次出现的位置，如果str2不是str的子串，那么返回string::npos
str.find(str2,pos)从str的pos号位开始匹配str2，返回值与上相同，时间复杂度为O(nm)，其中n和m分别为str和str2的长度。
str.replace(pos,len,str2)把str从pos号位开始，长度为len的子串替换为str2
str.replace(it1,it2,str2)把str的迭代器[it1,it2]范围的子串替换为str2时间复杂度为O(str.length())
map
map翻译为映射，也是常用的STL容器。在定义数组时，如a[2] = 3其实是定义了一个从int到int的映射，b[2]=3.5定义了int到double的映射，无论是什么类型，总是将int类型映射到了其他类型。当需要以其他类型作为关键字来做映射时，会显得不方便。我们可以利用map实现将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器)。
定义引入

#include < map>

单独定义一个map

map< type1,type2> mp;

如果是字符串到整型的映射，必须使用string而不能使用char数组

map< string,int> map;

将一个set容器映射到一个字符串

map< set< int> ,string>

访问方式
通过下标访问

对于一个定义为map< char,int> mp的map来说，就可以直接使用mp[c]的方式来访问它对应的整数。
通过迭代器访问,map可以使用it-> first来访问键，使用it-> second来访问值

map< char,int> mp; mp[m] = 20; mp[r] = 30; mp[a] = 40; for(map< char,int> ::iterator it = mp.begin(); it!=mp.end(); it++) printf("%c %d",it-> first,it-> second);

常用函数find(key)返回键为key的映射的迭代器，时间复杂度为O(log N),N为map中的映射的个数

map< char,int> mp; mp[m] = 20; mp[r] = 30; mp[a] = 40; map< char,int> ::iterator it = mp.find(r); printf("%c %d\\n",it-> first,it-> second);

erase(it)删除单个迭代器，可以配合find函数使用

map< char,int> mp; mp[m] = 20; mp[r] = 30; mp[a] = 40; map< char,int> ::iterator it = mp.find(b); mp.erase(it);

erase(key)key为欲删除的键，时间复杂度为O(logN)
erase(first,last)删除一个区间内的所有元素

map< char,int> mp; mp[m] = 20; mp[r] = 30; mp[a] = 40; map< char,int> ::iterator it = mp.find(m); mp.erase(it,mp.end());

size()用来获得map中映射的对数，时间复杂度为O(1)
clear()用来清空map中所有的元素，时间复杂度为O(N),N为元素个数
常见用途
需要建立字符与整数之间映射的题目，使用map可以减少代码量
判断大整数或者其他类型是否存在的题目，可以把map当bool数组用
字符串和字符串的映射也有可能会用到
注意，map的键和值是唯一的，而如果一个键需要对应多个值，就只能用multimap
queue
queue翻译成队列，先进先出的容器，尾进头出
定义引入

#include < queue>

queue定义的写法和其他STL容器相同

queue < type> name;

访问方式由于队列本身是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或者通过back()来访问队尾元素

queue< int> q; for(int i = 1; i< =5; i++) q.push(i); printf("%d %d\\n",q.front(),q.back());

常用函数push(x)将x进行入队，时间复杂度为O(1)
front(),back()获得队首和队尾元素
pop()令队首元素出队，时间复杂度为O(1)
empty()检测queue是否为空，返回true则空，返回false则非空
size()返回queue内元素的个数，时间复杂度为O(1)
常见用途
当需要实现bfs时，可以不用自己动手实现一个队列，而是用STL中的queue作为代替，以提高程序的准确性
有一点需要注意，使用front()和pop()函数前，必须用empty()判断队列是否为空，否则有可能因为队列空而出现错误。
priority_queue
priority_queue又称为优先队列，其底层是用堆来实现的，在优先队列中，队首元素一定是当前队列中优先级最高的那一个。例如在如下的队列中有以下元素，且定义好了优先级

桃子（优先级3）梨子（优先级4）苹果（优先级1）那么出队的顺序为梨子(4)-> 桃子(3)-> 苹果(1)

当然，可以在任何时候往优先队列里面push元素，而优先队列底层的数据结构heap会随时调整结构，使得每次的队首元素都是优先级最大的。
定义引入

#include < queue>

定义

priority_queue< type> name;

访问方式和队列不一样的是，优先队列没有front()函数与back()函数，而只能通过top()函数来访问队首元素（也可以称为堆顶元素），也就是优先级最高的元素

priority_queue< int> q; q.push(3); q.push(4); q.push(1); printf("%d\\n",q.top());

常用函数push(x)将x入队，时间复杂度为O(logN),其中N为当前优先队列中的元素个数
top()令队首元素出队，时间复杂度为O(logN)，其中N为当前优先队列中的元素个数
empty()检测优先队列是否为空，返回true则空，返回false则非空，时间复杂度为O(1)
size()返回优先队列内的元素的个数，时间复杂度为O(1)
元素优先级如何设置
基本数据类型

对于int，double，char型等可以直接使用的数据类型，优先队列对他们的优先级设置一般是数字越大的优先级别越高， char的话就是字典序越大的优先级越高。

自定义优先级

priority_queue< int,vector< int> ,less< int> > q 数字越大的优先级越高，与默认效果一样 priority_queue< int,vector< int> ,greater< int> > q 数字越小的优先级越高

结构体优先级的设置
优先队列的这个函数与sort中的cmp函数的效果是相反的
常见用途
优先队列可以解决一些贪心问题，也可以对迪杰斯特拉算法进行优化，因为优先队列的本质是堆
在使用top函数时，必须用empty函数判断优先队列是否为空，否则可能会因为队空而出现错误
stack
stack是栈，是一个后进先出的容器
定义引入

#include < stack>

定义

stack< type > name;

访问方式stack只能通过top()来访问栈顶元素
常用函数push(x)将x入栈，时间复杂度为O(1)
top()获得栈顶元素，时间复杂度为O(1)
pop()用来弹出栈顶元素，时间复杂度为O(1)
empty()用来检测stack内是否为空，返回 true 为空， false 为非空，时间复杂度为O(1)
size()返回stack 内元素的个数，时间复杂度为O(1)
常见用途
stack用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行错误。一般来说，程序的栈内存空间很小，对于有些题目来说，如果用普通的函数来执行递归，一旦递归层数过深，则会导致程序运行崩溃，如果用栈来模拟递归算法的实现，则可以避免这一方面的问题。
pair
pair是一个很实用的“小玩意”，当想要将两个元素绑在一起作为一个合成元素、又不想要因此定义结构体时，使用pair可以很方便的作为一个代替品。也就是说，pair实际上可以看作一个内部有两个元素的结构体，而且这两个元素的类型是可以指定的。

struct pair type1 first; type2 second; ;

定义引入

#include < utility> 或 #include < map> //map中包含utility

定义

pair < int,string> p; //定义时初始化 pair < string,int> p("test",5); //临时构建 pair < string,int> ("test",5) //使用自带的make_pair函数 make_pair("test",5)

访问方式使用first second的方式访问

pair< string,int> p; p.first = "Test" p.second = 5;

常用函数比较操作数 == != < > < = > =比较的规则是先以first的大小作为标准，只有当first相等时才用second比较
常见用途
用来代替二元结构体以及其构造函数，可以节省编码的时间。
作为map的键值对来进行插入，如下
map < string,int> mp; mp.insert(make_pair("test",5)); mp.insert(pair< string,int> ("test",5));

algorithm头文件下的常用函数max(x,y),min(x,y)和abs(x),fabs(x)max和min用来返回x,y中最大值和最小值，如果要比较三个数x,y,z，max(x,max(y,z))，abs(x)和math(x)下的fabs分别返回整形x和浮点型x的绝对值
swap(x,y)交换x和y的值
reverse(it,it2)将数组指针在[it,it2)之间的元素或容器的迭代器在这个范围内的元素进行反转
next_permutation()给出一个序列在全排列中的下一个序列
fill()可以把数组或容器中的某一段区间赋为某个相同的值。和memset不同，这里的赋值可以是数组类型对应范围中的任意值

int a[5] = 1,2,3,4,5; fill(a,a+5,233); //将a[0]~a[4]均赋值为233 输出数组为 233 233 233 233 233

sort(首元素地址，尾元素的下一个地址，比较函数)
实现自定义比较函数cmp

若不填比较函数，则默认按照从小到大的顺序排列如果要按照从大到小的顺序排列，比较函数这么写 bool cmp(int a,int b) return a> b;

结构体数组的排序
struct node
int x,y;
ssd[10];
bool cmp(node a,node b)
return a.x> b.x; //按照x的值从大到小对结构体数组进行排序

容器的排序
只有vector,string,deque是可以用sort的，这是因为像set,map这种容器是用红黑树实现的，
元素本身有序，故不允许使用sort排序

**lower_bound()和upper_bound()** lower_bound(first,last,val)用来寻找在数组或容器的[first,last)范围内第一个值**大于等于**val的元素的位置，如果是数组，则返回该位置的指针，如果是容器，则返回该位置的迭代器。 upper_bound(first,last,val)用来寻找在数组或容器的[first,last)范围内第一个值**大于**val的元素的位置，如果是数组，则返回该位置的指针，如果是容器，则返回该位置的迭代器。