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容器

基本概念

查找时间复杂度O(n),插入和删除时间复杂度O(n)。
插入和删除效率比vector高。

list是一个双向链表容器。不支持.at()和[]操作符。

#include <list>

list的构造

//默认的无参构造
list<int> lst;

//有参构造
list(n,elem);//构造函数将n个elem拷贝给本身
list(beg,end);//构造函数将[beg,end)的元素拷贝给本身
list(const list &lst);拷贝构造函数

list的查询

list.front();//返回第一个元素，可赋值
list.back();//返回最后一个元素，可赋值

比如：
list.front() = 20;

list的添加删除操作

list.push_back(elem);//尾部插入元素
list.push_front(elem);//头部插入元素
list.pop_back(elem);//尾部删除元素
list.pop_front(elem);//头部删除元素

list的插入

list.insert(pos,elem);//在pos位置插入elem的拷贝，返回新数据的位置
list.insert(pos,n,elem);//在pos位置插入n个elem的拷贝，无返回
list.insert(pos,beg,end);//在pos位置[beg,end)的数据，无返回

list的删除

list.clear();//移除所有元素
list.erase(beg,end);//删除[beg,end)的数据，返回下一个数据的位置
list.erase(pos);//删除pos位置的元素，返回下一个数据的位置
list.remove(elem);//删除容器中所有与elem匹配的元素

list的赋值

//assign是覆盖式，不是追加
list.assign(beg,end);//将[beg,end)区间中的数据拷贝赋值给本身
list.assign(n,elem);//将n个elem拷贝赋值给本身
list& operator=(const list &lst);//重载等号操作符
list.swap(lst);//将lst与本身的元素互换

list的大小

list.size();//返回容器元素个数
list.empty();//判断容器是否为空
list.resize(num);//重新指定容器长度为num，不够填充0，多余删除
list.resize(num,elem);//重新指定容器长度为num，不够填充elem，多余删除

list的反序排列

list.reverse();//反转链表

stack容器

stack是不可遍历的，没有迭代器

stack容器的构造

// 默认构造
stack<int> stk;

//带参构造
stack(const stack &stk);//拷贝构造函数
stack& operator=(const stack &stk);重载等号操作符

stack容器的出栈和入栈

stack.push(elem);//栈顶入栈
stack.pop();//栈顶出栈，无返回值
stack.top();//查看栈顶元素

stack容器的大小

stack.size();
stack.empty();

queue容器

queue是不可遍历的，没有迭代器

queue容器的构造

//默认无参构造
queue<int> que;
//有参构造
queue(const queue &que);//拷贝构造函数
queue& operator=(const queue &que);//重载等号操作符

queue容器的出队和入队

queue<int> que;

que.push(elem);//队尾入队
que.pop();//队头出队

queue容器的其他操作

queue.front();//查看队列第一个元素，可作为左值
queue.back();//查看队列最后一个元素，可作为左值

queue.size();
queue.empty();

set和multiset容器

基本概念

• 集合中的元素是唯一的，按一定的顺序(默认升序)排列，不能指定插入位置。

• set采用红黑树变体的数据结构实现，红黑树实现平衡二叉树。在插入操作和删除操作上比vector快

• set不可以直接存取元素。

• set支持唯一键值，multiset中同一值可以出现多次。

• 不可以直接修改集合中的元素值，因为该容器是自动排序的，必须先删除原有的元素，再插入新的元素。

set的构造

//默认无参构造
set<int> setInt;
multiset<int> multisetInt;

//有参构造
set(const set &st);//拷贝构造函数
set& operator=(const set &st);//重载赋值运算符
set.swap(st);//交换两个集合容器

set的插入

set.insert(elem);容器插入一个元素

set的删除

set.clear();
set.erase(pos);//不支持使用反向迭代器对元素进行删除
set.erase(beg,end);
set.erase(elem);

set的大小

set.size();//返回容器元素个数
set.empty();//判断容器是否为空

set的排序方式

set<int, less<int>> setIntA;该容器是按升序方式排列元素 -> 相当于set<int>

set<int, greater<int>> setIntB;该容器是按降序方式排列元素


less<int>和greater<int>

函数对象（伪函数）

//重载()操作符

//greater和less就是两个函数对象：

class greater{
	bool operator()(const int& iLeft, const int& iRight)
	{
		return (iLeft > iRight);
	}
}
//利用函数对象制定了容器对元素的排序规则。

//可通过自定义函数对象实现对应的功能：
class myfunctor{
	bool operator()(const int& iLeft, const int& iRight)
	{
		return (iLeft > iRight);
	}
}
set<int, myfunctor> s;

set的查找

set.find(elem);//查找elem元素，返回指向elem元素的迭代器，找不到返回end()迭代器
set.count(elem);//返回容器中值为elem的元素个数
set.lower_bound(elem);//返回第一个>=elem元素的迭代器
set.upper_bound(elem);//返回第一个>elem元素的迭代器

set.equal_range(elem);//返回容器中与elem相等的上下限的两个迭代器，范围是[上,下)，并且被封装在pair中。
//上返回的就是set.lower_bound(elem)，下返回的就是set.upper_bound(elem)
//根据编译器的不同，找不到返回end()或者指向最后一个元素的迭代器

pair对组

pair<T1, T2>//T1和T2可以是两种不同的数据类型，pair.first是第一个值，pair.second是第二个值

pair<set<int>>::iterator, set<int>>::iterator> pairIt = setInt.equal_range(5);

map和multimap容器

基本概念

哈希表

map的构造

//默认构造，T1是Key,T2是Value，T1和T2可以是不同类型，
map<T1, T2> mapTT;
multimap<T1, T2> multimapTT;

map的插入

map.insert(pair<int,string>(key,value));插入元素，返回pair
map.insert(map<int, string>::value_type(key,value));//通过value_type方式
mapstu[key] = value;//需要实现[]的重载

迭代器

基本概念

迭代器是一种检查容器内元素并且遍历容器内元素的数据类型。

常用于提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。

统一了对所有容器的访问方式，提高编程效率。

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迭代器失效

//插入元素失效
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函数返回的新迭代器

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

list的双向迭代器

list.begin();//返回容器中第一个元素的正向迭代器
list.end();//返回容器中最后一个元素之后的正向迭代器

list.rbegin();//返回容器中倒数第一个元素的反向迭代器
list.rend();//返回容器中倒数最后一个元素之后的反向迭代器


list<int>::reverse_iterator it1;
it1 = lst.rbegin();

注意，list的迭代器只能++或--，不支持其他的运算符。

list迭代器失效

//删除结点导致迭代器失效

list<int> lst1(3,5);//5 5 5
list.push_back(1);//5 5 5 1
for(it1 = lst1.begin();it1!= lst1.end();it++)
{
	if(*it == 1)
		lst1.erase(it);
}

//删除结点时，导致结点的指针域也被删除（清空），迭代器变成野指针
//所以无法继续访问下一个结点，会异常退出


改进之后：
for(it1 = lst1.begin();it1!= lst1.end();)
{
	if(*it == 1)
		it = lst1.erase(it);
	else
		it++;
}

set的双向迭代器

set.begin();//返回容器中第一个元素的正向迭代器
set.end();//返回容器中最后一个元素之后的正向迭代器

set.rbegin();//返回容器中倒数第一个元素的反向迭代器
set.rend();//返回容器中倒数最后一个元素之后的反向迭代器

算法