vector、list、pair、unordered_map、unordered_set、stack、queue
参考文章：
（1）【apollo】泛型编程 与 STL
（2）c++ stack用法 入门必看 超详细
（3）C++中queue的用法（超详细，入门必看）
（4）C++——list的简介及使用
（5）C++中pair用法
（6）c++中map详解
（7）c++中unordered_map的用法的详述（包含unordered_map和map的区别）
（8）【总结】C++ 基础数据结构 —— STL之集合（set）用法详解
（9）C++常用语法——unordered_set

1 C++中vector用法

向量（vector）：连续存储的元素
头文件包含：#include <vector>

1.1 Vector容器简介

（1）vector是将元素置于一个动态数组中加以管理的容器
（2）vector可以随机存取元素（支持索引值直接存取，用[ ]或at()方法）
（3）vector尾部添加或移除元素很快。但是在中间或头部插入、移除就很费时。

1.2 Vector对象的构造

① 默认构造：使用默认构造函数构造出来的vector对象的size为0

vector<int> vec;
vector<float> vec;
vector<string> vec;
class A {};
vector<A*> vec; // 用于存放A对象指针的vector容器
vector<A> vec; // 用于存放A对象的vector容器

② 带参数构造

• vector(beg, end); // 构造函数将[beg, end)元素拷贝给自身
• vector(n,elem); // 构造函数将n个elem拷贝给自身
• vector(const vector& vec); // 拷贝构造函数

int A[] = {0, 1, 2, 3, 4, 5};
vector<int> vecA(A, A + 5);
vector<int> vec(vecA.begin(), vecA.end());
vector<int> vec(vecA.begin(), vecA.begin() + 3);
vector<int> vec(n, 0);
vector<int> vecD(vecA);
vector v4 = v1;

③ Vector的赋值

vector.assign(beg, end); // 将[beg, end)数据拷贝赋值给本身
vector.assign(n, elem); // 将n个elem拷贝赋值给本身
vector& operator=(const vector& vec); // 重载等号操作符
vector.swap(vec); // 将vec与本身的元素互换

vector<int> vecA, vecB, vecC, vecD;
int aaa[] = {0, 1, 2, 3, 4};
vecA.assign(aaa, aaa + 5);
vecB.assign(vecA.begin(), vecA.end());
vecC.assign(3, 9);
vecD = vecA;
vecA.swap(vecD);

使用vector.assign()时，会将vector中原本的元素都清空，再执行赋值操作

///计算vector中的元素数量
vector.size() ;
///指向容器中的第一个元素的迭代器（指针）
vector.begin();
///指向容器中的最后一个元素的下一位的迭代器（指针）,左闭右开
vector.end();///a = {1，2，3，4，5，6，7};
vector.assign(a.begin()+2,vector.end()-1 )
///vector = {3，4，5，6};

④ Vector的大小、Vector的访问方式（查改）

vector.size(); // 返回容器中元素的个数
vector.empty(); // 判断容器是否为空
vector.resize(num); // 重新指定容器的长度为num，若容器变长，则以默认值0填充新位置，如果容器变短，则末尾超出容器长度的元素被删除
vector.resize(num, elem); // 重新指定容器的长度为num，若容器变长，则以elem填充新位置，如果容器变短，则末尾超出容器长度的元素被删除

下表法：访问vector容器中的元素，下标越界，可能会导致程序异常终止，且不会输出异常原因。但是使用STL中vector提供的访问方法就能够给出报错原因。

vector.at(idx); // 返回索引idx所指的数据，如果idx越界，抛出out_of_range异常
vec[idx]; // 返回索引idx所指的数据，越界运行会报错

vector<int> vecInt; // 1, 3, 5, 7, 9
vecInt.at(2) == vecInt[2]; // 5
vecInt.at(2) = 8; // 1, 3, 8, 7, 9
int if = vecInt.front(); // 1
int ib = vecInt.back(); // 9
vecInt.front() = 11; // 11, 3, 8, 7, 9
vecInt.back() = 19; // 11, 3, 8, 7, 19

⑤ vector的插入和 删除 （“增删”）
vector末尾添加和删除操作

vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.pop_back();

vector的插入

• vector.insert(pos, elem); // 在pos位置插入一个elem元素的拷贝，返回新数据的位置
• vector.insert(pos, n, elem); // 在pos位置插入n个elem数据，无返回值
• vector.insert(pos, beg, end); // 在pos位置插入[beg, end)区间的数据，无返回值

