C++深入学习之STL：1、容器部分

标准模板库STL的组成

主要由六大基本组件组成：容器、迭代器、算法、适配器、函数对象(仿函数)以及空间配置器。

容器：就是用来存数据的，也称为数据结构。
本文要详述的是容器主要如下：

序列式容器：vector、list
关联式容器：set、map
无序关联式容器：unordered_set、unordered_map

迭代器：行为类似于指针，具有指针的功能，我们使用迭代器来连接容器与算法。

算法：就是用来操作数据的。

适配器：因为STL中的算法的实现不是针对于具体容器的，所以可能有些算法并不适合用于具体的容器，需要使用适配器进行适配（或者转接）。

包含容器的适配器、迭代器的适配器、算法的适配器。

函数对象(仿函数)：函数对象就是通过重载小括号运算符对象的，在STL中用来做定制化操作的。

空间配置器：用来进行空间的申请与释放的。

容器

序列式容器

序列式容器总共有下面五种：

这里只讲vector、deque与list。

原因很简单，array是静态数组，forward_list是单向链表，而vector是动态数组、list是双向(循环)链表，谁又还会去用静态数组和单向链表呢？而deque是双端队列，是比较常用的数据结构，所以自然也是需要学习的。

序列式容器的模板参数类型

template<
class T,
class Allocator = std::allocator<T>
> class vector;

template<
class T,
class Allocator = std::allocator<T>
> class deque;

template<
class T,
class Allocator = std::allocator<T>
> class list;

可以看见第一个参数T是我们所要存放入模板的参数，Allocator是空间配置器，其具有一个默认参数为std::allocator<T>，因此我们使用序列式容器的时候不需要传入空间配置器而只需要传入我们要存放的数据。

序列式容器常用的初始化与遍历方式示例

#include <cstddef>
#include <iostream>
#include <list>
#include <vector>
#include <deque>

using namespace std;

void test(){
	//序列式容器的初始化与遍历操作都基本一样，主要有下面几种形式
	//以vector为例，deque操作与vector是一样的，就不再赘述
	//list与vector只有一处不同，就是list无法使用下标进行遍历，这一点要格外注意
	
	//常用的初始化方法
	//1、无参初始化
	vector<int> number;
	//2、指定容器大小初始化
	//2.1、指定初始化的内容
	//第一个参数表示容器要初始化的大小，第二个参数表示要初始化的值
	//即下面的number是初始化了 10 个 4，即传count个value
	vector<int> number(10,4);
	//2.2、不指定初始化的内容，则容器默认内容存储为0
	//即下面的number是初始化了10个0元素
	vector<int> number(10);
	//3、使用迭代器范围进行初始化(范围是左闭右开)
	int arr[10] = {1,2,4,3,6,3,8,9,10,5};
	vector<int> number(arr,arr+10);
	//4、使用初始化列表的形式进行初始化
	vector<int> number = {1,2,3,4,5,6,7,8,9,10};
	
	//常用的遍历方法
	//1、使用for循环
	for(size_t idx=0;idx!=number.size();++idx){
		cout << number[idx] << " ";
	}
	cout << endl;
	//2、使用迭代器
	vector<int>::iterator it;
	for(it=number.begin();it!=number.end();++it){
		cout << *it << " ";
	}
	cout << endl;
	//3、使用加强的for循环
	for(auto& elem : number){
		cout << elem << " ";
	}
	cout << endl;
}

int main(){
	test();
	return 0;
}

对于上面代码中的迭代器遍历方式，下面有个图示可能看了会有助于理解begin()与end()的工作机制：

这是一个比较简单和基本的概念，begin和end其实就是两个指针，begin指向容器的首部，而end指向容器尾部的下一个为空的元素，而迭代器iterator也是一个指针，因此可以通过这三个指针的组合来完成容器遍历，就和学习链表时遍历链表的操作一样，只不过STL这里进行了封装而已，不再赘述。

另外注意：list无法使用下标访问元素，切记。

序列式容器常用的头尾位置插入与删除方式示例

#include <iostream>
#include <vector>
#include <deque>
#include <list>

using namespace std;

//模板打印函数
template <typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem << " ";
	}
	cout << endl;
}

//从尾部插入与删除，三者是一样的
void test(){
	//序列式容器从尾部插入与删除操作是一样的，主要有下面两个方式
	//push_back()和pop_back()
	//这里依然只以vector为例，deque与list和vector是一样的，就不再赘述
	vector<int> number = {1,3,5,7,9,10};
	display(number);

	//在vector尾部进行插入
	number.push_back(100);
	number.push_back(200);
	display(number);
	
	//在vector尾部进行删除
	number.pop_back();
	display(number);

}

//从头部插入和删除，只有list和deque是一样的，vector没有这种方式
//为什么呢？
//因为插入与删除第一个元素的这种操作对于vector而言，其都会进行一个
//将后面的元素进行挪动的操作(跟数组一样)，时间复杂度过高(o(N))，所以不予实现
void test1(){
	//因为list和deque的方式一样，这里依然是只以list为例
	//两个方法: push_front()和pop_front()
	list<int> number = {1,2,3,4,5};
	//从头部插入
	number.push_front(20);
	number.push_front(50);
	display(number);

	//从头部删除
	number.pop_front();
	display(number);
}

