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函数返回的新迭代器

总结：在使用迭代器进行插入或删除的操作时，需要对迭代器重新赋值以保证迭代器一直有效。