STL的一个重要特点是数据结构和算法的分离
尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组
STL另一个重要特性是它不是面向对象的
为了具有足够通用性，STL主要依赖于模板而不是封装，继承和多态（虚函数）——OOP的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效
（重要知识点（10种）：
序列式容器：（3种）vector、deque、list
关联式容器：（4种）set、multiset、map、multimap
顺序容器适配器：（3种）queue、priority_queue、stack）
STL中六大组件：
容器，迭代器，算法，仿函数，适配器，分配器
容器
STL中的容器有序列式容器，关联式容器，容器适配器，位集和串包等
容器类自动申请和释放内存，无需new和delete操作
（1）序列式容器：每个元素都有固定位置——取决于插入时机和地点，和元素值无关，vector、deque、list
vector（单向动态数组）：将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时；
deque（双向动态数组）：是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时；
list（双向链表）：不提供随机存取（按顺序走到需存取的元素），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针；
（2）关联式容器：元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap
set/multiset：set内的相同数值的元素只能出现一次，multisets内可包含多个数值相同的元素，内部的元素依据其值自动排序，由二叉树实现，便于查找；
map/multimap：map的元素是成对的键值/实值，map内的相同数值的元素只能出现一次，multimaps内可包含多个数值相同的元素，内部的元素依据其值自动排序，由二叉树实现，便于查找；
迭代器
Iterator（迭代器）：用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素
迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator
算法
算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。
<algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。
<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
<functional>中则定义了一些模板类，用以声明函数对象。
STL中算法大致分为四类：
非可变序列算法：指不直接修改其所操作的容器内容的算法。
可变序列算法：指可以修改它们所操作的容器内容的算法。
排序算法：对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
数值算法：对容器内容进行数值计算。
适配器
标准库提供了三种顺序容器适配器：queue(FIFO队列)、priority_queue(优先级队列)、stack(栈)
要使用适配器，需要加入一下头文件：
#include <stack> //stack
#include <queue> //queue、priority_queue
queue
默认顺序容器：deque
可用顺序容器：list、deque
说明:FIFO队列，基础容器必须提供push_front()运算
priority_queue
默认顺序容器：vector
可用顺序容器：vector、deque
说明:优先级队列，基础容器必须提供随机访问功能
stack
默认顺序容器：deque
可用顺序容器：vector、list、deque
说明:栈
定义适配器
1、初始化：stack<int> stk(dep);
2、覆盖默认容器类型：stack<int,vector<int> > stk;
范例函数
queue/priority_queue范例函数：
queue<int> q;
priority_queue<int> q;
两者通用函数：
q.empty(); //判断队列是否为空
q.size(); //返回队列长度
q.push(item); //对于queue，在队尾压入一个新元素；对于priority_queue，在基于优先级的适当位置插入新元素
queue only：
q.front(); //返回队首元素的值，但不删除该元素
q.back(); //返回队尾元素的值，但不删除该元素
priority_queue only：
q.top(); //返回具有最高优先级的元素值，但不删除该元素
stack范例函数：
stack<int> s;
stack< int, vector<int> > s2; //覆盖基础容器类型，使用vector实现stk
s.empty(); //判断stack是否为空，为空返回true，否则返回false
s.size(); //返回stack中元素的个数
s.pop(); //删除栈顶元素，但不返回其值
s.top(); //返回栈顶元素的值，但不删除此元素
s.push(item); //在栈顶压入新元素item
常用容器用法
序列式容器：vector、deque、list：每个元素都有固定位置——取决于插入时机和地点，和元素值无关
关联式容器：set、multiset、map、multimap：元素位置取决于特定的排序准则，和插入顺序无关
vector（begin，end || pop和push只有back）
1、构造函数
vector<type> vec:声明一个元素类型为type的空vector
vector<type> vec(size):声明一个元素类型为type的vector,元素个数为size
vector<type> vec(size, value):声明一个元素类型为type的vector，元素个数为size,且值均为value
vector<type> obj(const vector&):复制构造函数
vector<type> obj(begin,end):复制[begin,end)区间数组的元素到vector中
2、增加函数
void push_back(const T& x):向量尾部增加一个元素X
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):
向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据
3、删除函数
iterator erase(iterator it):删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back():删除向量中最后一个元素
void clear():清空向量中所有元素
4、遍历函数
reference at(int pos):返回pos位置元素的引用
reference front():返回首元素的引用
reference back():返回尾元素的引用
iterator begin():返回向量头指针，指向第一个元素
iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin():反向迭代器，指向最后一个元素
reverse_iterator rend():反向迭代器，指向第一个元素之前的位置
5、判断函数
bool empty() const:判断向量是否为空，若为空，则向量中无元素
6、大小函数
int size() const:返回向量中元素的个数
int capacity() const:返回当前向量张红所能容纳的最大元素值
int max_size() const:返回最大可允许的vector元素数量值
7、其他函数
void swap(vector&):交换两个同类型向量的数据
void assign(int n,const T& x):设置向量中第n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素
补，待换位子
reverse(obj.begin(),obj.end()); 从头到尾进行反转
sort(obj.begin(),obj.end()); 从头到尾进行排序，第三个参数不写，默认升序
sort(obj.begin(),obj.end(),compare);写参数时可按下方格式创建bool值
bool compare(int a,int b)
{
return a< b; //升序排列，如果改为return a>b，则为降序
}
8、看着清楚
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.erase 删除指针指向的数据项
4.clear 清空当前的vector
5.empty 判断vector是否为空
6.at 得到编号位置的数据
7.begin 得到数组头的指针
8.end 得到数组的最后一个单元+1的指针
9.front 得到数组头的引用
10.back 得到数组的最后一个单元的引用
11.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
12.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
13.max_size 得到vector最大可以是多大
14.capacity 当前vector分配的大小
15.size 当前使用数据的大小
16.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
17.reserve 改变当前vecotr所分配空间的大小
18.swap 与另一个vector交换数据
访问方式
1、vector可以直接访问（类似于数组的[ ]还有at( )方式和指针方式）
2、借由迭代器进行间接访问
vector<int>::iterator it;//声明一个迭代器，来访问vector容器，作用：遍历或者指向vector容器的元素
for(it=vec.begin();it!=vec.end();it++)
{
cout<<*it<<" ";
}
deque（front，back || pop和push有front和back）
虽然deque也提供Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可同日而语。因此，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL的sort算法），再复制回deque。
1、构造函数
#include<deque> // 头文件
deque<type> deq; // 声明一个元素类型为type的双端队列deque
deque<type> deq(size); // 声明一个类型为type、含有size个默认值初始化元素的的双端队列deque
deque<type> deq(size, value); // 声明一个元素类型为type、含有size个 value元素的双端队列deque
deque<type> deq(mydeque); // 复制构造函数
deque<type> deq(first,last); // 复制[first,last)区间数组的元素到deque中
2、
deq[ ]：用来访问双向队列中单个的元素。
deq.front()：返回第一个元素的引用。
deq.back()：返回最后一个元素的引用。
deq.push_front(x)：把元素x插入到双向队列的头部。
deq.pop_front()：弹出双向队列的第一个元素。
deq.push_back(x)：把元素x插入到双向队列的尾部。
deq.pop_back()：弹出双向队列的最后一个元素。
3、deque的一些特点
1.支持随机访问，即支持[ ]以及at()，但是性能没有vector好。
2.可以在内部进行插入和删除操作，但性能不及list。
3.deque两端都能够快速插入和删除元素，而vector只能在尾端进行。
4.deque的元素存取和迭代器操作会稍微慢一些，因为deque的内部结构会多一个间接过程。
5.deque迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。
6.deque可以包含更多的元素，其max_size可能更大，因为不止使用一块内存。
7.deque不支持对容量和内存分配时机的控制。
8.在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector，因为其内部结构显示不需要复制所有元素。
9.deque的内存区块不再被使用时，会被释放，deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实际操作版本定义。
10.deque不提供容量操作：capacity()和reverse()，但是vector可以。
访问方式
1、deque同vector可以直接访问（类似于数组的[ ]还有at( )方式和指针方式）
2、借由迭代器进行间接访问
deque<int>::iterator it;//声明一个迭代器，来访问deque容器，作用：遍历或者指向deque容器的元素
deque<int>::iterator it;
for (it = deq.begin(); it != deq.end(); it++)
{
cout << *it << ' ';
}
list（）
list是stl实现的双向链表，与向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢。使用时需要添加头文件
1、构造函数
list<type> lst; // 声明一个元素类型为type的空list
list<type> lst(size); // 声明一个类型为type、含有size个默认值初始化元素的的list
list<type> lst(size, value); //声明一个元素类型为type、含有size个value元素的list
list<type> lst(mylist); // 复制构造函数
list<type> lst(begin,end); //复制[begin,end)区间数组的元素到deque中
2、常用函数
lst.assign() 给list赋值
lst.back() 返回最后一个元素
lst.begin() 返回指向第一个元素的迭代器
lst.clear() 删除所有元素
lst.empty() 如果list是空的则返回true
lst.end() 返回末尾的迭代器
lst.erase() 删除一个元素
lst.front() 返回第一个元素
lst.get_allocator() 返回list的配置器
lst.insert() 插入一个元素到list中
lst.max_size() 返回list能容纳的最大元素数量
lst.merge() 合并两个list
lst.pop_back() 删除最后一个元素
lst.pop_front() 删除第一个元素
lst.push_back() 在list的末尾添加一个元素
lst.push_front() 在list的头部添加一个元素
lst.rbegin() 返回指向第一个元素的逆向迭代器
lst.remove() 从list删除元素
lst.remove_if() 按指定条件删除元素
lst.rend() 指向list末尾的逆向迭代器
lst.resize() 改变list的大小
lst.reverse() 把list的元素倒转
lst.size() 返回list中的元素个数
lst.sort() 给list排序
lst.splice() 合并两个list
lst.swap() 交换两个list
lst.unique() 删除list中相邻重复的元素
lst.insert(++list1.begin(), 3, 9);在第一个元素后插入3个9