int main(){
	test();
	return 0;
}

对于插入删除操作只需要注意vector的特殊性：vector不提供头部删除与插入的操作，原因是复杂度过高。

序列式容器常用的中间位置插入与删除方式示例

#include <iostream>
#include <list>
#include <vector>

using namespace std;

template<typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem << " ";
	}
	cout << endl;
}

//对于中间位置插入，三个序列式容器都是可以做到的
//但是注意时间复杂度的问题，list毫无疑问是最快的，因为是双向链表
//这里只以list为例进行示例，insert方法三个序列式容器都是一样的操作
void test(){
	//list的中间插入操作示例
	//常用方法如下
	list<int> number = {1,2,34,3,8,56,89};
	auto cit = number.begin();
	++cit;
	++cit;
	//1、指定位置进行插入
	number.insert(cit,300);
	display(number);

	//2、指定位置插入count个value元素
	//下面这句代码的意思是在cit的位置出开始插入3个值为200的元素
	number.insert(cit,3,200);
	display(number);

	//3、指定位置按其它容器的迭代器范围进行元素插入
	vector<int> num = {2,3,4,5};
	number.insert(cit,num.begin(),num.end());
	display(number);
	
	//删除操作
	//使用erase()函数，传入参数为迭代器
	for(auto it = number.begin(); it!=number.end();++it){
		if(2 == *it){
			//erase函数要注意迭代器失效的问题嗷
			//具体参见本文下文：迭代器失效问题
			it = number.erase(it);
		}
	}
	display(number);
} 

int main(){
	test();
	return 0;
}

序列式容器常用的一些其它操作

注意这里只是提了一些比较常见的操作，还有更多的操作随用随查即可嗷。

#include <iostream>
#include <list>
#include <vector>

using namespace std;

template<typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem << " ";
	}
	cout << endl;
}

//这里要注意，对于deque而言其没有capacity()函数
//但其具有shrink_to_fit函数
//对于list来说，其没有capacity()函数也没有shrink_to_fit()函数
void test(){
	//容器元素的清空
	vector<int> number = {1,2,34,3,8,56,89};
	cout << "number.size = " << number.size() << endl;
	cout << "number.capacity = " << number.capacity() << endl;
	display(number);
	//使用clear函数可以清空元素，但要注意其容量不会被重置
	//清除前是多大清除后依然是多大
	number.clear();
	cout << "number.size = " << number.size() << endl;
	cout << "number.capacity = " << number.capacity() << endl;
	display(number);
	//如果想要将容量也一并清除
	//即缩减掉所有未使用的内存的话，可以使用shrink_to_fit()函数
	number.shrink_to_fit();
	cout << "number.size = " << number.size() << endl;
	cout << "number.capacity = " << number.capacity() << endl;
	display(number);
} 

int main(){
	test();
	return 0;
}

vector底层原理

通过阅读vector的底层源码，我们不难发现vector的继承体系如下：

vector保护继承自_Vector_base，_Vector_base公有继承自_Vector_alloc_base，在最上层的基类_Vector_alloc_base中有三个指针类型的数据成员：_Tp* _M_start，_Tp* _M_finish和_Tp* _M_end_of_storage;

三个指针的作用图示如下：

还是比较好理解的吧，_M_start指向头部，_M_finish指向实际存储元素的下一个空元素，而_M_end_of_storage则是控制整个vector容量的指针，永远指向vector容量最大位置的末端地址。

我们所使用的vector的各种函数其实都是由这三个指针实现的，如：

经典面试题: vector中的at函数与下标访问运算符函数有什么区别？

这里有一个经典的面试题，在vector提供的函数中有下面两个作用相同的函数：

也就是at函数和operator[]函数，二者的作用都是随机获取vector中的值，那么二者的区别是什么呢？

通过上面两幅图的源码显示我们可以看到，at函数在返回结果之前先调用了一个_M_range_check(__n)的函数，我们来看一下该函数的源码：

不难发现其做了一个越界检查，如果超出了vector的最大长度则会抛出异常。
因此二者的区别是：at函数可以进行范围的检查，比operator[]函数更加安全。

vector的push_back函数探究

源码如上，可以看见其逻辑还是比较简单的，如果vector没满那么就往里面存内容，如果满了的话就进行扩容即可，扩容操作在_M_insert_aux()函数中：

上面只是源码的一部分，从划红线位置可以看出，vector底层扩容时确实是按照两倍的标准进行的。

迭代器失效问题的典型：vector迭代器失效

由前文可知，vector在遇到空间大小不够时会自动进行扩容操作，其步骤就算不看源码我们也能猜出一二，大致如下：

1、检查容量：当向 std::vector 添加元素时，它首先检查当前容量是否足够。如果当前容量不足以容纳新元素，则进行下一步。
2、计算新容量：std::vector 不会仅仅为了添加一个新元素而重新分配内存。相反，它会预估在未来添加更多元素时需要的容量。3、默认情况下，每次扩容时，新容量是旧容量的2倍（这个比例可以在创建 std::vector 时通过第二个参数进行定制）。
4、分配新内存：使用计算出的新容量，std::vector 会分配一块新的内存区域。
5、复制元素：std::vector 会将旧数组中的所有元素复制到新数组中。
6、添加新元素：在新数组的末尾添加新元素。
7、释放旧内存：旧数组的内存被释放。
8、更新 std::vector 的大小：std::vector 的大小（size 成员）增加一个，以反映新添加的元素。