pos应该是指针或者迭代器，不能是下标
⑥ 打印vector中的所有元素

vector<int> vec = {1, 2, 3, 4, 5};
for (int i = 0; i < vec.size(); i++) {cout << vec[i] << " ";
}

⑦ vector容器中迭代器的基本使用

vector<int>::iterator iter;
vector容器的迭代器属于“随机访问迭代器”：迭代器一次可以移动多个位置

vector<int>::iterator iter = v.begin();
for (auto iter = v.begin(); iter != v.end(); iter++) *iter = 0;

2 C++中stack用法

2.1 基本操作

Stack：先进后出
包含头文件：#include <stack>

stack<int> stInt;
stack<float> stFloat;
stack<string> stString;

基本使用方法：
① push：往栈头添加元素

stack.push(elem);

② pop：往栈头移除第一个元素

stack.pop();

Tip：

• stack容器没有迭代器，不允许遍历。要想访问元素只有出栈这个方法
• stack.pop()函数删除栈顶元素，返回值为void，不会返回被删除的栈顶元素值
• 使用stack.top()函数就能够得到栈顶元素，不会删除栈顶元素，通常top和pop两个相结合使用

③ empty：判断是否为空，若为空，返回值为true；否则为false

if (!stInt.empty()) {}

④ size：返回堆栈的大小

int size = stInt.size();

⑤ top：返回栈顶元素

2.2 从stack到string

栈中的数据是不允许随机访问的，就是不能像数组那样用下标访问，也不能遍历栈内的元素，这是很局限的。实际上，我们经常使用的string类型就是一种栈结构，但是我们可以通过下标访问元素。
string的栈相关的成员函数

empty() //堆栈为空则返回真 
pop_back() //移除栈顶元素 
push_back() //在栈顶增加元素 
size() //返回栈中元素数目 
back() //返回栈顶元素 

#include <iostream>
#include <string> // string包括了一些字符串操作的库函数，但用string时是不用引入这个头文件的
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
int main()
{string s;//定义一个字符串s.push_back('1');//往栈里放入一个元素1s.push_back('2');//往栈里放入一个元素2s.push_back('3'); //往栈里放入一个元素3cout<<"按顺序放入字符1、2、3后，目前string里的元素：" ;for(int i=0;i<s.size();i++){cout<<s[i]<<' ';}cout<<endl; cout<<"s.pop_back()="<<s.size()<<endl;//s.size()返回string内字符的个数  cout<<"s.empty()="<<s.empty()<<endl; //判断栈是否为空，值为1代表空，0代表非空，用s.size()同样可以判断 ，s.size()的值为0就代表空的 cout<<"s.back()="<<s.back()<<endl;//查看栈顶的元素 cout<<endl;s.pop_back();//弹出栈顶元素 cout<<"s.pop_back()后，目前string里的元素：";for(int i=0;i<s.size();i++){//可以通过下标随机访问元素 cout<<s[i]<<' ';}cout<<endl; cout<<"s.size()="<<s.size()<<endl;cout<<"s.empty()="<<s.empty()<<endl; cout<<"s.back()="<<s.back()<<endl;cout<<endl;s.pop_back();cout<<"s.pop_back()后，目前string里的元素：";for(int i=0;i<s.size();i++){cout<<s[i]<<' ';}cout<<endl; cout<<"s.size()="<<s.size()<<endl;cout<<"s.empty()="<<s.empty()<<endl; cout<<"s.back()="<<s.back()<<endl;cout<<endl;s.pop_back();cout<<"s.pop_back()后，目前的string是空的"<<endl;cout<<"s.size()="<<s.size()<<endl;cout<<"string是空的就不能用s.back()访问栈顶元素了" <<endl; cout<<"s.empty()="<<s.empty()<<endl; return 0;
}

运行结果：

按顺序放入字符1、2、3后，目前string里的元素：1 2 3
s.pop_back()=3
s.empty()=0
s.back()=3s.pop_back()后，目前string里的元素：1 2
s.size()=2
s.empty()=0
s.back()=2s.pop_back()后，目前string里的元素：1
s.size()=1
s.empty()=0
s.back()=1s.pop_back()后，目前的string是空的
s.size()=0
string是空的就不能用s.back()访问栈顶元素了
s.empty()=1

2.3 从stack到vector

vector的栈相关的成员函数

