正文
C++常见STL介绍
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
栈 ：FILO
栈（stack）又名堆栈，它是一种线性表，是一个后进先出的数据结构。
使用时须加上头文件：#include<stack>
允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。
stack的基本操作有：
- l 入栈：如s.push(x);
- l 出栈：如s.pop()。注意出栈操作就是删除栈顶元素；
- l 访问栈顶：如s.top();
- l 判断栈空：如s.empty()。当栈空时返回true;
- l 访问栈中的元素个数。如s.size()；
栈代码示例：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<stack> //栈的头文件
using namespace std;
int main ()
{
stack<int> s1; //定义整型栈对象
stack<string>s2; // 定义字符型栈对象 s1.push(2); // 入栈2，就是插入数据2
s1.push(168); //入栈168
s1.push(888);//入栈888,现在栈中元素有{888,168,2} cout<<s1.top()<<endl; //访问栈顶元素，输出888
cout<<s1.size()<<endl; //访问栈中元素个数，输出3 s1.pop(); //出栈，出栈的元素是888
s1.push(233); // 入栈233，现在栈中元素应该是{233,168,2} int a=s1.size();
for(int i=1;i<=a;i++)
{
s1.pop();
if(s1.empty()) cout<<"空栈";
//如果是空栈(s1.empty()返回true) ,输出空栈
}
return 0;
}
队列
1、队列和优先队列的头文件都是<queue>
2、队列(FIFO)：先进先出的数据结构
3、queue<int>p; 定义一个变量名为p的队列
4 、入队： p.push(x) 将x从队列p最后面插入
出队： p.pop() 弹出（删除）p队列的第一个元素，注意并不会返回被弹出的元素的值
访问队首元素： p.front() 访问最早被压入队列的元素，即队首
访问队尾元素： p.back() 访问最晚被压入队列的元素 ，即队尾
判断队列空： p.empty() 当队列为空时，返回true
访问队列元素个数： p.size() 访问队列中元素的个数
清空队列： 可以p.pop()依次弹出（删除），p.clear()方法不行，是错误的
队列示例代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue> //队列和优先队列的头文件
using namespace std;
int h[10];
int main()
{
queue<int>p;//声明一个普通队列，普通队列先进先出
int i,n;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>h[i]; //输入n个整数
p.push(h[i]); //把输入的数依次压入队列p
cout<<p.back()<<" ";
//back()总是访问队列的最后一个元素（最后进的元素）
}
cout<<endl<<endl;
//队列 示例
for(i=1;i<=n;i++)
{
cout<<p.front()<<" "; //front()总是访问队列的第一个元素 （最先进的元素），
p.pop(); // 将其弹出 ，注意pop()总是弹出队列中的第一个元素 if(p.empty()) cout<<endl<<"空的队列";
//p.empty()为true时队列为空。
}
return 0;
动态数组vector:
C++的STL动态数组使用<vector>头文件
vector的基本操作有：
- l 构造vector: vector<T> vec。其中T是数据类型，可以是int、double等。
- l 插入x元素: vec.push_back(x)
- l 获取动态数组大小：vec.size()
- l 访问动态数组元素：vec[i],和数组一样操作
- l 修改动态数组元素：比如vec[1]=233,和数组一样操作
- l 清空动态数组：vec.clear()
示例代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector> //动态数组头文件
using namespace std;
int main()
{
vector<int> vec; //声明一个int类型的动态数组vec，注意现在动态数组是空的
vec.push_back(3); //通过push_back()方法在动态数组最后面插入一个新的元素3
vec.push_back(2); //...................................................2
vec.push_back(1); //...................................................1
vec.push_back(10); //...................................................10
for(int i=0;i<vec.size();i++) //vec.size()是获得动态数组vec的长度
{
cout<<vec[i]<<endl;
}
vec[0]=10; //修改元素的值，跟正常数组没区别 ，注意第一个元素下标也是0
vec[1]=9;
vec[2]=8;
vec[3]=7;
cout<<endl;
for(int i=0;i<vec.size();++i) //vec.size()是获得动态数组vec的长度
{
cout<<vec[i]<<endl;
}
cout<<endl<<"sort排序后"<<endl;
sort(vec.begin(),vec.end());
for(int i=0;i<vec.size();++i) //vec.size()是获得动态数组vec的长度
{
cout<<vec[i]<<endl;
}
cout<<endl;
vec.clear(); //清空动态数组
cout<<vec.size();
return 0;
}
快速排序sort
C++中排序函数sort，在头文件<algorithm>中
Sort函数有三个参数：
（1）第一个是要排序的数组的起始下标。
（2）第二个是要排序的数组的结束下标
（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，
Sortt函数的第三个参数可以用这样的语句告诉程序你所采用的排序原则
- less<数据类型>() 从小到大排序 如：sort(a,a+n,less<int>())
- greater<数据类型>() 从大到小排序 如：sort(a,a+n,greater<int>())
还可以不写第三个参数，此时默认的排序方法是从小到大排序。如：sort(a,a+n)
sort可以对任何线性数据排序（比如数组，vector...）
sort除了能对int、double等基础数据类型排序以外，
还能对自定义数据类型进行排序，比如结构体类型。请看后面的示例。
示例代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int a[10]={9,6,3,8,5,2,7,4,1,0},n=9; vector<int> v;//定义一个动态数组v struct PPtest//定义一个结构体
{
int x,y;
}p[4]={{1,2},{1,0},{2,1},{0,1}} ; //现在我们想对P[4]按照x值从小到大进行排序。
//我们定义一个比较函数int cmp(PPtest a,PPtest b)
//并把这个函数作为参数传递给sort
int cmp(PPtest a,PPtest b) //自定义数据类型排序
{
if(a.x==b.x) return a.y<b.y; //如果x值相等，就按照y的值从大到小排序
return a.x<b.x; // 按照x的值从大到小排序
} int main()
{
for(int i=0;i<=n;i++)
cout<<a[i]<<" "; //数组a排序前
cout<<endl; sort(a,a+n); //也可写成sort(a+0,a+n),表示对数组a的下标区间(0,n)进行排序
//默认从小到大排序，排序区间是(a+0,a+10)
//下标0 ,其实也可以这样写 sort(a,a+n，less<int>()) for(int i=0;i<=n;i++)
cout<<a[i]<<" ";//数组a排序后
cout<<endl; sort(a,a+n,greater<int>());
//加入第三个参数greater<int>()后 ，实现从大到小排序。
for(int i=0;i<=n;i++)
cout<<a[i]<<" ";//数组a排序后
cout<<endl; sort(p,p+4,cmp);//自定义排序，按照p.x的值从大到小排序
for(int i=0;i<=3;i++)
cout<<p[i].x<<" "<<p[i].y<<endl;//排序后的输出为 {0，1}，{1,2},{1,0},{2,1}
cout<<endl; v.push_back(5);//动态数据测试
v.push_back(8);
v.push_back(6);
v.push_back(3);
sort(v.begin(),v.end()); //对动态数组v[ ]进行排序 for(int i=0;i<=v.size()-1;i++)
cout<<v[i]<<" ";//动态数组排序后
cout<<endl; return 0;
}
优先队列：
l 优先队列的头文件是<queue>
l 优先队列： 先进的并不一定先出，先出的是最大(或者最小)的数值
l 从严格意义上来说：优先队列并不是队列,因为它并不遵循队列的FIFO(先进先出的原则)。
l 优先队列的时间复杂度为O（logn）。
优先队列可以按照自定义的一种方式（数据的优先级）来对队列中的数据进行动态的排序
每次的push和pop操作，队列都会动态的调整。以达到我们预期的方式来存储。
（比如说从小到大或从大到小）
例如：我们常用的操作就是对数据排序，优先队列默认的是数据大的优先级高
所以我们无论按照什么顺序push一堆数，最终在优先队列里总是top出最大的元素。
1、priority_queue <int> q; 定义一个变量名为q的优先队列 ，队内元素优先级是默认从大到小
2、priority_queue <int，vector<int>, greater<int> >q;
定义一个变量名为q的优先队列 ，队内元素优先级是从小到大 (感觉跟sort相似？)
3、自定义优先级：priority_queue<int>,vector<int>,cmp>q;
第一个参数是队列类型，第二个参数为容器类型。第三个参数为比较函数。（又跟sort相似？）
cmp为比较函数 。请看模板：在最后面。（比sort复杂一点，有重载运算什么之类的）目前可以不研究
- l 入队： q.push(x) 从队列q中加入x元素，x自己会在优先队列中找到自己的位置（从大到小或从小到大）
- l 出队： q.pop() 弹出（删除）q队列的最大或最小的一个元素，注意并不会返回被弹出的元素的值
- l 访问队首元素： q.top() 访问队首（最大或最小）的元素，不是最早被压入队列的元素
- l 访问队尾元素： ........ 优先队列没这个方法
- l 判断队列空： q.empty() 当优先队列为空时，返回true
- l 访问队列元素个数：q.size() 访问优先队列中元素的个数
- l 清空队列： 可以q.pop()依次弹出（删除），q.clear()方法不行，是错误的
示例代码一：
#include<iostream>
#include<cstdio>
#include<queue> //队列和优先队列的头文件
using namespace std;int main()
{
priority_queue<int>q;
//声明一个优先队列 ，注意：优先队列的元素排序默认是从大到小（int） priority_queue <int, vector<int>, greater<int> >q1;
//从小到大，注意的是greater<int> >,两个>之间一定有要空格。 int i,n;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>h[i]; //输入n个整数
q.push(h[i]); //把输入的数依次加入到优先队列q，动态调整
q1.push(h[i]); //把输入的数依次加入到优先队列q1，动态调整
}
cout<<endl<<endl; //优先队列从大到小（默认）
for(i=1;i<=n;i++)
{
cout<<q.top()<<" "; //top()总是访问队首元素（最大）,
q.pop();
// 将其弹出 ，注意pop()总是弹出优先队列中优先级最高的元素 （最大）
if(q.empty()) cout<<endl<<"队列已为空";
}
cout<<endl<<endl; //优先队列从小到大
for(i=1;i<=n;i++)
{
cout<<q1.top()<<" "; //top()总是访问队首元素（最小）,
q1.pop();
//将其弹出 ，注意pop()总是弹出优先队列中优先级最高的元素 （最小）
if(q1.empty()) cout<<endl<<"队列已为空";
}
cout<<endl<<endl; return 0;
}
示例代码二：自定义数据类型
//下面介绍自定义数据类型优先级的操作：
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int n;
struct Node//跟sort自定义有点相同，这里分为两个结构体来写，后面还有个cmp，
{
int x;
int y;
}dis[10];struct cmp//Node优先级规则
{
int operator()(Node a,Node b)//注意写法，跟sort不同 ，照着写，我也不明白operator
{
return a.x>b.x;//小的优先级高 , 一定要记住，跟sort相反
}
};//-----------------------------------------------------------------
struct cmp1 //结构体优先级规则
{
bool operator ()(int x, int y) //注意写法，跟sort不同 ，照着写，我也不明白operator
{
return x > y;//小的优先级高 , 一定要记住，跟sort相反
}
}; priority_queue<Node,vector<Node>,cmp> d; //自定义结构体优先级
priority_queue<int>q1; //默认，大的优先级高
priority_queue<int, vector<int>, cmp1>q2; //小的优先级高
//priority_queue <int, vector<int>, greater<int> >q2; //也是小的优先级高，可以替代上面。int main()
{
int i=0;
cin>>n;
for(int i=0;i<n;i++) //请输入数据3组，{1，2}，{3，1}，{2，5}用来测试
{
cin>>dis[i].x>>dis[i].y;
d.push(dis[i]); //插入数据
}
cout << endl;
while(!d.empty()) //逐步输出优先级大的
{
cout<<d.top().x <<" "<<d.top().y<<endl;
d.pop();
}
cout << endl;
for(int i=0;i<n;i++) //请输入测试数据 3个，依次是3 7 1
{
int b=0;
cin>>b;
q1.push(b);//从q1 队列 插入b
q2.push(b);
}
cout<<"q1优先队列"<<endl;
while(!q1.empty()) //访问q1队顶元素并输出队顶元素
{
cout<<q1.top() <<endl;
q1.pop();
}
cout << endl; cout<<"q2优先队列"<<endl;
while(!q2.empty()) //访问q1队顶元素并输出队顶元素
{
cout<<q2.top() <<endl;
q2.pop();
}
cout << endl;
return 0;
} /*
第一组
3
1 2
3 1
2 5
第二组：
3
7
1
*/
集合set
c++ set集合 参考文章https://www.cnblogs.com/zyxStar/p/4542835.html
集合是数学中的一个基本概念，通俗地理解，集合是由一些不重复的数据组成的。
比如{1,2,3}就是一个有1,2,3三个元素的集合。
c++的STL支持集合的高效插入、删除和查询操作，其时间复杂度都是O(logn)。
如果用数组，虽然插入的时间复杂度是O(1)，但是删除和查询都是O(n),时间效率低。
c++ set的基本操作：
- l #include<set>//集合头文件
- l 定义一个集合s: 比如set<int> s;定义一个整型集合s
- l 返回set集合s中的第一个元素： s.begin()
- l 返回set集合s中的最后一个元素： s.end()
- l 查找set集合s中的指定元素的个数： s.count(30),查找元素30有多少个？
- l 查找set集合s中的指定元素： s.find(20)，查找指定元素20
- l 删除set集合s中的所有元素： s.clear()
- l 判断set集合s是否为空： s.empty() 为空时返回true
- l 从set集合s中插入一个元素： s.insert()
- l 从set集合s中删除一个元素： s.erase()
- l 返回set集合s中元素的个数： s.size()
示例代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<set>//集合头文件
using namespace std;
int main()
{
set<int> s; // 声明一个整型s集合,初始是空的
s.insert(20); //{2} 用insert()方法向集合中插入一个新的元素。
s.insert(10); //{1,2} 插入元素1后集合会自动有序。
s.insert(30); //{1,2,3},每次插入元素后集合都会自动有序
s.insert(10); //{1,2,3}第二次插入1，重复元素，不会插入 //c++通过迭代器::iterator可以访问集合中的每个元素，可以不懂，记住用法就行了
set<int>::iterator it;//遍历之前先定义一个(::iterator)迭代器it
for(it = s.begin(); it != s.end(); it++)//遍历集合中的元素
{
cout<<(*it)<<" ";//实际上it就是个指针变量。*it是 获取it 指想某个变量的值。
}
cout<<endl;
s.erase(30);//{1,2} 删除指定元素 30
cout<<endl<<"删除30以后"<<endl; for(it = s.begin();it != s.end();++it)
cout<<(*it)<<" ";//实际上it就是个指针变量。*it是 获取it 指想某个变量的值。
cout<<endl<<endl;cout<<"查找指定元素20"<<endl; //遍历查找元素20
it = s.find(20); //查找键指定元素20
if (it != s.end()) //找到
cout << *it << endl;
else //未找到
cout << "未找到"<<endl;cout<<endl<<"查找有多少个30这样的元素"<<endl;//
if(s.count(30)) //可以用count()方法查找集合中的指定元素的个数。
cout<<s.count(30)<<endl;
else cout<<"没有30这个元素"<<endl<<endl;cout<<s.size()<<" "<<s.max_size()<<endl;
//输出集合中所有元素的个数及集合可以容纳最大的元素上限 s.clear();//清空集合
cout<<"清空集合后,集合中的元素为"<<" ";
cout<<s.size()<<endl; return 0;
}
C++中的STL中map用法详解 映射
参考文章：https://www.cnblogs.com/fnlingnzb-learner/p/5833051.html
注意：文章中像数组一样遍历好像不行。
https://www.cnblogs.com/qigaohua/p/5803629.html
map映射是指两个集合之间的元素的相互对应关系。通俗地说，就是一个元素对应另外一个元素。
众所周知，在定义数组时（如int array[100]），其实是定义了一个从int型到int型的映射，比如array[1]=28、array[3]=66就分别是将1映射到28、将3映射到66。一个double型数组则是将int映射到double型，例如db[0]=6.12，db[1]=10.02。但是，无论是什么类型，它总是将int型映射到其他类型。这似乎表现出一个弊端：当需要以其他类型作为关键字来映射时，会显得很不方便。例如有一本字典，上面提供了很多字符串和对应的页码，如果要用数组来表示“字符串-->页码”这样的对应关系，就会感觉不太好操作。这时，就可以用到map，因为map可以将任何基本类型映射到任何基本类型，也就可以建立string型到int型的映射。
比如有一个姓名集合{"Tom","Jone","Mary"},班级集合{1,2}。
姓名与班级之间可以有如下的映射关系：
class("Tom")=1, class("Jone")=2, class("Mary")=1。
我们称其中的姓名集合为 关键字集合(key)，班级集合为 值集合 (value)。
map的基本操作函数（常用）：
begin() 返回指向map头部的迭代器 end() 返回指向map末尾的迭代器
rbegin() 返回指向map尾部的反向迭代器 rend() 返回指向map头部的反向迭代器
clear(） 删除所有元素 empty() 如果map为空则返回true
count() 返回指定元素是否出现 find() 查找一个指定元素
insert() 插入元素 erase() 删除一个元素
size() 返回map中元素的个数 max_size() 返回可以容纳的最大元素个数
swap() 交换两个map，使用方法m1.swap(map2) ;m1和m2两个映射交换，而不是映射中的两个元素交换
代码示例：
#include<iostream>
#include<cstdio>
#include<string>
#include<map>//集合头文件
using namespace std;
int main ()
{
//数据的插入--第一种：用insert函数插入pair数据
map <int,string> mapStudent;//{}初始是空映射
mapStudent.insert(pair<int, string>(3, "student_three"));
mapStudent.insert(pair<int, string>(1, "student_one"));
//插入新的映射,映射会根据关键字key自动升序排序
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(2, "student_2"));
//如果关键字key已经有了，就是无效插入,就算值value不同。
//但是如果是数组的方式插入，就会覆盖原来的
//遍历map,第一种方法，使用前向迭代器 ，就是顺序遍历
map<int, string>::iterator iter;//定义一个前向迭代器iter，不明白没关系，记住使用方法
//map<元素类型,元素类型>::iterator 变量
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<<iter->first<<" "<<iter->second<<endl; //first对应map关键字key，second对应map的值value
cout<<endl<<"映射mapStudeng的大小为："<<mapStudent.size()<<endl<<endl;
//查询映射的大小
//数据的插入--第二种：像数组一样使用
map <string,int> DICT;//{}
DICT["Tom"]=1;//还可以像访问数组一样访问映射。
DICT["Jone"]=2;
DICT["Mary"]=1;
DICT["Tom"]=2;//就算已有关键字Tom,也会完全覆盖原有的映射
DICT["Test"];//如果这个映射不存在，自动建立一个新映射，默认Key值0
//输出测试
cout<<"测试映射的值是什么"<<endl;
cout<<DICT["Mary"]<<endl;//输出Mary的值1
cout<<DICT["Test"]<<endl;//输出Test的值0
cout<<endl<<endl;
//遍历map,第二种方法，使用反向迭代器 ，就是反向遍历
map<string,int>::reverse_iterator it; //map<元素类型,元素类型>::reverse_iterator 变量
for(it = DICT.rbegin();it != DICT.rend();++it)
//反向遍历map，注意不是begin()和end(),而是rbegin()和rend()
cout<<it->first<<"在班级 "<<it->second<<endl;
//first对应map关键字key，second对应map的值value
//删除映射，两种方法
//1、可以用关键字删除，比如m.erase(1),
//2、也可以成片的删除，如m.erase(m.begin(),m.end());
DICT.erase("Tom");//单独删除Tom关键字
cout<<endl<<"删除后Tom映射不见了"<<endl;
for(it = DICT.rbegin();it != DICT.rend();++it)
//反向遍历map，注意不是begin()和end(),而是rbegin()和rend()
cout<<it->first<<"在班级 "<<it->second<<endl;
//first对应map关键字key，second对应map的值value
cout<<endl<<"全部删除所有映射"<<endl;
DICT.erase(DICT.begin(),DICT.end()) ;//成片删除 跟DICT.clear效果一样DICT.clear();
cout<<DICT.size()<<endl;
/*查找并获取map中的元素（包括判定这个关键字是否在map中出现）：
有两种：1、用m.count() 用2、m.find()
第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,
count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了 */
cout<<endl<<"count查找...."<<endl;
map <string,int> m;//{}
m["Tom"]=2;
m["Jone"]=5;
m["Mary"]=3;
if(m.count("Tom"))//如果Tom出现
cout<<m.count("Tom")<<endl;//返回1
/*第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，
它返回数据所在位置的迭代器，如果map中没有要查找的数据，
它返回的迭代器等于end函数返回的迭代器 */
map<string,int>::iterator TEST;//定义一个迭代器TEST
cout<<endl<<"前向遍历"<<endl;
for(TEST=m.begin();TEST!=m.end();TEST++)//前向遍历
cout<<TEST->first<<" "<<TEST->second<<endl;
cout<<endl<<"find()查找...."<<endl;
TEST=m.find("Tom");
if(TEST!=m.end())//判断是否找到Tom，记住判断方法
{
cout<<"找到了，他的值是 "<<TEST->second<<endl;
m.erase(TEST); //测试用，删除Tom
}
else cout<<"没找到"<<endl;
//排序 map中的sort问题 ，略.................
return 0;
}