同时我们知道vector容器的迭代器就是指针类型，那么vector在扩容时其内存地址发生该变是不是意味着原来的迭代器指针就会失效呢？

来看下面的代码示例;

运行结果如下：

不难看出因为我们是迭代器指针cit本来指向的是元素34，一开始vector的大小和容量都为7（因为初始化时总共七个元素），在32位置插入300之后，我们可以看到number的capacity容量值发生了扩容（并且清晰的是2倍扩容），此时就意味着vector容器的内存地址发生了改变，因为内存是被重新分配了的，那么原先旧版number容器的迭代器自然也就失效了，此时再使用该迭代器去继续迭代崭新的容器元素必然出现错误，这也就是为什么上述运行结果出现乱码且出现了core dumped的原因。

解决办法很简单，使用insert方法返回的新容器的迭代器即可：

运行结果如下：

此时不再发生迭代器失效问题，除了上述方法之外还可以对cit迭代器重新赋值也是可以的：

cit = number.begin();

同理，vector在删除元素时也会发生迭代器失效的情况，其原因是在我们删除如中间某一个元素的时候，vector底层实现不允许其中间具有空值(因为vector是连续存储的)，所以在缺少元素时vector会进行一个元素移动的操作，这同样会引发迭代器失效而出现意料之外的情况，解决办法相同，测试用例如下，程序目的为删除number容器中所有的 6 ：

运行结果如下：

上图中第一次运行为异常情况(即迭代器失效的情况)，第二次运行为解决了迭代器失效问题的运行结果，分析就不再赘述，自己画图分析一目了然。

另外除了vector容器需要考虑迭代器失效以外，其它序列式容器如list和deque一样需要考虑，在插入删除操作时迭代器失效的情况很常见，一种最佳实践是每次进行插入删除操作时都按时更新新的迭代器，从而避免迭代器失效的情况。

vector动态扩容的底层原理

对于insert函数插入元素时，其扩容方式为：设size() = t，capacity() = n，插入的元素个数为m，则有如下关系式：

1、m <= n - t，此时不需要扩容；
2、n - t < m < t ，此时是 2 * t 进行扩容操作；
3、n - t < m，t < m < n，此时是 t + m 进行扩容操作；
4、n - t < m，m > n，此时是 t + m 进行扩容操作。

因为push_back每次插入的元素的个数是一个，所以按照两倍的扩容方式是没有问题的。
而insert每次插入的元素个数是不确定的，所以扩容方式也是不固定的，因此insert扩容会麻烦一些。

deque底层原理

通过分析源码，我们可以得出deque的继承体系如下：

顶层基类_Deque_alloc_base有两个数据成员_M_map和_M_map_size；

deque的迭代器详解

派生类_Deque_base类有两个数据成员_M_start和_M_finish，也就是一个指向队头一个指向队尾，值得注意的点是这两个数据成员的类型为iterator迭代器，之前我们说过iterator都可以抽象的理解为指向容器存储位置的指针，但这并不意味着所有容器的迭代器的实现都是通过指针实现的，上文的vector的迭代器是指针实现的，而deque容器的迭代器则是一个类(_Deque_iterator<_Tp,_Tp&,_Tp*> iterator)被typedef后实现的，在该类内部实现了iterator的类指针操作。

_Deque_iterator类的源码实现（部分）如下：

可以看出该类内部实现了iterator的各个函数重载，如++运算符、->运算符等等，让deque的迭代器抽象成了一个类似指针的东西。

因此之前说迭代器是一种指针，这只是广义上的说法，我们并不能断定说容器的iterator就是一个指针，这样的说法是错误的。
比如deque容器的迭代器实现就是通过一个类typedef之后重定义而成的。

_M_map中控器

deque作为双端队列，直觉上给人的感觉似乎就是一个两端开口，存储连续的数据结构，如下：

但实际上其底层实现并非如此直观，deque使用了_M_map中控器的数据结构：

从上图可以看到，中控器的每个位置都指向了一小块内存片段，在每一小块内部数据是连续存放的，小块与小块之间是并不连续的。

所以千万注意：deque逻辑上是连续的，但实际物理存储上是分散的非连续的嗷！

这个中控器就是基类_Deque_alloc_base的主要内容，然后派生类_Deque_base公有继承自基类_Deque_alloc_base拿到这个中控器，其有两个数据成员_M_start和_M_finish来操作该中控器，对于这两个数据成员其类型都为迭代器类型，从前文可以知道，每个迭代器类型都具有四个指针：_M_cur、_M_first、_M_last、_M_node；

_M_start的原理分析：

_M_start会指向中控器的第一个内存片段，然后其内部的四个指针会做如下操作：

_M_first会指向该片段的第一个可以存放元素的位置（可能为空）；
_M_cur会指向该内存片段中的真正存储的第一个元素（也就是整个deque的第一个元素）；
_M_last会指向该片段的最后一个元素的下一个空元素的位置；
_M_node表示一个节点。

_M_finish的原理分析：

同理，_M_finish会指向中控器的最后一个内存片段，其余指针效果同前。