empty() //堆栈为空则返回真 
pop_back() //移除栈顶元素 
push_back() //在栈顶增加元素 
size() //返回栈中元素数目 
back() //返回栈顶元素 

#include<iostream>//c++标准头文件，可以使用cout,cin等标准库函数 
#include<vector>//使用vector时需要的头文件 
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){vector<int> v;//定义一个int类型的stackv.push_back(1);//往vector里放入一个元素1v.push_back(2);//往vector里放入一个元素2v.push_back(3); //往vector里放入一个元素3cout<<"按顺序放入字符1、2、3后，目前vector里的元素：" ;for(int i=0;i<v.size();i++){//可以通过下标随机访问元素 cout<<v[i]<<' ';}cout<<endl; cout<<"v.pop_back()="<<v.size()<<endl;//v.size()返回vector内元素的个数  cout<<"v.empty()="<<v.empty()<<endl; //判断栈是否为空，值为1代表空，0代表非空，用v.size()同样可以判断 ，v.size()的值为0就代表空的 cout<<"v.back()="<<v.back()<<endl;//查看栈顶的元素 cout<<endl;v.pop_back();//弹出栈顶元素 cout<<"v.pop_back()后，目前vector里的元素：";for(int i=0;i<v.size();i++){cout<<v[i]<<' ';}cout<<endl; cout<<"v.size()="<<v.size()<<endl;cout<<"v.empty()="<<v.empty()<<endl; cout<<"v.back()="<<v.back()<<endl;cout<<endl;v.pop_back();cout<<"v.pop_back()后，目前vector里的元素：";for(int i=0;i<v.size();i++){cout<<v[i]<<' ';}cout<<endl; cout<<"v.size()="<<v.size()<<endl;cout<<"v.empty()="<<v.empty()<<endl; cout<<"v.back()="<<v.back()<<endl;cout<<endl;v.pop_back();cout<<"v.pop_back()后，目前的vector是空的"<<endl;cout<<"v.size()="<<v.size()<<endl;cout<<"vtring是空的就不能用v.back()访问栈顶元素了" <<endl; cout<<"v.empty()="<<v.empty()<<endl; return 0;
}

运行结果：

按顺序放入字符1、2、3后，目前vector里的元素：1 2 3
v.pop_back()=3
v.empty()=0
v.back()=3v.pop_back()后，目前vector里的元素：1 2
v.size()=2
v.empty()=0
v.back()=2v.pop_back()后，目前vector里的元素：1
v.size()=1
v.empty()=0
v.back()=1v.pop_back()后，目前的vector是空的
v.size()=0
vtring是空的就不能用v.back()访问栈顶元素了
v.empty()=1

push与emplace的异同点：

• 对于int、double等内置数据类型而言，push()和emplace()是相同的
• 对于自定义数据类型而言，使用push()前必须先将要添加的对象构造出来(实例化)，而使用emplace()既可以填入实例化的对象也可以填入对象的构造参数

3 C++中queue用法

queue：先进先出
包含头文件：#include <queue>

queue的定义 :

queue<int> q1;
queue<double> q2;
queue<string> q3;
queue<结构体类型> q4;

基本使用方法：

back()  // 返回队列中最后一个元素 
empty() // 判断队列是否为空 
front() // 返回队列中的第一个元素 
pop()   // 删除队列的第一个元素 
push()  // 在队列末尾加入一个元素 
size()  // 返回队列中元素的个数 

#include <iostream>
#include <queue>
using namespace std;
int main()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()) {cout << q.front() << " ";q.pop();	}
}

运行结果：

1 2 3 4

4 C++中list用法

4.1 list构造

list<int> lt1;	// 构造int类型的空容器
list<int> lt2(3, 2);  // 构造含有3个2的int类型容器
list<int> lt3(lt2);  // 拷贝构造lt2
string s("hello");
list<char> lt4(s.begin(), s.end());  // 利用迭代器构造

4.2 list插入和删除数据

push_front和pop_front

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> lt;// 头插数据lt.push_front(1);lt.push_front(2);lt.push_front(3);for (auto e : lt){cout << e << " ";}cout << endl;// 头删数据lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

运行结果

3 2 1
2 1

push_back和pop_back

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> lt;// 尾插数据lt.push_back(1);lt.push_back(2);lt.push_back(3);for (auto e : lt){cout << e << " ";}cout << endl;// 尾删数据lt.pop_back();for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

