C++ STL常见容器

vector为可变长数组（动态数组），定义的vector数组可以随时添加数值和删除元素。

头文件

#include < vector >

初始化：

//初始化
//方式一：初始化一维可变长数组
vectornum; //定义了一个名为num的存int数据的一维数组
vectornum;//定义了一个名为num的存double数据的一维数组
vectornum;//node是结构体类型

//方式二：初始化二维可变长数组
vectornum[5];//定义可变长二维数组
//注意：行是不可变的（只有5行），而列可变可以在指定行添加元素
//第一维固定长度为5，第二维长度可以改变

//方式三:初始化二维均可变长数组
vector >num;//定义一个行和列均可变的二维数组

简单访问：

//方式一：单个访问，假设num数组中已经有了5个元素
cout< 

初始化技巧：
 
//1.附加长度
vectorv(n);//定义一个长度为n的数组，动态定义
//2.附加长度和初始值
vectorv(n，0);//所有的元素均为0
 
1.2 方法函数 
知道了如何定义初始化可变数组，下面就需要知道如何添加，删除，修改数据。
 
相关方法函数如下：c指定为数组名称
 
代码
含义
c.front()
返回第一个数据
c.pop_back()
删除最后一个数据 O(1)
c.push_back(element)
在尾部加一个数据 O(1)
c.size()
返回实际数据个数（unsigned类型） O(1)
c.clear()
清除元素个数 O(N),N为元素个数
c.resize(n,v)
改变数组大小为n,n个空间数值赋为v，如果没有默认赋值为0
c.insert(it,x)
 
向任意迭代器it插入一个元素x O(N)，
 
例：c.insert(c.begin()+2,-1) 将-1插入c[2]的位置
 
c.erase(first,last)
删除[first,last)的所有元素
c.begin()
返回首元素的迭代器（通俗来说就是地址）
c.end()
返回最后一个元素后一个位置的迭代器（地址）
c.empty()
判断是否为空，为空返回真，反之返回假
 
 
 
 
 
 
 
 
 
 
 
 
 
 
注意： end()返回的是最后一个元素的后一个位置的地址，不是最后一个元素的地址,所有容器均是如此。以上 O(n),O(1)说的是时间复杂度。
 
 
1.3 注意点 
1.3.a 排序 
使用sort排序要： sort(c.begin(),c.end());
 
对所有元素进行排序，如果要对指定区间进行排序，可以对sort()里面的参数进行加减改动。
 
1.3.b 访问 
数组访问：上面有简单的访问演示，下面进行扩充并复习
 
下标法： 和普通数组一样；注意：一维数组的下标是从0到v.size()-1,访问之外的数可能会出错
 
迭代器法： 类似指针一样的访问 ，首先需要声明迭代器变量，和声明指针变量一样，可以根据代码进行理解（附有注释）。
 
代码如下：
 
vectorvi; //定义一个vi数组
vector::iterator it = vi.begin();//声明一个迭代器指向vi的初始位置
 

 vector数组访问相关代码：
 
1.3.1.下标访问：
 
//添加元素
for(int i=0;i<5;i++)
	vi.push_back(i);
	
//下标访问 
for(int i=0;i<5;i++)
	cout< 

1.3.2.迭代器访问：
 
//迭代器访问
vector::iterator it;   
//相当于声明了一个迭代器类型的变量it
//通俗来说就是声明了一个指针变量

//方式一：
vector::iterator it=vi.begin(); 
for(int i=0;i<5;i++)
	cout<<*(it+i)<<" ";
cout<<"n";

//方式二：
vector::iterator it;
for(it=vi.begin(); it != vi.end();it++)
	cout<<*it<<" ";
//vi.end()指向尾元素地址的下一个地址
 

1.3.3.智能指针：
 
只能遍历完数组，如果要指定的内容进行遍历，需要另选方法。
 auto 能够自动识别类型。
 
vectorv;
v.push_back(12);
v.push_back(241);
for( auto i : v) 
	cout< 

 综上：
 
vi[i] 和 *(vi.begin() + i) 等价
 
说明：只有vector和string的stl容器支持*（it+i）的元素访问
 
关于string下面有讲述，可以往后看哦
 
 
2.stack（栈） 
2.1 介绍 
栈为数据结构的一种，是STL中实现的一个先进后出，后进先出的容器。
 