总结：

deque是由多个小内存片段组成的，每个小片段内部是连续的，但是片段与片段之间不是连续的，每个小片段靠中控器数组进行管理，当元素过多之后会重新申请新的片段，如果片段过多之后，可能会扩大中控器数组的大小。

list容器的一些特殊操作

#include <functional>
#include <iostream>
#include <list>
#include <vector>

using namespace std;

template<typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem << " ";
	}
	cout << endl;
}

//自定义的排序方式
struct Com{
	bool operator()(const int& lhs,const int& rhs) const{
		return lhs < rhs;
	}
};

void test(){
	//list的一些特殊操作，这些是vector和deque所不具有的
	list<int> number = {1,3,4,6,7,98,8,3,3,8};
	display(number);

	cout << "链表的逆置" << endl;
	number.reverse();
	display(number);

	cout << "链表的排序" << endl;
	//默认从小到大排序，可以传入比较参数来重新定义排序
	//number.sort();
	//number.sort(greater<>());//从大到小进行排序
	//也可以自定义,写成普通类或者模板类的形式都是可以的
	number.sort(Com());
	display(number);
	
	cout << "链表的去重,注意只是去重连续重复的值" << endl;
	number.unique();
	display(number);

	cout << "链表的合并" << endl;
	//如果两个链表本身是有序的，那么合并之后也依然会有序
	list<int> lst1 = {1,3,7,9,4};
	list<int> lst2 = {8,30,70,90,40};
	lst1.sort();
	lst2.sort();
	lst1.merge(lst2);
	display(lst1);
	display(lst2);//lst2为空，相当于将lst2的内容move到了lst1中
	
	cout << "链表的splice()的使用" << endl;
	list<int> lst3 = {1,4,7,9,3};
	list<int> lst4 = {5,8,10,20,2};
	auto cit = lst3.begin();
	cout<< "*cit = " << *cit << endl;
	//将整个lst4存进lst3中的cit位置
	//lst3.splice(cit,lst4); 此时lst4也为空了嗷，相当于move
	
	//将lst4中的it所指向的位置的元素存进lst3中的cit位置处
	//注意这个操作也可以自己对自己使用，如lst3.splice(cit,lst3,it);
	//效果相当于移动自己所存储的元素到其它位置
	auto it = lst4.end();
	--it;
	cout << "*it" << *it << endl;
	lst3.splice(cit,lst4,it);
	display(lst3);
	display(lst4);//lst4中的it所指向的值就没有了，但其它元素还在
	
} 

int main(){
	test();
	return 0;
}

关联式容器

set 与 multiset

首先第一点要注意的就是：set 和 multiset 都位于同一个头文件 <set>中！

set 的模板参数类型

template<
	class Key,
	class Compare = std::less<Key>,
	class Allocator = std::allocator<Key>
> class set;

可以看到有三个值，key值不用多说是我们要传入的数据，而Compare类型参数是我们用来定义排序的比较方式，默认是从小到大升序，若想从大到小可以使用 std::greater ，另外我们也可以自定义这个比较类然后传入即可。第三个值是空间配置器，这个在后面会进行详述。

set 的基本CRUD操作

#include <iostream>
#include <ostream>
#include <set>
#include <vector>

using namespace std;

//打印函数
template<typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem << " ";
	}
	cout << endl;
}

void test(){
	//set 的初始化
	//set的特点：
	//1、key值是唯一的，不能重复
	//2、默认情况下，会按照key值进行升序排列
	//3、底层使用的数据结构是红黑树
	set<int> number = {1,3,5,2,3,5,7,9,4,5};
	display(number);

	//set 的查找操作
	//常用的是count和find
	size_t cnt1 = number.count(3);
	size_t cnt2 = number.count(10);
	cout << "cnt1 = " << cnt1 << "  "
		<< "cnt2 = "<< cnt2  << endl;
	
	auto it = number.find(5);
	if(it != number.end()){
		cout << "*it = " << *it << endl;
	}
	else{
		cout << "查找失败" << endl;
	}
	
	//set的插入操作
	//auto it2 = number.insert(8); 使用auto可以简化我们的代码形式
	//但set 的insert 操作返回的是 一个 pair 类型的值
	pair<set<int>::iterator,bool> ret = number.insert(8);
	if(ret.second){
		cout << "该元素插入成功" << *ret.first << endl;
	}else{
		cout << "插入失败" << endl;
	}

	//插入迭代器范围的方式进行插入
	vector<int> vec = {10,3,6,20,50};
	number.insert(vec.begin(),vec.end());
	display(number);
	
	//插入大括号表达式进行插入也是可以的
	number.insert({1,0,100,200});
	display(number);
	
	//set 的删除
	number.erase(10);
	display(number);
	
	//set 的下标访问 
	//cout << "number[10]" << number[0] << endl; error,set不支持下标访问嗷

	//set的修改操作
	auto it3 = number.begin();
	cout << "*it3 = " << *it3 << endl;
	//*it3 = 200; error set是不支持修改的
}

class Comparation;

//自定义类型point
class Point{
	friend Comparation;
	public:
		Point(int ix = 0, int iy = 0)
		:_ix(ix)
		 ,_iy(iy)
		{
			cout << "Point()" << endl;
		}

