一、基本概念
在C语言中,很多东西都需要自己实现,例如用数组模拟栈和队列等等有些复杂的操作实现起来会非常麻烦。
因此, C++提供了标准模板库(Standard Template Library, STL) ,其中封装了很多非常实用的容器,不需要费力去实现他 们的细节而直接调用函数来实现很多功能,十分方需便。
二、栈和队列
栈(stack)又称堆栈,是只能在某一端插入和删除的特殊线性表。具有先进后出(FILO, first in last out)的特性。
栈(stack)在STL 中的定义：
stack<typename> name;
例子：
stack<int> name;
stack<double> name;
stack<node> name;
stack常用函数：
队列: queue,遵循先进先出的原则。
队列是线性表的一种,在操作数据元素时,和栈一样,有自己的规则:使用队列存取数据元素时，数据元素只能从表的一端进入队列，另一端出队列
队列(queue)在STL中的定义：
queue<typename> name;
例子：
queue<int> que;
queue常用函数：
优先队列:
优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性，就是队列中优先级最大的元素总是位于队首。
通俗来讲：
通过优先队列可以实现快速获取极值<最大、最小>
普通优先队列定义:
priority_queue<int,vector<int>,greater<int> > q1;//这里需要一个空格,以防止识别成位移运算符
priority_queue<int,vector<int>,less<int> >q1 //或是 priority_queue<int> q1
递增greater函数对象排序： q1.top()可访问到队列最小值
递减less函数对象排序： q1.top()可访问到队列最大值
优先队列元素为结构体类型时的运算符重载
元素的比较规则默认按元素值由大到小排序，可以重载"<"操作符来重新定义比较规则。结构体优先队列：
struct node {
int x, y;
friend bool operator < (node a, node b) return a.x > b.x;//结构体中，x小的优先级高
priority_queue<node>q;
};
优先队列常用函数：
三、动态数组
我们为什么要用动态数组呢？
有时我们会碰到使用普通数组会超内存的情况，这种情况使用vector会让问题的解决便捷很多。vector又称动态数组,也就是长度可以根据需要而自动改变的数组。
vector的定义：
vector<int> name;
vector<double> name; vector<node> name;
vector<vector<int> > name; //两个>之间一定一定要加空格！！
定义完之后会得到一个空的vector,通常我们需要对它进行初始化:
已知vector一般有两种访问方式：通过下标访问
vector<int> v{2, 1, 3, 5, 3};
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
或通过迭代器访问:
vector<int> v{2, 1, 3, 5, 3};
for(vector<int>::iterator it=v.begin(); it!=v.end(); it++) cout << *it << endl;
}
vector常用函数：
二维vector的定义：
方式1. vector < vector > V;
其中, vector表示内层的vector，因此vector<vector >就表示外层的vector，即二维vector。为了访问二维vector中的元素,可以使用两个下标,例如: v[2][]=1;其中,表示外层vector的下标,j表示内层vector的下标。
方式2.vector v[100];
但如果v需要存储的元素数量超过100个，就会出现访问越界的情况。
四、集合set
set (集合)是C++STL中的一种关联式容器,它内部使用红黑树(一种自平衡二叉搜索树）来实现元素的有序存储。
特点是: 自动去重、自动排序,可以快速查找、插入和删除元素。
定义：
set<int> name;
set<double> name; set<node> name;
set<set<int> > name; //两个>之间要加空格
访问：
set只能通过迭代器访问，如
set<int> s{1,0,0,8,6};
for(set<int>：：iterator it=s.begin(); it!=s.end(); it++){
cout<<*it<<" ";
set常用函数：
set常用查询函数：
在C++11中, auto关键字可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型，例如：
如果需要有相同元素的集合,需要使用multiset,multiset的使用方法与set的使用方法基本相同。
unordered_set 是 C++ STL 中的无序集合容器，可以用于存储一组唯一的元素。
五，映射map
map （映射）也是常用的STL容器。
它可以将任何基本类型映射到任何基本类型，也就可以建立string型到int型的映射。
如果是int映射int,就相当于是普通的int型数组。
【定义】
map<key, value> mp;
【例子】
map<string, int> mp;
map常用函数及示例：
map中不存在键相同的元素, multimap中允许多个元素拥有同一键。multimap的使用方法与map的使用方法基本相同。
unordered_map的元素没有顺序,而map的元素按照键的大小进行排序。
map和set注意点：
map与set可以使用count判断元素是否存在，但要注意multiset的count()复杂度是0(元素个数)
访问.begin时需要判断是否等于.end,或者说要判断容器是否为空,这个要注意。
multiset erase(x)会把multiset里所有等于x的元素都删除: s.erase(x)
如果只想删除一个x,需要先找到等于x的元素的迭代器,然后删除迭代器:
s.erase(s.find(x));
在利用下标访问map中的某个元素时,如果map中不存在相应键的元素,会自动在map中插入一个新元素,并将其值设置为默认值