就像火车进入没有出口的隧道一样，隧道是stack栈容器，火车车厢是入栈元素，火车头先进去，火车尾最后进隧道，当火车倒出来时，火车尾最先出来，火车头最后出来，所有的元素满足先进后出的规则。
 
//头文件需要添加
#include

//声明
stacksta;
stacksta;
stacksta;//node是结构体类型
 

2.2 方法函数 
代码
含义
push()
压栈，增加元素 O(1)
pop()
移除栈顶元素 O(1)
top()
取得栈顶元素（但不删除）O(1)
empty
检测栈内是否为空，空为真 O(1)
size()
返回stack内元素的个数 O(1)
 
 
 
 
 
 
 
2.3 注意点 
2.3.a.栈遍历 
栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中
 
2.3.b.模拟栈 
可以通过一个数组对栈进行模拟，一个存放下标的变量top模拟指向栈顶的指针。
 
特点： 比stack更快，如果能模拟就模拟，会减少时间。（注：我就做过这样的题，stack超时了，但模拟轻松通过）
 
下面是简单的代码描述：
 
int sta[100];
int top=0;//初始化top
for(int i=0;i<=5;i++)
{
	//入栈 
	sta[top++]=i;
}
int top_element = sta[--top]; 

//入栈操作示意
//  0  1  2  3  4  5  
//                    top
//出栈后示意
//  0  1  2  3  4 
//                 top
 

 注意： top始终指向栈顶元素的下一个位置（除初始位置外），数组中的元素其实还存在
 
看完上述代码，我i们可以发现这种方法可以很方便地对栈的元素进行遍历。
 
如果想要在栈中存放不同的数据类型，可以考虑使用vector数组进行模拟栈。
 
 
3.queue（队列） 
3.1 介绍 
队列是一种先进先出的数据结构。
 
比喻性的描述可为 一条两端通透的隧道，火车车厢先进就先出，后进就后出。
 
//头文件
#include
//定义初始化
queueq;
 

 3.2 方法函数 
代码
含义
front()
返回队首元素 O(1)
back()
返回队尾元素 O(1)
push()
尾部添加一个元素副本 进队O(1)
pop()
删除第一个元素 出队 O(1)
size()
返回队列中元素个数，返回值类型unsigned int O(1)
empty()
判断是否为空，队列为空，返回true O(1)
 
 
 
 
 
 
 
 
队列还有另外两种双端队列，优先队列，下面做简单阐述，如果要详细了解大家可以找相关的博客学习，很抱歉不能够提供更多信息。
 
 
4.deque（双端队列) 
4.1 介绍 
首为都可插入和删除的队列为双端队列。
 
//添加头文件
#include
//初始化定义
dequedq;
 

 4.2 方法函数 