		//重写小于运算符函数
		friend bool operator<(const Point& lhs,const Point& rhs);

		~Point(){
			cout << "~Point()" << endl;
		}

		friend ostream& operator<<(ostream& os,const Point& rhs);

	private:
		int _ix;
		int _iy;
};

ostream& operator<<(ostream& os,const Point& rhs){
	os << "(" << rhs._ix << "," << rhs._iy << ")" << endl;
	return os;
}

bool operator<(const Point& lhs,const Point& rhs){
	//定义小于比较的逻辑，随便定义，set会根据这个逻辑来进行排序
	if(lhs._ix < rhs._ix){
		return true;
	}else{
		return false;
	}
}

//比较器的类，重载函数调用运算符即可
struct Comparation{
	bool operator()(const Point& lhs,const Point& rhs){
		if(lhs._ix < rhs._ix){
			return true;
		}else{
			return false;
		}
	}
};

//set存储自定义类型的情况
void test2(){
	set<Point> number = {
		Point(1,2),
		Point(1,-2),
		Point(-1,-2),
		Point(4,5)
	};
	display(number);
	//此时进行打印会报错，因为set容器是会自动进行排序的
	//而我们的Point类里面并没有实现对应的比较函数
	//实现了之后输出才是正确的
	//另一种方式是手写一个比较类，然后在其内部重载函数调用运算符即可
	//然后把该类当成set模板参数列表的第二个比较器参数传入
	set<Point,Comparation> number2 = {
		Point(1,2),
		Point(1,-2),
		Point(-1,-2),
		Point(4,5)
	};
	display(number2);
}

int main(){
	test2();
	return 0;
}

对于set 的使用，要注意当存储的元素类型为自定义类型的情况。

重载大于符号或者小于符号，等价实现 std::less 或者 std::greater。

multiset 的CRUD操作

#include <iostream>
#include <ostream>
#include <set>
#include <vector>

using namespace std;

//打印函数
template<typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem << " ";
	}
	cout << endl;
}

void test(){
	//multiset 的初始化
	//multiset的特点：
	//1、key值是不唯一的，可以重复
	//2、默认情况下，会按照key值进行升序排列
	//3、底层使用的数据结构是红黑树
	multiset<int> number = {1,3,5,2,3,5,7,9,4,5};
	display(number);

	//multiset 的查找操作
	//常用的是count和find
	//count会计数传入参数在multiset容器中出现的次数
	size_t cnt1 = number.count(3);
	size_t cnt2 = number.count(10);
	cout << "cnt1 = " << cnt1 << "  "
		<< "cnt2 = "<< cnt2  << endl;
	
	auto it = number.find(5);
	if(it != number.end()){
		cout << "*it = " << *it << endl;
	}
	else{
		cout << "查找失败" << endl;
	}

	//测试multiset的xxx_bound()函数
	//lower_bound()会返回第一个大于等于所给定的key值的迭代器
	//upper_bound()会返回第一个大于所给定的key值的迭代器
	auto itt1 = number.lower_bound(5);
	cout << "*itt1 = " << *itt1 << endl;
	auto itt2 = number.upper_bound(5);
	cout << "*itt2 = " << *itt2 << endl;
	
	//测试multiset的euqal_range()函数
	//该函数返回的是pair类型的两个迭代器指针，用来表示一个范围
	//该范围内就全是所给定的key的值
	auto ret2 = number.equal_range(5);
	while(ret2.first != ret2.second){
		cout << *ret2.first << " ";
		++ret2.first;
	}
	cout << endl;
	
	//multiset的插入操作
	//auto it2 = number.insert(8); 使用auto可以简化我们的代码形式
	//但multiset 的insert 操作返回的是 一个 iterator 类型的值
	//使用multiset时只管插入即可，肯定是成功的，不需要考虑返回值，
	number.insert(8);
	display(number);
	
	//插入迭代器范围的方式进行插入
	vector<int> vec = {10,3,6,6,20,50};
	number.insert(vec.begin(),vec.end());
	display(number);
	
	//插入大括号表达式进行插入也是可以的
	number.insert({1,0,100,200});
	display(number);
	
	//multiset 的删除
	number.erase(10);
	display(number);
	
	//multiset 的下标访问 
	//cout << "number[10]" << number[0] << endl; error,multiset不支持下标访问嗷

	//multiset的修改操作
	auto it3 = number.begin();
	cout << "*it3 = " << *it3 << endl;
	//*it3 = 200; error multiset是不支持修改的
}

class Comparation;

//自定义类型point
class Point{
	friend Comparation;
	public:
		Point(int ix = 0, int iy = 0)
		:_ix(ix)
		 ,_iy(iy)
		{
			cout << "Point()" << endl;
		}

		//重写小于运算符函数
		friend bool operator<(const Point& lhs,const Point& rhs);

		~Point(){
			cout << "~Point()" << endl;
		}

		friend ostream& operator<<(ostream& os,const Point& rhs);

	private:
		int _ix;
		int _iy;
};

ostream& operator<<(ostream& os,const Point& rhs){
	os << "(" << rhs._ix << "," << rhs._iy << ")" << endl;
	return os;
}