运行结果：

1 2 3
1 2

insert支持三种插入方式:

• 在指定位置插入数据
• 在指定位置插入n个值为val的数
• 在指定位置插入一段迭代器区间（左闭右开）

int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);list<int>::iterator pos = find(lt.begin(), lt.end(), 2);lt.insert(pos, 4); //在2的位置插入4for (auto e : lt){cout << e << " ";}cout << endl; pos = find(lt.begin(), lt.end(), 3);lt.insert(pos, 3, 5); //在3的位置插入3个5for (auto e : lt){cout << e << " ";}cout << endl;vector<int> v{ 6, 6 };pos = find(lt.begin(), lt.end(), 1);lt.insert(pos, v.begin(), v.end()); //在1的位置插入2个6for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

运行结果：

1 4 2 3
1 4 2 5 5 5 3
6 6 1 4 2 5 5 5 3

erase有两种删除方式:

• 删除指定位置数据
• 删除指定迭代器区间中的数据

int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator pos = find(lt.begin(), lt.end(), 2);lt.erase(pos); // 删除2for (auto e : lt){cout << e << " ";}cout << endl;pos = find(lt.begin(), lt.end(), 3);lt.erase(pos, lt.end()); //删除3及其之后的元素for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

运行结果：

1 3 4
1

4.3 list迭代器的使用

• begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
• rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

#include <iostream>
#include <list>using namespace std;int main()
{string s("hello");list<char> lt(s.begin(), s.end());//正向迭代器遍历容器list<char>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;//反向迭代器遍历容器list<char>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";rit++;}cout << endl;return 0;
}

运行结果：

h e l l o
o l l e h

4.4 基本操作

front和back

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << lt.front() << endl;cout << lt.back() << endl;return 0;
}

运行结果：

1
4

empty和size

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);cout << lt.size() << endl;cout << lt.empty() << endl;
}

运行结果：

2
0

4.5 list相关操作函数

swap：用于交换两个容器的内容

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt1(3, 2);list<int> lt2(2, 3);lt1.swap(lt2); // 交换两个容器的内容for (auto a : lt1) {cout << a << " ";}return 0;
}

运行结果：

3 3

clear：用于清空容器，清空后容器的size为0

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt(3, 2);lt.clear();cout << lt.size() << endl;return 0;
}

运行结果：

0

sort：将容器当中的数据排序（升序）

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt;lt.push_back(2);lt.push_back(1);lt.push_back(4);lt.push_back(3);for (auto e : lt){cout << e << " ";}cout << endl;lt.sort();for (auto e : lt){cout << e << " ";}cout << endl;
}

运行结果：

2 1 4 3
1 2 3 4

resize操作方式有两种：

• 当所给值大于当前的size时，将size扩大到该值，扩大的数据为第二个所给值，若未给出，则默认为容器所存储类型的默认构造函数所构造出来的值
• 当所给值小于当前的size时，将size缩小到该值

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt(3, 3);for (auto e : lt){cout << e << " ";}cout << endl;lt.resize(5, 4); //将size扩大为5，扩大的值为4for (auto e : lt){cout << e << " ";}cout << endl;lt.resize(2); //将size缩小为2for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

运行结果：

3 3 3
3 3 3 4 4
3 3

remove：移除指定元素

int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(2);lt.push_back(3);for (auto e : lt){cout << e << " ";}cout << endl; lt.remove(2); // 删除容器当中值为2的元素for (auto e : lt){cout << e << " ";}cout << endl; return 0;
}

运行结果：

1 2 2 3
1 3

unique：去除连续重复的元素（如果要去除所有重复的元素需要先排序）

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(3);lt.push_back(2);lt.push_back(3);lt.push_back(2);for (auto e : lt){cout << e << " ";}cout << endl;lt.unique();// 去除连续重复的元素for (auto e : lt){cout << e << " ";}cout << endl;lt.sort();// 排序lt.unique();for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

运行结果：

1 2 3 3 2 3 2
1 2 3 2 3 2
1 2 3

reverse：将容器当中元素的进行逆置

#include <iostream>
#include <list>using namespace std;int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);for (auto e : lt){cout << e << " ";}cout << endl;lt.reverse();// 逆置for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

运行结果：

1 2 3
3 2 1

5 C++中pair用法

pair：将2个数据整合成一组数据，本质其实就是个结构体，它含有两个成员变量first和second。
包含头文件：#include <utility>