代码
含义
push_back(x)/push_front(x)
把x压入后/前端
back()/front()
访问(不删除)后/前端元素
pop_back() pop_front()
删除后/前端元素
erase(iterator it)
删除双端队列中的某一个元素
erase(iterator first,iterator last)
删除双端队列中[first,last）中的元素
empty()
判断deque是否空
size()
返回deque的元素数量
clear()
清空deque
 
 
 
 
 
 
 
 
 

 4.3 注意点 
deque可以进行排序，只能进行从小到大的排序
 
sort(d.begin(),d.end())//从小到大
 
 
5.priority_queue(优先级队列) 
5.1 介绍 
优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最大的。
 
每次操作队列中的元素都是按优先级排序的。
 
（你可以用它来排序，但是sort一般就可以排序，他的用处一般是在每次对序列进行增 删 改 的操作时，优先队列还能按优先级排序）
 
（比如一个优先队列 6 4 2 1 0 加入一个值5，优先队列就是6 5 4 2 1 0）
 
它的底层是通过堆来实现的。
 
//头文件
#include

//初始化定义
priority_queuepq;
 
5.2 函数方法 
代码
含义
top()
访问队首元素
push()
入队
pop()
堆顶（队首）元素出队
size()
队列元素个数
empty()
是否为空
注意没有clear()！
不提供该方法
 
 
 
 
 
 
 
 
优先队列只能通过top()访问队首元素（优先级最高的元素）
 
5.3 设置优先级 
5.3.a 基本数据类型的优先级 
priority_queue, less >pq;
//最后两个>之间要有空格
 
解释：
 
第二个参数：
 vector< int > 是用来承载底层数据结构堆的容器，若优先队列中存放的是double型数据，就要填vector< double >
 
总之存的是什么类型的数据，就相应的填写对应类型。
 
第三个参数：
 
less< int > 表示数字大的优先级大，降序队列
 
greater< int >表示数字小的优先级大，升序队列
 
int代表的是数据类型，也要填对应的类型
 
自定义排序：
 
struct cmp1
{
	bool operator()(int x,int y)
	{
		return x>y;//小的优先级高 ,从小到大排 
	}
}; 
struct cmp2
{
	bool operator()(const int x,const int y)
	{
		return a[x]>a[y];
	}
}; 
priority_queue,cmp1>pq1;
priority_queue,cmp2>pq2;

 

 5.3.b 结构体(或自定义)优先级设置 
优先级设置可以定义在结构体内进行小于号重载，也可以定义在结构体外，下面演示定义在外面的简单写法，详情大家可以搜索相关博客进行了解。
 
//要排序的结构体（存储在优先队列里面的）
struct node
{
	int x,y;
};
 

 版本一：
 
//定义的比较结构体
//注意：cmp是个结构体 
struct cmp
{//自定义堆的排序规则 
	bool operator()(const node& a,const node& b)
	{
		return a.x>b.x;//从堆底到堆顶 降序排序 
	}//如果要升序改变不等号方向就好
};

//初始化定义， 
priority_queue,cmp >pq; 
 
版本二：不用写关的参数，直接在node里面写
 
因为是在node里面自定义的规则，所以是node里面的值自动排了，并不需要cmp结构体了。
 
struct node
{
	int x,y;
	friend bool operator<(node a,node b)
	{//为两个结构体参数，结构体调用一定要写上friend
		return a.x>b.x;//按x从小到大排 
	}
};
 

 或者：
 
struct node
{
    bool operator < (const node& a) const
    {//直接传入一个参数，不必要写friend
        return x > a.x;//优先级大的为x小的值，升序排列
    }
};
 
优先队列的定义：
 
priority_queuepq4;
 

 注意： 优先对列自定义排序规则和sort()函数定义cmp函数很相似，但是最后返回的情况是相反的。即相同的符号，最后定义的排列顺序是完全相反的。
 
所以只需要记住sort的排序规则和优先队列的排序规则是相反的就可以了。
 
 
5.4 存储特殊类型的优先级 
5.4.a 存储pair类型 
排序规则：默认先对pair的first进行降序排序，然后再对second降序排序
 
对first先排序，大的排在前面，如果first元素相同，再对second元素排序，保持大的在前面。
 
#include
using namespace std;
int main()
{
    priority_queue >q;
	q.push({7,8});
	q.push({7,9});
	q.push(make_pair(8,7));
    while(!q.empty())
    {
        cout< 
结果：
 8 7
 7 9
 7 8
 
 
6.map(映射) 
6.1. map介绍 
映射类似于函数的对应关系，每个x对应一个y，而map是每个键对应一个值。会python的朋友学习后就会知道这和python的字典非常类似。
 
比如说：学习 对应 看书，学习 是键，看书 是值。
 学习->看书
 玩耍 对应 打游戏，玩耍 是键，打游戏 是值。
 玩耍->打游戏
 
//头文件
#include
 
map特性：map会按照键的顺序从小到大自动排序
 
 
6.2. 函数方法 
代码
含义
mp.find(key)
返回键为key的映射的迭代器 O(logN) 注意：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器，
mp.erase(it)
删除迭代器对应的键和值O(1)
mp.erase(key)
根据映射的键删除键和值 O(logN)
mp.erase(first,last)
删除左闭右开区间迭代器对应的键和值 O(last-first)
mp.size()
返回映射的对数 O(1)
mp.clear()
清空map中的所有元素 O(N)
mp.insert()
插入元素，插入时要构造键值对
mp.empty()
如果map为空，返回true，否则返回false
mp.begin()
返回指向map第一个元素的迭代器（地址）
mp.end()
返回指向map尾部的迭代器（最后一个元素的下一个地址）
mp.rbegin()
返回指向map最后一个元素的迭代器（地址）
mp.rend()
返回指向map第一个元素的迭代器（地址）
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 注意：
 
mp.begin()和mp.end()用法：用于正向遍历map
 
mapmp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.begin();
while(it!=mp.end())
{
	cout<first << " "<second<<"n";
	it ++;
}
 

 结果：
 
1 2
 2 3
 3 4

mp.rbegin()和mp.rend()：用于逆向遍历map
 
mapmp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.rbegin();
while(it!=mp.rend())
{
	cout<first << " "<second<<"n";
	it ++;
}
 

 结果：
 
3 4
 2 3
 1 2
 
6.3. 添加元素 
//先声明
mapmp;
 
方式一：
 
mp["学习"] = "看书";
mp["玩耍"] = "打游戏";
 
方式二：插入元素构造键值对
 
mp.insert(make_pair("vegetable","蔬菜"));
 
方式三：
 
mp.insert(pair("fruit","水果"));
 
方式四:
 
mp.insert({"hahaha","wawawa"});
 

 6.4. 访问元素 
6.4.1.下标访问：(大部分情况用于访问单个元素) 
mp["菜哇菜"] = "强哇强";
cout< 
6.4.2.遍历访问： 
方式一：迭代器访问
 
map::iterator it;
for(it=mp.begin();it!=mp.end();it++)
{
	//      键                 值 
	// it是结构体指针访问所以要用 -> 访问
	cout<first<<" "<second<<"n";
	/
 
string数组：
 
#include
#include
using namespace std;
int main()
{
	string s[10];
	for(int i=1;i<10;i++)
	{
		s[i] = "loading...  " ;
		cout< 
9.2 string 特性 
1、string字符串支持常见的比较操作符（>,>=,<,<=,==,!=），甚至支持string与C-string的比较(如 str<”hello”)。
 在使用>,>=,<,<=这些操作符的时候是根据“当前字符特性”将字符按 字典顺序 进行逐一得 比较。字典排序靠前的字符小， 比较的顺序是从前向后比较，遇到不相等的字符就按这个位置上的两个字符的比较结果确定两个字符串的大小(前面减后面) 同时，string (“aaaa”)  
2、另一个功能强大的比较函数是成员函数compare()。他支持多参数处理，支持用索引值和长度定位子串来进行比较。 他返回一个整数来表示比较结果，返回值意义如下：0：相等 1：大于 -1：小于 (A的ASCII码是65，a的ASCII码是97)
 
3、string字符串可以拼接，通过"+"运算符进行拼接。
 
string s1;
string s2;
s1 = "123";
s2 = "456";
string s = s1 + s2;
cout< 
9.3 读入详解 
9.3.1 :读入字符串，遇空格，回车结束 
string s;
cin>>s;
 

 9.3.2: 读入一行字符串（包括空格），遇回车结束 
string s;
getline(cin,s);
 

 注意！！！ getline(cin,s)会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()
 
错误读取：
 
int n;
string s;
cin>>n;
getline(cin,s);//此时读取相当于读取了前一个回车字符
 

 正确读取：
 
int n;
string s;
cin>>n;
getchar();//cin.get()
getline(cin,s);//可正确读入下一行的输入
 

 9.3.3 cin>>与cin.getline()混用 
cin输入完后，回车，cin遇到回车结束输入，但回车还在输入流中，cin并不会清除，导致getline（）读取回车，结束。 (即上述注意点)
 需要在cin后面加cin.ignore();主动删除输入流中的换行符
 
9.3.4：cin和cout解锁 
代码：
 
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
 

 为什么要进行cin和cout的解锁呢，原因是：
 
在一些题目中，读入的数据量很大，往往超过了1e5（105）的数据量,而cin和cout的读入输出的速度很慢，远不如scanf和printf的速度，具体原因可以搜索相关的博客进行了解。
 
所以对cin和cout进行解锁使cin和cout的速度几乎接近scanf和printf，避免超时。
 
注意！！！：cin cout解锁使用时，不能与 scanf 、getchar, printf,cin.getline( ) 混用，一定要注意，会出错。
 
 
9.4 函数方法 
获取字符串长度 
代码
含义
s.size()和length()
返回string对象的字符个数，他们执行效果相同。
s.max_size()
返回string对象最多包含的字符数，超出会抛出length_error异常
s.capacity()
重新分配内存之前，string对象能包含的最大字符数
 
 
 
 
 
 

 插入 
代码
含义
s.push_back()
在末尾插入
例：s.push_back(‘a’)
末尾插入一个字符a
s.insert(pos,element)
在pos位置插入element
例：s.insert(s.begin(),‘1’)
在第一个位置插入1字符
s.append(str)
在s字符串结尾添加str字符串
例：s.append(“abc”)
在s字符串末尾添加字符串“abc”
 
 
 
 
 
 
 
 
删除 
代码
含义
erase(iterator p)
删除字符串中p所指的字符
erase(iterator first, iterator last)
删除字符串中迭代器区间[first,last)上所有字符
erase(pos, len)
删除字符串中从索引位置pos开始的len个字符
clear()
删除字符串中所有字符
例：s.clear()
实质是把字符串空间首字符设置为了“”
 
 
 
 
 
 
 
 
字符替换 
代码
含义
s.replace(pos,n,str)
把当前字符串从索引pos开始的n个字符替换为str
s.replace(pos,n,n1,c)
把当前字符串从索引pos开始的n个字符替换为n1个字符c
s.replace(it1,it2,str)
把当前字符串[it1,it2)区间替换为str it1 ,it2为迭代器哦
 
 
 
 
 

大小写转换 
法一：
 
代码
含义
tolower(s[i])
转换为小写
toupper(s[i])
转换为大写
 
 
 
 
法二：
 
通过stl的transform算法配合tolower 和toupper 实现。
 有4个参数，前2个指定要转换的容器的起止范围，第3个参数是结果存放容器的起始位置，第4个参数是一元运算。
 
string s;
transform(s.begin(),s.end(),s.begin(),::tolower);//转换小写
transform(s.begin(),s.end(),s.begin(),::toupper);//转换大写
 

 分割 
代码
含义
s.substr(pos,n)
截取从pos索引开始的n个字符
 
 
 

 查找 
代码
含义
s.find (str, pos)
在当前字符串的pos索引位置(默认为0)开始，查找子串str，返回找到的位置索引，-1表示查找不到子串
s.find (c, pos)
在当前字符串的pos索引位置(默认为0)开始，查找字符c，返回找到的位置索引，-1表示查找不到字符
s.rfind (str, pos)
在当前字符串的pos索引位置开始，反向查找子串s，返回找到的位置索引，-1表示查找不到子串
s.rfind (c,pos)
在当前字符串的pos索引位置开始，反向查找字符c，返回找到的位置索引，-1表示查找不到字符
s.find_first_of (str, pos)
在当前字符串的pos索引位置(默认为0)开始，查找子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_first_not_of (str,pos)
在当前字符串的pos索引位置(默认为0)开始，查找第一个不位于子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_last_of(str, pos)
在当前字符串的pos索引位置开始，查找最后一个位于子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_last_not_of ( str, pos)
在当前字符串的pos索引位置开始，查找最后一个不位于子串s的字符，返回找到的位置索引，-1表示查找不到子串
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
还是不会用？ 下面上代码，进行实操
 
#include
#include
int main()
{
    string s("dog bird chicken bird cat");
//字符串查找-----找到后返回首字母在字符串中的下标
// 1. 查找一个字符串
    cout << s.find("chicken") << endl;// 结果是：9
    
// 2. 从下标为6开始找字符'i'，返回找到的第一个i的下标
    cout << s.find('i',6) << endl;// 结果是：11
    
// 3. 从字符串的末尾开始查找字符串，返回的还是首字母在字符串中的下标
    cout << s.rfind("chicken") << endl;// 结果是：9
    
// 4. 从字符串的末尾开始查找字符
    cout << s.rfind('i') << endl;// 结果是：18因为是从末尾开始查找，所以返回第一次找到的字符
    
// 5. 在该字符串中查找第一个属于字符串s的字符
    cout << s.find_first_of("13br98") << endl;// 结果是：4---b
    
// 6. 在该字符串中查找第一个不属于字符串s的字符------先匹配dog，然后bird匹配不到，所以打印4
    cout << s.find_first_not_of("hello dog 2006") << endl; // 结果是：4
    cout << s.find_first_not_of("dog bird 2006") << endl;  // 结果是：9
    
// 7. 在该字符串最后中查找第一个属于字符串s的字符
    cout << s.find_last_of("13r98") << endl;// 结果是：19

// 8. 在该字符串最后中查找第一个不属于字符串s的字符------先匹配t--a---c，然后空格匹配不到，所以打印21
    cout << s.find_last_not_of("teac") << endl;// 结果是：21
}
 

 排序 
sort(s.begin(),s.end());  //按ASCII码排序
 
10.list（链表） 
11.bitset