bool operator<(const Point& lhs,const Point& rhs){
	//定义小于比较的逻辑，随便定义，multiset会根据这个逻辑来进行排序
	if(lhs._ix < rhs._ix){
		return true;
	}else{
		return false;
	}
}

//比较器的类，重载函数调用运算符即可
struct Comparation{
	bool operator()(const Point& lhs,const Point& rhs){
		if(lhs._ix < rhs._ix){
			return true;
		}else{
			return false;
		}
	}
};

//multiset存储自定义类型的情况
void test2(){
	multiset<Point> number = {
		Point(1,2),
		Point(1,-2),
		Point(-1,-2),
		Point(4,5)
	};
	display(number);
	//此时进行打印会报错，因为multiset容器是会自动进行排序的
	//而我们的Point类里面并没有实现对应的比较函数
	//实现了之后输出才是正确的
	//另一种方式是手写一个比较类，然后在其内部重载函数调用运算符即可
	//然后把该类当成multiset模板参数列表的第二个比较器参数传入
	multiset<Point,Comparation> number2 = {
		Point(1,2),
		Point(1,-2),
		Point(-1,-2),
		Point(4,5)
	};
	display(number2);
}

int main(){
	test2();
	return 0;
}

multiset注意一下count、upper_bound和lower_bound、insert以及equal_range等函数与set的区别，对比学习即可。

map的基本CRUD操作

#include <iostream>
#include <ostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

//打印函数
template<typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem.first << ", " << elem.second << endl;
	}
	cout << endl;
}

void test(){
	//map的初始化
	//map的特征：
	//    1、存放的元素是一个pair类型，key与value值，key是唯一的，不能重复
	//       但是value值重复与否是没有关系的
	//    2、默认情况下，会按照key值进行升序排列
	//    3、底层实现是红黑树
	map<int,string> number = {
		{3,"武汉"},
		{5,"上海"},
		pair<int,string>(4,"北京"),
		pair<int,string>(5,"天津"),
		//也可以使用make_pair函数，其返回类型是一个pair
		make_pair(2,"南京")
	};
	display(number);

	cout << endl << "map的下标访问" << endl;
	//使用下标访问当该下标key存在时访问就相当于查找对应key下标的value值
	cout << "number[2] = " << number[2] << endl;
	//若不存在则就相当于插入一个新的value值，对应的key为下标
	cout << "number[1] = " << number[1] << endl;
	display(number);
	//同时如果对已经存在的key进行赋值的话，就相当于修改操作
	number[1] = "东京";
	display(number);
} 

class Point{
public:
	Point(int ix=0,int iy=0)
	:_ix(ix),_iy(iy)
	{
		cout << "Point()" << endl;
	}

	~Point(){
		cout << "~Point()" << endl;
	}

	friend ostream& operator<<(ostream& os,const Point& rhs);
private:
	int _ix;
	int _iy;
};

ostream& operator<<(ostream& os,const Point& rhs){
	os << "(" << rhs._ix << "," << rhs._iy << ")" << endl;
	return os;
}

//map的自定义类型存储时的特殊情况
void test2(){
	//注意：并非每次出现自定义类型时都要去重写比较运算符
	//因为map是根据key来排序的，如果key键为内置类型，那么库是帮我们写好了比较运算符的
	//此时排序行为和我们的自定义类型都没有关系，就不用在自定义类型中重写比较运算符
	//比如下面这种情况就不需要重写
	map<string,Point> number = {
		{"wuhan",Point()},
		pair<string,Point>("nanjing",Point(1,2)),
		make_pair("dongjing",Point(2,3))
	};

	//map的查找操作
	//其count函数与find函数与之前序列式容器中的count与find效果一样
	//不再赘述
	size_t cnt1 = number.count("wuhan");
	size_t cnt2 = number.count("wuhan2");
	cout << "cnt1 = " << cnt1 << endl;
	cout << "cnt2 = " << cnt2 << endl;

	//map的插入操作
	//1、pair<map<string,Point>::iterator,bool> ret = number.insert(pair<string,Point>("hubei",Point(1,2)));
	//2、auto ret = number.insert((make_pair("hubei2",Point(2,3))));
	auto ret = number.insert({"hubei2",Point(2,3)});
	
	if(ret.second){
		//因为first里面存的是指针数据，所以要用->去引用其存储的pair类型数据
		cout << "插入成功" << ret.first->first << " "
			<< ret.first->second << endl;
	}else{
		cout << "插入失败,该元素存在map中" << endl;
	}
	display(number);

	//map的删除操作
	//对于map而言，使用erase可以删除元素
	//erase两种重载形式：传入迭代器删除 和 传入key值删除
	//因为更常用的是下标访问运算符的方式，所以这里不再赘述erase函数的使用
	
	//cout的下标访问
	//如果下标运算符传入的key值存在，则可以打印出其对应的value
	cout << "number[\"dongjing\"]" << number["dongjing"] << endl;
	//如果下标运算符中传入的key值不存在，那么对于自定义类型而言就直接调用无参构造
	cout << "number[\"1\"]" << number["1"] << endl;
	//如果下标运算符中传入的key值存在且赋予其新值，那么就是修改
	number["1"] = Point(2,4);	
}

int main(){
	test();
	return 0;
}

multimap的CRUD操作

#include <functional>
#include <iostream>
#include <ostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

