目录
STL容器和算法
基本概念
标准模板库，主要分为容器、算法、迭代器。
通过迭代器访问容器中的数据，并进行算法操作。
所有代码采用模板类和模板函数的方式。
容器
容器的分类
序列式容器
每个元素都有固定位置，该位置取决于插入时机和地点，和元素值无关。
vector,deque,list,stack,queue
关联式容器
元素位置取决于特定的排序准则，和插入顺序无关。
set multiset map multimap
vector容器
连续存储的动态数组，类似于数组，不过是动态的，可以添加移除元素。
尾部添加移除元素方便，但是中部或头部比较麻烦，复杂度为O(n)。
vector的定义
//无参构造
vector<int> int1darray;
vector<vector<int>> int2darray;
//带参数构造
vector(start, end);//左闭右开[start,end)
vector(n, elem);//拷贝n个elem
vector(const vector &vec);//拷贝构造函数
比如：
int arr[5] = {0};
vector<int> int1darray1(arr,arr+5);//拷贝arr
vector<int> int1darray2(3, 10);//存储3个10
vector<int> int1darray3(int1darray1);//拷贝int1darray1
vector的赋值
vector.assign(beg,end);//将[beg,end)区间的数据拷贝给本身
vector.assign(n,elem);//将n个elem拷贝赋值给本身
vector &operator=(consr vector &vec);//重载等号操作符
vector.swap(vec);将vec与本身元素交换
比如：
vector<int> v1,v2,v3,v4;
int array[] = {1,2,3,4,5};
v1.assign(array,array+5);
v2.assign(3,10);
v3 = v2;
v4.swap(v3);
vector的大小
vector.size();//容器元素的个数
vector.empty();//判断容器是否为空
vector.resize(num);//重新指定容器长度为num，多余删除，不够添加默认值
vector.resize(num,elem);//重新指定容器长度为num，多余删除，不够添加elem
比如：
vector<int> v1(3,10);
v1.size();//3
v1.empty();//False
v1.resize(5);//10,10,10,0,0
v1.resize(5,3);//10,10,10,3,3
vector的访问方式
[]下标法和.at(idx)
但是[]下标法的下标有时候会越界，导致程序异常终止，但不会抛出异常信息，和数组同理。
采用.at(idx)，如果出现越界情况，抛出异常信息out_of_range。
vector的元素操作
//在末尾插入移除元素
vector.push_back(elem);//末尾插入
vector.pop_back(elem);//末尾删除
// 可在任意位置插入删除，但是复杂度不同
注意pos必须是指针(v1.begin())
vector.insert(pos,elem);//在pos位置插入一个elem的拷贝，返回新数据的位置
vector.insert(pos,n,elem);//在pos位置插入n个elem的拷贝，无返回
vector.insert(pos,beg,end);//在pos位置插入[beg,end)的数据，无返回
比如：
vector<int> v1(3,10);//10,10,10
v1.insert(v1.begin()+2,3);//10,10,3,10 返回2
v1.insert(v1.begin()+2,2,4);//10,10,4,4,3,10
int array[] = {1,2,3};
v1.insert(v1.beign()+2,array,array+3);//10,10,1,2,3,4,4,3,10
deque容器
double-ended queue。
deque是双端数组，而vector是单端数组。deque的许多操作和vector相似。
单端：长度可以沿着一个方向变化 O(n)
双端：长度可以沿着两个方向变化
deque头部和尾部添加移除元素很快，但是中部比较麻烦。
#include <deque>
deque.push_front(elem);//头部添加
deque.pop_front();//头部删除
deque<int> d1 = {1,2,3,4};
d1.push_front(5);//5,1,2,3,4
d1.pop_front();//1,2,3,4
list容器
基本概念
迭代器
基本概念
迭代器是一种检查容器内元素并且遍历容器内元素的数据类型。
常用于提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。
统一了对所有容器的访问方式，提高编程效率。
vector的迭代器
//定义vector迭代器对象
vector<int>::iterator iter;
vector<int> v1(3,10);
v1.begin();//返回指向容器的第一个元素的正向迭代器
v1.end();//返回指向容器最后元素的下一个位置的正向迭代器
//迭代器指向第一个元素
vector<int> v1(3,10);
iter = v1.begin();
//使用迭代器遍历容器
for(iter = v1.begin();iter != v1.end();iter++)
cout<< *it << " ";
注意：iter++可以实现的原因是迭代器本身实现了++运算符的重载，* 同理。
迭代器失效
//插入元素失效
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int>::iterator it = v.begin() + 3;
v.insert(it, 8);
cout<<*it<<endl;//输出0或4
/*
编译器在插入元素时，会新new一个内存空间再把原来的容器拷贝过去。
那么针对之前的空间，不同编译器处理的方式也不同，有些是保持不动，有些覆盖为0。
而it迭代器依然指向原来的内存空间，所以输出有可能是4或0。这就是迭代器失效（变成了野指针）。
解决办法；
insert函数会返回新的迭代器或采用深拷贝。
*/
//删除元素失效
vector<int> v1 = {1,2,3,3,3,4};
vector<int>::iterator it;
for(it = v1.begin();it != v1.end();it++)
{
if(*it == 3)
v1.erase(it);
}
for(it = v1.begin();it != v1.end();it++)
{
cout<< *it << " ";//输出1,2,3,4
}
/*
删除是覆盖的操作，并且删除之后it会向前移动，导致遗漏。
*/
修改之后；
for(it = v1.begin();it != v1.end();)
{
if(*it == 3)
v1.erase(it);
else
it++；
}
或者使用erase函数返回的新迭代器
总结：在使用迭代器进行插入或删除的操作时，需要对迭代器重新赋值以保证迭代器一直有效。