/*
STL容器主要分为以下几部分
序列容器vector (向量容器) deque (两端队列容器) list (双向链表)
关联容器set (单集合) multiset (双集合) map (单映射表) multimap (多映射表) )。
容器适配器堆栈(堆栈)队列)优先级队列(优先级_队列)
*/
(一)矢量集装箱
1 .包含在头文件#include vector中
2 .功能模拟了动态数组
3 .实现底层
首先，打开一定大小的数组，随着元素的增加，如果空间不够，就会自动采用扩展机制
扩展规则
以原始空间大小的2倍打开新空间，将空间的要素转移到新空间中继续添加要素
每次放大都遵循原始空间大小的两倍大小
4 .常用函数接口vector常用接口vectorint vec；
由于载体的基础是数组，所以存储器是连续的，可以采用下标访问方式
由于对数组而言，尾插和尾删的时间复杂度为o(1)，因此vector提供push_back )、pop_back ) )
vec.begin (其中：是vec的第一个元素vec.end ) :通过指向vec中最后一个元素的以下位置的两个函数来确定vec元素的范围
vec.size(:表示vec中的实际元件的数量的vec.capacity ) :返回vec实际上可容纳的元件的大小
VEC.max_size(:表示返回向量的最大容量
5 .向量初始化方式
vectorint vec1； //默认方式初始化基础没有分配内存空间
vectorintveC2(10； //指定第一个容量为10，默认值为0
vectorintvec3(10，20 )； //将开始的容量10和各单元的默认值指定为20
vectorintveC4(veC3 )； 调用//复制构造函数，用同类型的已存在对象创建同类型的新对象
intarray [ 10 ]={ 1，2，34，5，6，7，8，9，10 }；
vectorintveC5(Array，array 10 )； //使用数组区间数组实现向量的初始化
6 .向量元素遍历方法
使用迭代器遍历向量
常见的迭代器包括：转发迭代器反向迭代器reserve_iterator
常数序迭代器const_iterator常数逆迭代器const_reserve_iterator
插入线迭代器
前插式迭代器
后插入型迭代器
插入型迭代器
流迭代器
输入流迭代器
输出流迭代器
vector int :3360 iterator it=vec.begin (；
for (； it！=vec.end (； it )
{
cout*it '；
}
coutendl；
7 .在向量中插入元素
push_back (；
插入(vec.begin )、val )； //插件
插入(vec.end )、val )； //尾插
7 .通过向量删除元素
删除指定的元素
删除重复的元素只保留一个
8 .用向量动态创建二维数组
templatetypenamecontainervoidshow (container con ) container 33603360 iterator it=con.begin )； for (； it！=con.end (； it}{cout*it '； }coutendl； } templatetypenamecontainerbooldel _ container1(container con，int val ) if(con.empty ) {return false； } container :3360 iterator it=con.begin (； for(it； it！=con.end (； (if ) it==val ) it=con.erase ) it； (else ) it； } }返回真； } templatetypenamecontainerbooldel _ container2(container con，int val ) {Container:iter
ator it = con.begin();int count = 0 ;sort(con.begin(),con.end());for( it ; it != con.end();++it){if(*it == val){break;}}//排序后，用pos标记要删的数字的第一个位置；Container:: iterator pos = it;//从标记位开始找要删数字的个数for(it = pos ; it != con.end();++it){if(*it == val){count++;}}//it指向要删数字区间的最后一个；it = pos+3;//留出一个数字 删除后面的区间内的所有元素con.erase(pos+1,it);return true ;}template <typename Container>bool Del_Container3(Container &con,int val){if(con.empty())return false;sort(con.begin(),con.end());Container::iterator it = unique(con.begin(),con.end());//unique(begin.end),表示一定区间，通过相邻比较删除重复的元素，但是不会真正的删除，而是会放到尾地址后面//unique函数会将重复出现的数字放在容器的末尾并返回第一个重复的数字的迭代器 //再用erase函数擦除从指向的元素到最后的元素con.erase(it,con.end());return true;}int main(){int row;cin>>row;int col;cin>>col;vector<vector<int>> array(row);for(int i = 0 ; i < row ; ++i){array[i].resize(col);}for(int i = 0 ; i < row ;++i){for(int j = 0 ; j < col ;++j){cin>>array[i][j];}}int arr[] = {1,2,3,4,2,6,2,2,2,3,3,3,3,7,8,2};int len = sizeof(arr)/sizeof(arr[0]);vector<int> vec(arr,arr+len);cout<<"删除前vector中的元素"<<" "; Show(vec);Del_Container1(vec,2);cout<<"删除后vector中的元素"<<" ";Show(vec);return 0;}（二）deque双端队列
1.包含在头文件#include <deque>
2.底层实现
底层是一个二维数组 刚开始只开辟了两个格子的一维数组，每个一维数组里的指针指向一个二维数组的格子
每个指针指向的格子的大小由创建的双端队列所存放的数据类型有关
tempalate <typename T>
QUEUE_SIZE = 4096/T
3.扩容规则
扩容方式如上图所示
从deque的内存布局来看 它是整体不连续 局部连续
优点:随机访问方便 支持[]操作符和at操作
在内部可以进行头插 头删 尾插 尾删 时间复杂度都为O(1)
缺点:内存占用量大
4.初始化方式
deque<int> dq1;//创建一个空的队列
deque<int> dq2(10);//创建一个含有10个数据的队列 数据被默认初始构造
deque<int> dq3(10,5);//创建有一个含有10个数据并且都初始化为5的队列
deque<int> dq4(begin.end);//创建一个以(begin,end)区间的队列
deque<int> dq5(dq4);//复制一个队列
5.常用函数接口
dq.begin():表示迭代器指向的第一个元素 dq.end():表示迭代器指向尾元素的后一个位置
dq.at(index):传回index对应的元素 如果index越界 抛出out_of_range
dq.back():传回最后一个元素 不检查这个数据是否存在
dq.front():传回第一个元素
dq.assgin(begin.end):将(begin.end)区间中的数据赋值c
dq.assign(n.val):将n个val的拷贝值给dq
dq.empty():判空
dq.erase(pos):删除os位置 传回pos的下一个位置
d1.erase(begin,end):删除(begin,end)区间的值
dq.resize(num):重新指定队列的长度
dq.size():返回容器中的实际数据个数
dq1.swap(dq2):将dq1和dq2元素互换
6.元素遍历方式
7.插入元素
8.删除元素
dq.erase(pos):删除os位置 传回pos的下一个位置
d1.erase(begin,end):删除(begin,end)区间的值
dq1.pop_back():尾删
dq1.pop_front():头删
9.迭代器失效问题
1.在deque容器首部或者尾部插入元素不会使得任何迭代器失效
2.在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效
3.在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效
4.在扩容阶段也会使所有迭代器失效
template <typename Container>void Show(Container &con){Container::iterator it = con.begin();for(; it != con.end();++it){cout<<*it<<" ";}cout<<endl;}template <typename Container>bool Del_Container1(Container &con,int val){if(con.empty()){return false ;}Container::iterator it = con.begin();for( it ; it != con.end();){if(*it == val){ it = con.erase(it);}else{++it;}}return true;}int main(){deque<int> dq1(10,5);deque<int>::iterator it = dq1.begin();for(; it != dq1.end();++it)cout<<*it<<" ";cout<<endl;int arr[] = {1,2,3,4,5,6,7,8,1,2,1,2,2,2};int len = sizeof(arr)/sizeof(arr[0]);deque<int> dq2(arr,arr+len);Show(dq2);dq2.pop_back();Show(dq2);return 0;}
（三）list双向链表
底层是一个环状的循环链表 由于其链表节点具有pre和next域 所以list也支持push_back、push_front、pop_back、pop_front
根据链表的插入与删除 插入时需要配置一个节点空间 删除时需要删除对应元素的节点空间
它的扩容机制不受影响 每次插入节点 只需要先开辟节点空间 在放置元素
它的底层不是连续的 所以不能通过[]随机访问元素 但是可以双向遍历
增加元素都不会使迭代器失效
删除元素时 只是指向当前被删元素的迭代器失效 不影响其他迭代器