template<class T1,class T2> struct pair

#include<utility>
#include<iostream>using namespace std;
int main()
{pair<string, string>s1;s1.first="ctx";s1.second="666";cout<<s1.first<<endl;cout<<s1.second<<endl;cout<<s1.first<<s1.second<<endl;
}

定义

pair<int, int> p1;
pair<int, double> p2;
pair<double, string> p3;
pair<string, vector<int>> p4;

初始化赋值

pair<string, string> p1("a", "b");
pair<string, int> p2("a", 23);
pair<string, int> p3(p2);  // 拷贝p2的值来初始化p3 
pair<string, int> p3 = p2; // 将p2的值赋值给p3

typedef简化pair的定义

typedef pair<int, int> intInt;
intInt c1(1, 2);

pair中的make_pair：一般make_pair都使用在需要pair做参数的位置，可以直接调用make_pair生成pair对象。 另一个使用的方面就是pair可以接受隐式的类型转换，这样可以获得更高的灵活度。

pair<int, double> p1;
p1 = make_pair(1, 1.2);
// 第一个的second变量是float类型
// 而make_pair函数会将second变量都转换成double类型。
std::pair<int, float>(18, 1.78);
std::make_pair(18, 1.78);

6 C++中map用法

map是STL的一个关联容器，以键值对存储的数据，map内部有序（自动排序，单词时按照字母序排序），查找时间复杂度为O(logn)。
包含头文件：#include <map>
定义

map<string, int> my_map;
typedef map<string,int> My_Map;
My_Map my_map;

6.1 基本方法

• my_map.insert()或按照数组直接赋值：插入
• my_map.find()：查找一个元素
• my_map.clear()：清空
• my_map.erase()：删除一个元素
• my_map.size()：map的长度大小
• my_map.begin()：返回指向map头部的迭代器
• my_map.end()：返回指向map末尾的迭代器
• my_map.rbegin()：返回一个指向map尾部的逆向迭代器
• my_map.rend()：返回一个指向map头部的逆向迭代器
• my_map.empty()：map为空时返回true
• swap()：交换两个map，两个map中所有元素都交换

6.2 map插入数据的几种方法

用insert函数插入pair数据：

map<int, string> my_map;
my_map.insert(pair<int, string>(1, "a"));

用insert函数插入value_type数据:

map<int,string> my_map;
my_map.insert(map<int,string>::value_type(1,"first"));
my_map.insert(map<int,string>::value_type(2,"second"));map<int,string>::iterator it;           //迭代器遍历
for(it=my_map.begin();it!=my_map.end();it++)cout<<it->first<<it->second<<endl;

用数组的方式直接赋值:

map<int, string> my_map;
my_map[1] = "first";

6.3 查找元素（判定这个关键字是否在map中出现）

用count函数来判断关键字是否出现，其缺点是无法定位元素出现的位置。由于map一对一的映射关系，count函数的返回值要么是0，要么是1

map<string, int> my_map;
my_map["first"] = 1;
cout << my_map.count("first") << endl;

用find函数来定位元素出现的位置，它返回一个迭代器，当数据出现时，返回的是数据所在位置的迭代器；若map中没有要查找的数据，返回的迭代器等于end函数返回的迭代器。

#include <map>  
#include <string>  
#include <iostream>  using namespace std;  int main()  
{  map<int, string> my_map;  my_map.insert(pair<int, string>(1, "student_one"));  my_map.insert(pair<int, string>(2, "student_two"));  my_map.insert(pair<int, string>(3, "student_three"));  map<int, string>::iterator it;  it = my_map.find(1);  if(it != my_map.end())  cout<<"Find, the value is "<<it->second<<endl;      else  cout<<"Do not Find"<<endl;  return 0;  
}
//通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据iterator->first和iterator->second，分别代表关键字和value值。

6.4 删除元素

#include <map>  
#include <string>  
#include <iostream>  using namespace std;  int main()  
{  map<int, string> my_map;  my_map.insert(pair<int, string>(1, "one"));  my_map.insert(pair<int, string>(2, "two"));  my_map.insert(pair<int, string>(3, "three"));  //如果你要演示输出效果，请选择以下的一种，你看到的效果会比较好//如果要删除1,用迭代器删除map<int, string>::iterator it;  it = my_map.find(1);  my_map.erase(it);                   //如果要删除1，用关键字删除int n = my_map.erase(1);            //如果删除了会返回1，否则返回0//用迭代器，成片的删除//一下代码把整个map清空my_map.erase( my_map.begin(), my_map.end() );  //成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合//自个加上遍历代码，打印输出吧return 0;
}  