//打印函数
template<typename Container>
void display(Container& con){
	for(auto& elem : con){
		cout << elem.first << ", " << elem.second << endl;
	}
	cout << endl;
}

void test(){
	//multimap的初始化
	//multimap的特征：
	//    1、存放的元素是一个pair类型，key与value值，key是不唯一的，可以重复
	//       但是value值重复与否是没有关系的
	//    2、默认情况下，会按照key值进行升序排列
	//    3、底层实现是红黑树
	//multimap<int,string> number = {
	//如果想实现降序排列，那么需要将第三个模板参数传入
	multimap<int,string,greater<int>> number = {
		{3,"武汉"},
		{5,"上海"},
		pair<int,string>(4,"北京"),
		pair<int,string>(5,"天津"),
		//也可以使用make_pair函数，其返回类型是一个pair
		make_pair(2,"南京")
	};
	display(number);
#if 0
	multimap不支持下标访问，原因显而易见，key值重复会产生二义性
	cout << endl << "multimap的下标访问" << endl;
	//使用下标访问当该下标key存在时访问就相当于查找对应key下标的value值
	cout << "number[2] = " << number[2] << endl;
	//若不存在则就相当于插入一个新的value值，对应的key为下标
	cout << "number[1] = " << number[1] << endl;
	display(number);
	//同时如果对已经存在的key进行赋值的话，就相当于修改操作
	number[1] = "东京";
	display(number);
#endif
} 

class Point{
public:
	Point(int ix=0,int iy=0)
	:_ix(ix),_iy(iy)
	{
		cout << "Point()" << endl;
	}

	~Point(){
		cout << "~Point()" << endl;
	}

	friend ostream& operator<<(ostream& os,const Point& rhs);
private:
	int _ix;
	int _iy;
};

ostream& operator<<(ostream& os,const Point& rhs){
	os << "(" << rhs._ix << "," << rhs._iy << ")" << endl;
	return os;
}

//multimap的自定义类型存储时的特殊情况
void test2(){
	//注意：并非每次出现自定义类型时都要去重写比较运算符
	//因为multimap是根据key来排序的，如果key键为内置类型，那么库是帮我们写好了比较运算符的
	//此时排序行为和我们的自定义类型都没有关系，就不用在自定义类型中重写比较运算符
	//比如下面这种情况就不需要重写
	multimap<string,Point> number = {
		{"wuhan",Point()},
		pair<string,Point>("nanjing",Point(1,2)),
		make_pair("dongjing",Point(2,3))
	};

	//multimap的查找操作
	//其count函数与find函数与之前序列式容器中的count与find效果一样
	//不再赘述
	size_t cnt1 = number.count("wuhan");
	size_t cnt2 = number.count("wuhan2");
	cout << "cnt1 = " << cnt1 << endl;
	cout << "cnt2 = " << cnt2 << endl;

	//multimap的插入操作
	//1、number.insert(pair<string,Point>("hubei",Point(1,2)));
	//2、auto ret = number.insert((make_pair("hubei2",Point(2,3))));
	number.insert({"hubei2",Point(2,3)});
#if 0
	因为multimap的insert方法返回的并非是pair类型的值，所以无法使用下面注释的这一段内容来打印
	if(ret.second){
		//因为first里面存的是指针数据，所以要用->去引用其存储的pair类型数据
		cout << "插入成功" << ret.first->first << " "
			<< ret.first->second << endl;
	}else{
		cout << "插入失败,该元素存在multimap中" << endl;
	}
#endif
	display(number);

	//multimap的删除操作
	//对于multimap而言，使用erase可以删除元素
	//erase两种重载形式：传入迭代器删除 和 传入key值删除
	//因为更常用的是下标访问运算符的方式，所以这里不再赘述erase函数的使用
#if 0
	因为multimap的insert方法返回的并非是pair类型的值，所以无法使用下面注释的这一段内容来打印
	//cout的下标访问
	//如果下标运算符传入的key值存在，则可以打印出其对应的value
	cout << "number[\"dongjing\"]" << number["dongjing"] << endl;
	//如果下标运算符中传入的key值不存在，那么对于自定义类型而言就直接调用无参构造
	cout << "number[\"1\"]" << number["1"] << endl;
	//如果下标运算符中传入的key值存在且赋予其新值，那么就是修改
	number["1"] = Point(2,4);	
#endif 
}

int main(){
	test();
	return 0;
}

无序关联式容器

无序关联式容器的底层实现使用的是哈希表，关于哈希表有几个概念需要了解：哈希函数、哈希冲突、
解决哈希冲突的方法、装载因子(装填因子、负载因子)

1、哈希函数

是一种根据关键码key去寻找值的数据映射的结构，即：根据key值找到key对应的存储位置。

2、哈希函数的类型

1、直接定址法： H(key) = a * key + b
2、平方取中法： key^2 = 1234^2 = 1522756 ------>227
3、数字分析法：H(key) = key % 10000；
4、除留取余法：H(key) = key mod p (p <= m, m为表长)

3、哈希冲突

就是对于不一样的key值，可能得到相同的地址,即:H(key1) = H(key2)。

4、解决哈希冲突的方法

1、开放定址法
2、链地址法 (推荐使用这种，这也是STL中使用的方法)
3、再散列法
4、建立公共溢出区