6.5 排序，按value排序

map中元素是自动按key升序排序（从小到大）的；按照value排序时，想直接使用sort函数是做不到的，sort函数只支持数组、vector、list、queue等的排序，无法对map排序，那么就需要把map放在vector中，再对vector进行排序。

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;bool cmp(pair<string,int> a, pair<string,int> b) {return a.second < b.second;
}int main()
{map<string, int> ma;ma["Alice"] = 86;ma["Bob"] = 78;ma["Zip"] = 92;ma["Stdevn"] = 88;vector< pair<string,int> > vec(ma.begin(),ma.end());//或者：//vector< pair<string,int> > vec;//for(map<string,int>::iterator it = ma.begin(); it != ma.end(); it++)//    vec.push_back( pair<string,int>(it->first,it->second) );sort(vec.begin(),vec.end(),cmp);for (vector<pair<string,int>>::iterator it = vec.begin(); it != vec.end(); ++it){cout << it->first << " " << it->second << endl;}return 0;
}

7 C++中unordered_map用法

包含头文件：#include <unordered_map>

unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的

map和unordered_map各自优缺点

• map

优点：

• 有序性，这是map结构最大的有点，其元素的有序性在很多应用中都会简化很多的操作
• 红黑树，内部实现一个红黑树使得map的很多操作在logn的时间复杂度下就可以实现，因此效率非常的高

缺点：

• 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

适用处：对于那些有顺序要求的问题，用map会更高效一些

• unordered_map

优点：因为内部实现了哈希表，因此其查找速度非常的快
缺点：哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map 会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

定义

unordered_map<string, string> umap;

初始化

unordered_map<string, string> umap{{"as", "as"},{"s", "ass"},{"v", "qwe"}};

调用 unordered_map 模板中提供的复制（拷贝）构造函数，将现有 unordered_map 容器中存储的键值对，复制给新建 unordered_map 容器

unordered_map<string, string> umap2(umap);

包含 umap 容器中除第 1 个键值对外的所有其它键值对

unordered_map<string, string> umap2(++umap.begin(), umap.end());

map和unordered_map的使用

unordered_map的用法和map是一样的，提供了insert，size，count等操作，并且里面的元素也是以pair类型来存储的，其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的。

#include<iostream>
#include<unordered_map>
#include<map>
#include<string>
using namespace std;int main()
{// 注意：c++11才开始支持括号初始化unordered_map<int, string> myMap = {{5, "zhangsan"},{6, "lisi"}};  // 使用{}赋值myMap[2] = "wanger";  // 使用[ ] 进行当个插入，若已存在键值2，则赋值修改，若无则插之。myMap.insert(pair<int, string>(3, "mazi"));  // 使用insert和pair插入。// 遍历输出+迭代器的使用。auto iter = myMap.begin();  // auto自动识别为迭代器类型unordered_map<int, string>::iteratorwhile(iter != myMap.end()){cout << iter->first << "," << iter->second << endl;++iter;}// 查找元素并输出 + 迭代器的使用auto iterator = myMap.find(6);  // find()返回一个指向2的迭代器。if(iterator != myMap.end())cout << endl << iterator->first << "," << iterator->second << endl;system("pause");return 0;
}

运行结果：

3,mazi
2,wanger
6,lisi
5,zhangsan6,lisi

c++ unordered_map容器的成员方法

8 C++中set用法

set是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高。set 和 multiset 的区别是：set 插入的元素不能相同，但是 multiset 可以相同。
set特点：

• 每个元素的键值都唯一，不允许两个元素有相同的键值
• 所有元素都会根据元素的键值自动排序（默认从小到大）
• set 中的元素不像 map 那样可以同时拥有实值(value)和键值(key)，只能存储键，是单纯的键的集合
• set 中元素的值不能直接被改变
• set 支持大部分的map的操作，但是 set 不支持下标的操作，而且没有定义mapped_type类型

包含头文件：#include <set>

8.1 set 的基本操作

set 的定义及初始化

set<Type> s						      // 定义一个set容器
set<Type> s(s1)			              // 定义一个set容器，并用容器s1来初始化
set<Type> s(b, e)					  // b和e分别为迭代器的开始和结束的标记
set<Type> s(s1.begin(), s1.begin()+3) // 用容器s1的第0个到第2个值初始化s
set<Type> s(a, a + 5)      		      // 将a数组的元素初始化vec向量，不包括a[4]
set<Type> s(&a[1], &a[4]) 			  // 将a[1]~a[4]范围内的元素作为s的初始值

set 的基本操作

s.begin()					// 返回指向第一个元素的迭代器
s.end()						// 返回指向最后一个元素的迭代器
s.clear()					// 清除所有元素
s.count()					// 返回某个值元素的个数
s.empty()					// 如果集合为空，返回true，否则返回false
s.equal_range()				// 返回集合中与给定值相等的上下限的两个迭代器
s.erase()					// 删除集合中的元素
s.find(k)					// 返回一个指向被查找到元素的迭代器
s.insert()					// 在集合中插入元素
s.lower_bound(k)			// 返回一个迭代器，指向键值大于等于k的第一个元素
s.upper_bound(k)			// 返回一个迭代器，指向键值大于k的第一个元素
s.max_size()				// 返回集合能容纳的元素的最大限值
s.rbegin()					// 返回指向集合中最后一个元素的反向迭代器
s.rend()					// 返回指向集合中第一个元素的反向迭代器
s.size()					// 集合中元素的数目

8.2 set 的用法

#include <iostream>
#include <set>
using namespace std;
int main(){set<int> s;s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set的size值为 ："<<s.size()<<endl;cout<<"set的maxsize的值为 ："<<s.max_size()<<endl;cout<<"set中的第一个元素是 ："<<*s.begin()<<endl;cout<<"set中的最后一个元素是:"<<*s.end()<<endl;s.clear();if(s.empty())cout<<"set为空"<<endl;cout<<"set的size值为 ："<<s.size()<<endl;cout<<"set的maxsize的值为 ："<<s.max_size()<<endl;return 0;
}

一共插入了4个数，但是集合中只有3个数并且是有序的，说明了set集合的两个特点，有序和不重复

count() 的用法

//返回某个值元素的个数
#include <iostream>
#include <set>
using namespace std;
int main(){set<int> s;s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set 中 1 出现的次数是 ："<<s.count(1)<<endl;cout<<"set 中 4 出现的次数是 ："<<s.count(4)<<endl;return 0;
}

count() 用来查找set中某个键值出现的次数，但因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了，所以这个函数在set中并不是很实用

erase() 的用法

#include <iostream>
#include <set>
using namespace std;
int main(){set<int> s;set<int>::const_iterator it;set<int>::iterator first;set<int>::iterator second;for(int i=1; i<=10; ++i)s.insert(i);//第一种删除，删掉1s.erase(s.begin());//第二种删除，删掉2和3first = s.begin();second = s.begin();second++;second++;s.erase(first,second);//第三种删除，删掉8s.erase(8);cout<<"删除后 set 中元素是 ：";for(it=s.begin(); it!=s.end(); ++it)cout<<*it<<" ";cout<<endl;return 0;
}

find() 的用法

//返回一个指向被查找到元素的迭代器，如果没找到则返回end()
#include <iostream>
#include <set>
using namespace std;
int main(){int a[] = {4,5,6};set<int> s(a,a+3);set<int>::iterator it;if((it=s.find(4))!=s.end())cout<<*it<<endl;return 0;
}

insert() 的用法

#include <iostream>
#include <set>
using namespace std;
int main(){int a[] = {1,2,3};set<int> s;set<int>::iterator it;s.insert(a,a+3);for(it=s.begin(); it!=s.end(); ++it)cout<<*it<<" ";cout<<endl;pair<set<int>::iterator,bool> pr;pr=s.insert(5);if(pr.second)cout<<*pr.first<<endl;cout<<"插入数值之后的set中有："<<endl;for(it=s.begin(); it!=s.end(); ++it)cout<<*it<<" ";cout<<endl;return 0;
}

lower_bound()、upper_bound() 的用法

#include <iostream>
#include <set>
using namespace std;
int main(){set<int> s;s.insert(1);s.insert(3);s.insert(4);s.insert(6);cout<<*s.lower_bound(1)<<endl; // 1cout<<*s.lower_bound(2)<<endl; // 3cout<<*s.upper_bound(3)<<endl; // 4return 0;
}