5、装载因子

装载因子 a = (实际装载数据的长度n)/(表长m)
a越大，哈希表填满时所容纳的元素越多，空闲位置越少，好处是提高了空间利用率，但是增加了哈希碰
撞的风险，降低了哈希表的性能，所以平均查找长度也就越长；但是a越小，虽然冲突发生的概率急剧下
降，但是因为很多都没有存数据，空间的浪费比较大，经过测试，装载因子的大小在[0.5~0.75]之间比
较合理，特别是0.75。

6、哈希表的设计思想

用空间换时间，注意数组本身就是一个完美的哈希，所有元素都有存储位置，没有冲突，空间利用率也
达到极致。

7、四种无序关联式容器

(unordered_set、unordered_multiset、unordered_map、unordered_multimap)：底层实现使用哈
希表。针对于自定义类型需要自己定义std::hash函数与std::equal_to函数，四种容器的类模板如下：

//unordered_set与unordered_multiset位于#include <unordered_set>中
template < class Key,
	class Hash = std::hash<Key>,
	class KeyEqual = std::equal_to<Key>,
	class Allocator = std::allocator<Key>
> class unordered_set;

template < class Key,
	class Hash = std::hash<Key>,
	class KeyEqual = std::equal_to<Key>,
	class Allocator = std::allocator<Key>
> class unordered_multiset;

 
//unordered_map与unordered_multimap位于#include <unordered_map>中
template< class Key,
	class T,
	class Hash = std::hash<Key>,
	class KeyEqual = std::equal_to<Key>,
	class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

template< class Key,
	class T,
	class Hash = std::hash<Key>,
	class KeyEqual = std::equal_to<Key>,
	class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_multimap;

针对内置类型，初始化、遍历、查找、插入、删除、修改、下标访问这些与关联式容器类似，无序关联
式容器中元素没有顺序，底层采用的是哈希表。特别是：对于自定义类型而言，没有针对key值对应的哈
希函数以及比较函数，所以需要自己写。

无序关联式容器unordered_set的示例

#include <iostream>
#include <ostream>
#include <unordered_set>

using namespace std;

template<typename Container>
void display(const Container& con){
	for(auto& elem : con){
		cout << elem << " ";
	}
	cout << endl;
}

void test(){
	//unordered_set 的特征
	//1、key值是唯一，不能重复
	//2、key值是没有顺序的
	//3、底层使用的是哈希
	//因为容器的基本使用都是差不多的，所以这里不再赘述，和set基本一致
	//只有下面测试函数test2中的哈希和比较函数的一点不同，其它基本一致
	unordered_set<int>  number= {1,3,5,7,9,6,4,2,3,1,3};
	display(number);
}

//自定义数据类型
class Point{
public:
	Point(int ix = 0,int iy = 0)
	:_ix(ix)
	 ,_iy(iy)
	{
		cout << "Point()" << endl;
	}

	~Point(){
		cout << " ~Point()" << endl;
	}

	friend ostream& operator<<(ostream& os,const Point& rhs);
	friend class HashPoint;
	friend bool operator==(const Point& lhs,const Point& rhs);
private:
	int _ix;
	int _iy;
};

ostream& operator<<(ostream& os,const Point& rhs){
	os << "(" << rhs._ix << ", " << rhs._iy << ")" << endl;
	return os;
}

//哈希函数的实现，函数对象的形式
struct HashPoint{
	size_t operator()(const Point& rhs)const {
		cout << "HashPoint" << endl;
		return (rhs._ix << 1)^(rhs._iy << 2);
	}
};

//标准命名空间std中的类模板hash的全特化版本：std::hash
namespace std{ //这是标准命名空间的扩展
	//哈希函数的特化（全特化）的形式
	template<>
	struct hash<Point>
	{
		size_t operator()(const Point& rhs) const
		{
			//此处参考上面的哈希函数
			return true;
		}
	};
};// end of namespace


//比较函数的实现:std::equal_to
bool operator==(const Point& lhs,const Point& rhs){
	cout << "operator==" << endl;
	return (lhs._ix == rhs._ix && lhs._iy == rhs._iy);
}

void test2(){
	//对于unordered_set容器在使用自定义数据类型时需要
	//传入第二个模板参数：hash函数
	//然后还有第三个模板参数equal_to，只不过这个模板参数是自定义类型中的==运算符函数
	//这个函数需要被实现以定义某种比较两个自定义类型对象是否相等
	//若不实现的话则哈希函数无法判断是否发生哈希冲突（即相同对象存储到了同一块位置）
	unordered_set<Point,HashPoint> number = {
		Point(1,2),
		Point(1,2), 
		Point(1,-2),
		Point(3,2),
		Point(-1,4)
	};
	display(number);
}

int main(){
	test();
	return 0;
}

unordered_multiset的示例

其与unordered_set的使用没有什么区别，只要记住下述的一点特性即可：
1、key值是不唯一的，可以重复
2、key值是没有顺序的
3、底层使用的是哈希结构

unordered_map的示例

和 map 基本没有区别，就是其不会根据key值进行排序而已，然后底层实现是哈希不是红黑树，基本使用是一样的。

unordered_multimap的示例

就记几个特性就行，基本都差不多。