equal_range() 的用法

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main(){set<int> s;set<int>::iterator it;for(int i=1; i<=5; ++i)s.insert(i); //向set中加入数据for(it=s.begin(); it!=s.end(); ++it)cout<<*it<<" ";  //输出set中的数据cout<<endl;pair<set<int>::const_iterator,set<int>::const_iterator> pr;pr=s.equal_range(3);cout<<"第一个大于等于3的数是："<<*pr.first<<endl;cout<<"第一个大于3的数是： "<<*pr.second<<endl;return 0;
}

运行结果：

1 2 3 4 5 
第一个大于等于3的数是：3
第一个大于3的数是：4

自定义比较函数

• 元素不是结构体

 //自定义比较函数myComp,重载“（）”操作符
struct myComp{bool operator()(const your_type &a,const your_type &b){return a.data > b.data;}
}
set<int,myComp>s;
set<int,myComp>::iterator it;

• 元素是结构体

//可以直接将比较函数写在结构体内
struct Info{string name;float score;//重载“<”操作符，自定义排序规则bool operator < (const Info &a) const{//按score从大到小排列return a.score<score;}
}set<Info> s;
set<Info>::iterator it;

9 C++中unordered_set用法

unordered_set 容器，可直译为“无序 set 容器”。即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。

包含头文件：#include <unordered_set>

9.1 unordered_set的初始化

创建空的set

unordered_set<int> set1;

拷贝构造

unordered_set<int> set2(set1);

使用迭代器构造

unordered_set<int> set3(set1.begin(), set1.end());

使用数组作为其初值进行构造

unordered_set<int> set4(arr,arr+5);

移动构造

unordered_set<int> set5(move(set2));

使用处置列表进行构造

unordered_set<int> set6 {1,2,10,10};

9.2 unordered_set的常用内置函数

empty()函数——判断是否为空

set1.empty();

find()函数——查找:找到返回迭代器，失败返回end()

set1.find(2);

count()函数——出现次数

set1.count(2);

insert()函数——插入元素

//插入元素，返回pair<unordered_set<int>::iterator, bool>
set1.insert(3);
//使用initializer_list插入元素
set1.insert({1,2,3});
//指定插入位置，如果位置正确会减少插入时间，返回指向插入元素的迭代器
set1.insert(set1.end(), 4);
//使用范围迭代器插入
set1.insert(set2.begin(), set2.end());

9.3 关于insert函数的返回值

insert()只传入单个参数（待插入元素）

• 会返回一个 pair 对象
• 这个 pair 对象包含一个迭代器，以及一个附加的布尔值用来说明插入是否成功
• 如果元素被插入，返回的迭代器会指向新元素
• 如果没有被插入，迭代器指向阻止插入的元素

auto pr = words.insert("ninety"); // Returns a pair - an iterator & a bool value

insert()传入两个参数（迭代器+待插入元素）

• 可以用一个迭代器作为insert()的第一个参数，它指定了元素被插入的位置
• 在这种情况下，只会返回一个迭代器

auto iter = words.insert (pr.first, "nine"); // 1st arg is a hint. Returns an iterator

insert()传入初始化列表

• 插入初始化表中的元素
• 在这种情况下，什么都没有返回

words.insert({"ten", "seven", "six"});  // Inserting an initializer list

emplace()函数——插入元素(转移构造)

//使用转移构造函数添加新元素3，比insert效率高
set1.emplace(3);

erase()函数——删除元素

//删除操作，成功返回1，失败返回0
set1.erase(1);
//删除操作，成功返回下一个pair的迭代器
set1.erase(set1.find(1));
//删除set1的所有元素，返回指向end的迭代器
set1.erase(set1.begin(), set1.end());

bucket_count()函数——篮子数目

//返回容器中的篮子总数
set1.bucket_count();

bucket_size()函数——篮子中元素数目

//返回1号篮子中的元素数
set1.bucket_size(1);

bucket()函数——在哪个篮子

//元素1在哪一个篮子
set1.bucket(1);

clear()函数——清空

set1.clear();

load_factor()函数——负载因子

//负载因子，返回每个篮子元素的平均数，即size/float(bucket_count);
set1.load_factor();

rehash()函数——设置篮子数目并重新分布

//设置篮子的数量为20，并且重新rehash
set1.rehash(20);

---

本文详解了STL中的vector、stack、queue、list、pair、map、unordered_map、set、unordered_set，不正之处望读者指教。