【C 中的STL】

我莫名又来了孤独感，可城市分明人山人海.............................................................................

目录

前言

一、【STL简介]

1.1【 STL是什么】

1.2【 STL的发行版本】

1.3【STL的缺陷】

二、【string】

2.1 【string的介绍】

2.2 【string类的常用接口说明】

1.【 常见构造方式】

2. 【容量操作方式】

3.【 访问及遍历方式】

4. 【增删查改操作】

5.【非成员函数】

6.【比较，拷贝，替换以及交换】：

1.【比较——compare】

2.【拷贝——copy】

3.【替换——replace】

3.【交换——swap】

7.【vs和g++下string结构的说明】

1.【vs下string的结构】

2.【g++下string的结构】

2.3【string的模拟实现】

2.4【模拟实现中的问题】

1.【拷贝构造】

2.【写时拷贝】

三、【vector】

3.1 【vector的介绍】

3.2【vector的使用】

1.【vector的构造】

2.【vector中的迭代器】

begin和end

rbegin和rend

3.【容量操作】

4.【增删查改】

3.3【vector的模拟实现】

3.4【实现中遇到的问题】：

1、【vector迭代器失效】

2、【不使用memcpy的原因】

3.【动态二维数组理解】

四、【list】

4.1【list的介绍】

4.2 【list的使用】

1.【 list的构造】

2.【list 迭代器的使用】

3.【容量操作】

resize

splice

empty和size

unique

assign

4 .【list 的头和尾】

5. 【增删查改】

4.3【list的实现】

1.【list的组成】

2.【list的迭代器】

3.【list的实现代码部分】

4.4.【实现中遇到的问题】

【list的迭代器失效】

4.5【list与vector的对比】

五、【stack和queue】

5.1【stack】

5.1.1【stack的介绍】

5.1.2【stack的使用】

5.1.3【stack的模拟实现】

5.2【queue】

5.2.1【queue的介绍】

5.2.2【queue的使用】

5.2.3【queue的模拟实现】

5.3【deque的简单说明】

5.3.1【deque的介绍】

5.3.2 【deque的缺陷】

5.3.3【选择deque作为底层默认容器的原因】

5.4【优先级队列】

5.4.1【priority_queue的介绍】

5.4.2【priority_queue的使用】

5.4.3【priority_queue的模拟实现】

5.5【容器适配器】

六、【map和set】

6.1【关联式容器和序列式容器】

1、【树形结构和哈希结构】

2、【键值对】

6.2【set】

6.2.1【set的介绍】

6.2.2【set的使用】

1.【set的构造】

2.【迭代器的使用】

3.【增删查改】

6.2.3.【multiset】

1.【multiset的介绍】

2.【multiset的使用】

6.3【map】

6.3.1【map的介绍】

6.3.2【map的使用】

1、【map的构造】

2、【迭代器的使用】

3、【增删查改】

插入函数

查找函数

删除函数

map的[ ]运算符重载

其他成员函数

6.3.3【multimap】

6.4【set和map的模拟实现】

1、【问题说明及解决】

2、【红黑树迭代器的实现】

3、【set的模拟实现】

4、【map的模拟实现】

5、【封装后的完整代码】

七、【unordered_map和unordered_set】

7.1、【unordered_set】

7.1.1【unordered_set的介绍】

7.1.2【unordered_set的使用】

1、【unordered_set的定义】

2、【函数接口】

3、【unordered_multiset】

7.2、【unordered_map】

7.2.1【unordered_map的介绍】

7.2.2【unordered_map的使用】

1、【unordered_map的定义】

2、【函数接口】

3、unordered_multimap

7.3、【unordered_map和unordered_set的模拟实现】

1、【问题及其说明】

2、【哈希桶迭代器的实现】

3、【unordered_set的模拟实现】

4、【unordered_map的模拟实现】

5、【封装后的完整代码】

7.4【map/set和unordered_set/unordered_map的区别】

1、map/set与unordered_map/unordered_set底层数据结构的区别

2、map/set与unordered_map/unordered_set的性能测试

八、【位图】

8.1【位图的介绍】

【引入】

【概念】

8.2【位图的使用】

1、【定义方式】

2、【函数接口】

3、【bitset运算符的使用】

8.3【位图的模拟实现】

1、【构造函数】

2、【成员函数】

8.4【位图的应用】

总结

---

前言

网上有句话说：“不懂STL，不要说你会C++”。STL是C++中的优秀作品，有了它的陪伴，许多底层的数据结构像顺序表，链表，栈和队列，以及堆，等甚至包括算法都不需要自己重新造轮子，就好像站在巨人的肩膀上，健步如飞的进行开发。

---

一、【STL简介]

1.1【 STL是什么】

STL(standard template libaray)又名“ 标准模板库 ”：是C++标准库的重要组成部分，它不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。它主要包含六大组成部分，又叫六大组件：

本博客对于这六大组件都会有所涉及，还请耐心看完。

1.2【 STL的发行版本】

【原始版本】
Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本，本着开源精神，他们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码，无需付费。唯一的条件就是也需要向原始版本一样做开源使用。所以原始版本也叫【 HP 版本】    --所有STL实现版本的始祖。
【P. J. 版本】
由P. J. Plauger开发，继承自HP版本，被Windows Visual C++采用，不能公开或修改。

缺陷：可读性比较低，符号命名比较怪异。
【RW版本】
由Rouge Wage公司开发，继承自HP版本，被C+ + Builder 采用，不能公开或修改，可读性一般。
【SGI版本】
由Silicon Graphics Computer Systems，Inc公司开发，继承自HP版 本。被GCC(Linux)采用，可移植性好，可公开、修改甚至贩卖，从命名风格和编程 风格上看，阅读性非常高。

本篇博客主要参考的就是这个版本。

1.3【STL的缺陷】

1. STL库的更新太慢了。这个得严重吐槽，上一版靠谱是C++98，中间的C++03基本一些修订。C++11出来已经相隔了13年，STL才进一步更新。
2. STL现在都没有支持线程安全。并发环境下需要我们自己加锁。且锁的粒度是比较大的。
3. STL极度的追求效率，导致内部比较复杂。比如类型萃取，迭代器萃取。
4. STL的使用会有代码膨胀的问题，比如使用vector/vector/vector这样会生成多份代码，当然这是模板语法本身导致的。

二、【string】

在C语言中，我们知道字符串是以 '\0' 结尾的一些字符的集合，而为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP（面向对象编程）的思想，而且底层空间需要用户自己进行管理，稍不留神可能还会导致越界访问。

而STL为了体现C++中的OOP的思想，设计了string这一容器，它将相关算法封装到string的内部，当用户定义string对象时可以直接调用相关算法，而在正式开始介绍string之前，

【先附一份优质博客以供参考】：

C++面试中string类的一种正确写法 | 酷 壳 - CoolShell

2.1 【string的介绍】

【首先我们要知道以下内容】：

1. 字符串是表示字符序列的类
2. 标准的字符串类提供了对此类对象的支持，其接口类似于标准字符容器的接口，但添加了专门用于操作单字节字符字符串的设计特性。
3. string类是使用char即作为它的字符类型。
4. string类是basic_string模板类的一个实例，它使用char来实例化basic_string模板类，并用char_traits和allocator作为basic_string的默认参数。
5. 注意，这个类独立于所使用的编码来处理字节:如果用来处理多字节或变长字符(如UTF-8)的序列，这个类的所有成员(如长度或大小)以及它的迭代器，将仍然按照字节(而不是实际编码的字符)来操作。

6.在使用string类时，必须包含#include头文件以及using namespace std;

【总结】：
1. string是表示字符串的字符串类
2. 该类的接口与常规容器的接口基本相同，再添加了一些专门用来操作string的常规操作。

3. string在底层实际是：basic_string模板类的别名即使用了typedef：

typedef basic_string<char, char_traits, allocator>   string  ;
4. 不能操作多字节或者变长字符的序列，在使用时要包含对应的头文件。

2.2 【string类的常用接口说明】

1.【 常见构造方式】

【参考资料】：

 http://www.cplusplus.com/reference/string/string/string/

using namespace std;
void TestString1()
{
	string s1;
	string s2("hello world");
	string s3(s2);
	//string s3("hello string", 3);  //复制"hello string"的前3个字符
	string s4(10, 's');            //生成10个's'字符的字符串
	string s5(s2);                 //生成s2的复制品
	string s6(s2, 0, 4);           //复制s2中从字符位置0开始并跨越4个字符的部分
	cout << s1 << endl;
	cout << s2 << endl;
	cout << s3 << endl;
	cout << s4 << endl;
	cout << s5 << endl;
	cout << s6 << endl;
}



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

2. 【容量操作方式】

【参考资料】：

cplusplus.com/reference/string/string/

string ::size和string::length都是同义词并返回相同的值

【使用示例】：

void TestString2()
{
	string s1("hello world");
	cout << s1.max_size() << endl;
	cout << s1.capacity() << endl;
	cout << s1.size() << endl;
	cout << s1.length() << endl;
	cout << s1 << endl;
	s1.reserve(100);
	cout << s1.capacity() << endl;
	cout << s1.size() << endl;
	cout << s1.length() << endl;
	s1.resize(20,'!');
	cout << s1.capacity() << endl;
	cout << s1.size() << endl;
	cout << s1.length() << endl;
	cout << s1 << endl;
	cout << s1.empty() << endl;
	s1.clear();
	cout << s1 << endl;
	cout << s1.empty() << endl;




}

这里展示了reserve,capacity,resize,length,clear,empty,等接口的用法。

// 利用reserve提高插入数据的效率，避免增容带来的开销
//====================================================================================
void TestPushBack()
{
	string s;
	size_t sz = s.capacity();
	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

这里我们可以看到初始容量是15，那么达到它的容量了以后会怎么办呢？会进行扩容吗？

答案是会的，会自动扩容，初始容量为15，第一次扩容为31，之后按接近1.5倍的速率增长。

所以我们可以通过利用reverse来提前对容量进行规划，以提高效率减少开销。

clear和resize的用法注意事项：

void Teststring2()
{
	// 注意：string类对象支持直接用cin和cout进行输入和输出
	string s("hello, bit!!!");
	cout << s.size() << endl;
	cout << s.length() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小
	s.clear();
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到10个，多出位置用'a'进行填充
	// “aaaaaaaaaa”
	s.resize(20, 'a');
	cout << s << endl;
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到15个，多出位置用缺省值'\0'进行填充
	// "aaaaaaaaaa\0\0\0\0\0"
	// 注意此时s中有效字符个数已经增加到15个
	s.resize(15);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中有效字符个数缩小到5个
	s.resize(5);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;
}

注意事项：
 1、当n大于对象当前的size时，将size扩大到n，扩大的字符为c，若c未给出，则默认为’\0’。
 2、当n小于对象当前的size时，将size缩小到n。

   3、clear只会改变容器的大小不会改变容量，哪怕发生过扩容。

【注意】：
1. size()与length()方法底层实现原理完全相同，引入size()的原因是为了与其他容器的接口保持一致，一般情况下基本都是用size()。
2. clear()只是将string中有效字符清空，不改变底层空间大小。

3. resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，不同的是当字符个数增多时：resize(n)用0来填充多出的元素空间，resize(size_t n, char c)用字符c来填充多出的元素空间。需要注意的是resize在改变元素个数时，如果是将元素个数增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变。
4. reserve(size_t  res_arg=0)：为string预留空间，不改变string中有效元素个数，当reserve的参数小于string的底层空间总大小时，reserver不会改变容量大小。也就是说reserve只能增加容量而不能减小容量。

3.【 访问及遍历方式】

参考资料：

【cplusplus.com/reference/string/string/】

有关迭代器的函数：

这里可以看一下具体使用方法：
使用 [ ] 和正向迭代器以及反向迭代器来实现遍历

void TestString3()
{
	string s3("hello world");
	const string s4("aaaaa");
	cout << s3[0] << endl;//可以直接使用[]打印
	cout << s4[0] << endl;//可以直接使用[]打印
	s3[0] = 'H';//可直接修改
	//s4[0] = 'A';//此时s4类似常量字符串，不能修改。
	// 
	//1.For循环+operator[]
;	for (int i = 0; i < s3.size(); i++)
	{
		cout << s3[i];
	}
    cout << endl;
    //2.迭代器进行遍历
    string::iterator it = s3.begin();
	/// <summary>
	/// 这里也可以替换为auto it=s3.begin
	/// </summary>
	while (it != s3.end())
	{
		cout << *it;
		it++;
	}
	cout << endl;
	string::reverse_iterator  rit = s3.rbegin();
	while (rit != s3.rend())
	{
		cout << *rit;
		rit++;
	}
	cout << endl;
	//3.范围for遍历 
	for (auto ch : s3)
	{
		cout << ch ;
	}


}

int main()
{
	//TestString1();
	//TestString2();
	//TestPushBack();
	TestString3();
	return 0;
}

4. 【增删查改操作】

【参考资料】：

【cplusplus.com/reference/string/string/】

使用示例：

void TestString1()
{
	string s1("hello world");
	cout << s1 << endl;
	s1.push_back('a');
	cout << s1 << endl;
	s1.append("b");
	cout << s1 << endl;
	s1 += 'c';
	s1 += "abc";
	cout << s1 << endl;
	cout << s1.c_str() << endl;


}

rfind默认从后向前寻找，rfind找的是字符串中某个字符最后出现的位置，而find找的是某个字符首次出现的位置，而当字符串中不包含某个字符时，就会返回npos

先面来看一个示例：

//size_t find (const string& str, size_t pos = 0) const;
//size_t find (const char* s, size_t pos = 0) const;
//size_t find (char c, size_t pos = 0) const;


void TestString2()
{
	string file("Test.cpp.pp");
	size_t pos = file.rfind('.');
	cout << pos << endl;
	string suffix(file.substr(pos, file.size() - pos));
	cout << suffix << endl;
	string url("http://www.cplusplus.com/reference/string/string/find/");
	size_t start = url.find("/");
	if (start == string::npos)
	{
		cout << "invalid url" << endl;
		return;
	}
	cout << start << endl;
}


//size_t rfind (const string& str, size_t pos = npos) const;
//size_t rfind (const char* s, size_t pos = npos) const;
//size_t rfind (char c, size_t pos = npos) const;

下面是整体的使用用例：

void TestString3()
{
	    // npos是string里面的一个静态成员变量
		// static const size_t npos = -1;
		// 取出url中的域名
	string url("http://www.cplusplus.com/reference/string/string/find/");
	cout << url << endl;
	size_t start = url.find("://");
	if (start == string::npos)
	{
		cout << "invalid url" << endl;
		return;
	}
	start += 3;
	size_t finish = url.find('/', start);
	string address = url.substr(start, finish - start);//利用substr将“//”和“第一个‘/’ ”之间
                                                       //的数据截取出来
	cout << address << endl;

	// 删除url的协议前缀
	size_t pos = url.find("://");
	url.erase(0, pos + 3);
	cout << url << endl;
}

删除操作使用示例：

void Test_String_Erase()
{
	

	//1.使用pop_back进行尾删(void pop_back();)
	string s1("C++");
	s1.pop_back();
	s1.pop_back();
	cout << s1 << endl; //C
	string s2("I like C++!!!");



	//2.使用erase删除
	// string& erase (size_t pos = 0, size_t len = npos);
	//iterator erase(iterator p);
	//iterator erase(iterator first, iterator last);
	//erase(pos, n)删除pos位置开始的n个字符
	s2.erase(8, 5); //I like C

	//erase(pos)删除pos位置的字符
	s2.erase(s2.end() - 1); //I like

	//erase(pos1, pos2)删除[pos1pos2)上所有字符
	s2.erase(s2.begin() + 1, s2.end()); //I

	cout << s2 << endl; //I
}

提取子串：

void Test_String()
{
	//string substr(size_t pos = 0, size_t len = npos) const;
	string s1("abcdef");
	string s2;

	//substr(pos, n)提取pos位置开始的n个字符序列作为返回值
	s2 = s1.substr(2, 4);
	cout << s2 << endl; //cdef

}

【注意】：
1. 在string尾部追加字符时，s.push_back(c) / s.append(1, c) / s += 'c'三种的实现方式差不多，一般情况下string类的+=操作用的比较多，+=操作不仅可以连接单个字符，还可以连接字符串。
2. 对string操作时，如果能够大概预估到放多少字符，可以先通过reserve把空间预留好。

5.【非成员函数】

【参考资料】：

【cplusplus.com/reference/string/string/】

使用示例:

void Test_String()
{

	/*string类中对 + 运算符进行了重载，重载后的 + 运算符支持以下几种类型的操作：
		string类 + string类
		string类 + 字符串
		字符串 + string类
		string类 + 字符
		字符 + string类
		它们相加后均返回一个string类对象。*/
	string s1("hello");
	cout << s1 << endl;
	string s2("CSDN");
	string s3;
	s3 = s1+s2;
	cout << s3 << endl;
	s3 = s1+"world";
	cout << s3 << endl;
	s3 = s1+"x";
	cout << s3 << endl;
	s1 += s2;
	cout << s1 << endl;
	string s4("abcd");
	string s5("abde");
	cout << (s4> s5) << endl; //0
	cout << (s4 < s5) << endl; //1
	cout << (s4 == s5) << endl; //0
}

getline函数的使用：

我们知道，使用>>进行输入操作时，当>>读取到空格便会停止读取，基于此，我们将不能用>>将一串含有空格的字符串读入到string对象中。

这里就需要用到getline函数：

用法一、

void Test_String()
{
	//istream& getline(istream & is, string & str);
	//getline函数将从is中提取到的字符存储到str中，直到读取到换行符’\n’为止。
	string s;
	getline(cin, s); //输入：hello CSDN
	cout << s << endl; //输出：hello CSDN
	
}

用法二、

void Test_String()
{
	//istream& getline (istream& is, string& str, char delim);
	//getline函数将从is中提取到的字符存储到str中，直到读取到分隔符delim或不传参数就遇到换行符’\n’为止
	string s;
	getline(cin, s, 'D'); //输入：hello CSDN
	cout << s << endl; //输出：hello CS
	

}

6.【比较，拷贝，替换以及交换】：

1.【比较——compare】

int compare (const string& str) const;
int compare (size_t pos, size_t len, const string& str) const;
int compare (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen)const;

比较规则：
 1、比较字符串中第一个不匹配的字符对应ASCII，较小的字符串小，或者所有比较字符都匹配，但比较字符串较短，字符串小，小就返回小于0的值。
 2、比较字符串中第一个不匹配的字符值，较大的字符串大，或者所有比较字符都匹配，但比较字符串较长，字符串大，大则返回大于0的值。
 3、比较的两个字符串相等，则返回0。

使用示例：

void Test_String()
{
	string s1("hello world");
	string s2("hello CSDN");

	//"hello world"和"hello CSDN"比较
	cout << s1.compare(s2) << endl; //1

	//"ell"和"hello CSDN"比较
	cout << s1.compare(1, 3, s2) << endl; //-1

	//"hello"和"hello"比较
	cout << s1.compare(0, 4, s2, 0, 4) << endl; //0

	
}

注意：除了支持string类之间进行比较，compare函数还支持string类和字符串进行比较。

2.【拷贝——copy】

size_t copy (char* s, size_t len, size_t pos = 0) const;

使用示例：

void Test_String()
{
	string s("abcdef");
	char str[20];

	//copy(str, n, pos)复制pos位置开始的n个字符到str字符串
	size_t length = s.copy(str, 4, 2);//返回的是成功拷贝的字符数
	cout << length << endl;
	cout << sizeof(str) << endl;
	//copy函数不会在复制内容的末尾附加'\0'，需要手动加
	str[length] = '\0';
	cout << str << endl; //dcef
	

}

3.【替换——replace】

使用replace函数完成string的替换：

string& replace (size_t pos, size_t len, const char* s);
string& replace (size_t pos, size_t len, size_t n, char c);

使用示例：

void Test_String()
{
	string s("hello world");

	//replace(pos, len, str)将pos位置开始的len个字符替换为字符串str
	s.replace(6, 4, "CSDN"); //hello CSDNd
	cout << s << endl;
	//replace(pos, len, n, char)将pos位置开始的len个字符替换为n个字符char
	s.replace(10, 1, 3, '!'); //hello CSDN!!!

	cout << s << endl;
	
}

3.【交换——swap】

使用swap函数完成两个string类的交换：

void swap (string& x, string& y);
void swap (string& str);

使用示例：

void Test_String()
{
	string s1("hello");
	string s2("CSDN");

	//使用string类的成员函数swap交换s1和s2
	s1.swap(s2);
	cout << s1 << endl; //CSDN
	cout << s2 << endl; //hello

	//使用非成员函数swap交换s1和s2
	swap(s1, s2);
	cout << s1 << endl; //hello
	cout << s2 << endl; //CSDN
	
}

string类中还有一些其他的操作，这里不一一列举，大家在需要用到时不明白了查文档即可。

7.【vs和g++下string结构的说明】

下述结构是在32位平台下进行验证，32位平台下指针占4个字节。

1.【vs下string的结构】

string总共占28个字节，内部结构稍微复杂一点，先是有一个联合体，联合体用来定义string中字符串的存储空间：

首先，当字符串长度小于16时，使用内部固定的字符数组来存放当字符串长度大于等于16时，从堆上开辟空间这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，那string对象创建好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高。
其次，还有一个size_t字段保存字符串长度，一个size_t字段保存从堆上开辟空间总的容量。
最后，还有一个指针做一些其他事情。
故总共占16+4+4+4=28个字节。

2.【g++下string的结构】

g++下，string是通过写时拷贝实现的，string对象总共占4个字节，内部只包含了一个指针，该指针将来指向一块堆空间，内部包含了如下字段：

struct _Rep_base
{
 size_type _M_length;//空间总大小
 size_type _M_capacity;//字符串有效长度
 _Atomic_word _M_refcount;//引用计数&&指向堆空间的指针，用来存储字符串。
};

但是string类中仍然有一些缺陷这里推荐博客：

STL 的string类怎么啦？_stl里为什么没讲string-CSDN博客

2.3【string的模拟实现】

附上一篇优质博客：C++STL详解（二）—— string类的模拟实现_string(const string& s): _str(), _size(), _capacit-CSDN博客

我们为了跟更加深入了解string除了了解其使用方法以外，最好能够模拟实现string：
下面是代码部分：

【String.h部分】：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string>
#include <stdbool.h>
#include <iostream>
using namespace std;
namespace str
{
	class String
	{
	public:
		void swap(str::String& s);
		const static size_t npos = -1;
		typedef char* iterator;
		typedef const char* const_iterator;
		String(const char* str = "");
		~String();
		String(const String& s);
		String& operator=(const str::String& s);
		size_t capacity() const;
		size_t size() const;
		const char* c_str() const;
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;
		const char& operator[](size_t pos)const;
		void push_back(char ch);
		void append(const char* str);
		void reserve(size_t n);
		String& operator+=(char ch);
		String& operator+=(const char* str);
		void Insert(size_t pos, const char* str);
		void Insert(size_t pos, char ch);
		void erase(size_t pos, size_t len = npos);
		bool operator<(const String& s)const;
		bool operator==(const String& s)const;
		bool operator>(const String& s)const;
		bool operator<=(const String& s)const;
		bool operator!=(const String& s)const;
		bool operator>=(const String& s)const;
		void clear();
		void resize(size_t n, char ch = '\0');
		size_t find(char ch, size_t pos = 0);
		size_t find(const char* sub, size_t pos = 0);
		String substr(size_t pos, size_t len = npos);
	private:
		char* _str;
		
		size_t _size;
		size_t _capacity;
	};
}
ostream& operator<<(ostream& out, const str::String& s);
istream& operator>>(istream& in, str::String& s);

【String.cpp部分】：

#define _CRT_SECURE_NO_WARNINGS
#include "String.h"


str::String::String(const char* str)
	:_size(strlen(str))
	,_capacity(_size)
{
	_str = new char[_capacity + 1];
	strcpy(_str, str);

}
str::String::String(const str::String& s)
{
	_str = new char[s._capacity + 1];
	strcpy(_str, s._str);
	_size = s._size;
	_capacity = s._capacity;
}
str::String& str::String::operator=(const str::String& s)
{
	if (this != &s)
	{
		char* tmp = new char[s._capacity + 1];
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;
		_size = s._size;
		_capacity = s._capacity;
	}
	return *this;

}

str::String::~String()
{
	delete[] _str;
	_str = nullptr;
	_size = _capacity = 0;
}
size_t str::String::capacity() const
{
	return _capacity;
}
size_t str::String::size() const
{
	return _size;
}
const char* str::String:: c_str() const
{
	return _str;
}
str::String::iterator str::String:: begin()
{
	return _str;
}
str::String::iterator str::String::end()
{
	return _str + _size;
}
str::String::const_iterator str::String::begin() const
{
	return _str;
}
str::String::const_iterator str::String::end() const
{
	return _str + _size;
}
const char& str::String::operator[](size_t pos)const
{
	assert(pos < _size);
	return _str[pos];
}
void str::String::reserve(size_t n)//按需调整空间
{
	if (_capacity < n)//当前容量小于指定容量就进行扩容，将数组的内容扩大。
	{
		char* tmp = new char[n + 1];//多开的1个空间是为了存储‘\0’
		strcpy(tmp, _str);//之后将原字符串中的内容拷贝到新空间
		delete[] _str;//并释放原空间
		_str = tmp;//将原数组指向新开辟的数组空间
		_capacity = n;//并更新容量
	}
}
void str::String::push_back(char ch)
{

	if (_size == _capacity)在进行尾插之前，要先判断是否需要扩容
	{
		reserve((_capacity == 0) ? 4 : _capacity * 2);
	}
	_str[_size] = ch;
	_size++;
	_str[_size] = '\0';
}
void str::String::append(const char* str)
{
	size_t len = strlen(str);
	if (_size + len >= _capacity)
	{
		reserve(_size + len);
	}
	strcpy(_str + _size, str);
	_size += len;
}
str::String& str::String::operator+=(char ch)
{
	push_back(ch);
	return *this;
}
str::String& str::String::operator+=(const char* str)
{
	append(str);
	return *this;
}
void str::String::Insert(size_t pos, char ch)
{
	if (_size == _capacity)//判断是否需要扩容
	{
		reserve((_capacity == 0) ? 4 : 2 * _capacity);
	}
	size_t end = _size + 1;//这里定义end位于‘\0’之后的一个位置
	while (end > pos)//将pos之后的数据全都向后移
	{
		_str[end] = _str[end-1];
		end--;
	}
	_str[pos] = ch;//将pos位置处放上需要插入的字符
	_size++;//最后将_size++即可
	/*int  end = _size;
	while (end >=(int) pos)//这里转换成int的原因是，pos为无符号整数，直接进行比较大小会导致end
	{//进行类型提升将end也当作无符号整数，当end--为-1时，由于end变为无符整形，-1=4294967295
        _str[end+1] = _str[end];//会大于0
		end--;
	}
	_str[pos] = ch;
	_size++;*/
}
bool str::String:: operator<(const String& s)const
{
	return strcmp(_str, s._str) < 0;
}

bool str::String:: operator==(const String& s)const
{
	return strcmp(_str, s._str)== 0;
}

bool str::String:: operator>(const String& s)const
{
	return strcmp(_str, s._str) > 0;
}

bool str::String:: operator<=(const String& s) const
{
	return *this < s || *this == s;
}

bool str::String::operator>=(const String& s) const
{
	return !(*this < s);
}

bool str::String::operator!=(const String& s) const
{
	return !(*this == s);
}
void str::String::clear()
{
	_str[0] = '\0';
	_size = 0;
}
ostream& operator<<(ostream& out, const str::String& s)
{
	/*for (size_t i = 0; i < s.size(); i++)
	{
		out << s[i];
	}
	return out;*/
	for (auto ch : s)//范围for遍历字符串
	{
		out << ch;
	}
	return out;
	/*str::String::const_iterator it = s.begin();
	while (it != s.end())
	{
		out << *it;
		it++;
	}
	return out;*/

}
istream& operator>>(istream& in, str::String& s)
{
	s.clear();//在流提取之前要先将字符串里之前的数据清空，不然提取到的新字符串就会尾插在旧数据
	char ch;//之后
	ch = in.get();//由于cin类似于scanf遇到空格就不会再进行读取了因此这里需要用到istream里的get
	char buffer[129];//这里定义一个数组，用来存放读取到的字符，由于是在函数中创建的，不会占用
	size_t i = 0;//字符串的空间，跟随函数的生命周期
	while (ch != ' ' && ch != '\n')
	{
		buffer[i++] = ch;
		if (i == 128)//如果读取的字符太长数组都存满了，还没有读取结束
		{//就将获取到的字符先放入到字符串中，之后重新进行读取
			buffer[i] = '\0';
			s += buffer;
			i = 0;
		}
		ch = in.get();
	}
	if (i != 0)//如果字符不长，则可以直接将其放到字符串中
	{
		buffer[i] = '\0';
		s += buffer;
	}
	return in;
}

void str::String::Insert(size_t pos, const char* str)
{
	assert(pos < _size);
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		reserve(len + _size);
	}
	//int end = _size + len;
	//while (end > pos)
	//{
	//	_str[end] = _str[end - len];
	//	end--;
	//}
	int end = _size;
	while (end >= (int)pos)
	{
		_str[end + len] = _str[end];
		end --;
	}
	strncpy(_str + pos, str, len);
	_size += len;
}
void str::String::erase(size_t pos, size_t len )
{
	assert(pos < _size);
	if (len == npos || len + pos > _size)
	{
		_str[pos] = '\0';
		_size = pos;
	}
	else
	{
		size_t begin = pos + len;
		while (begin <= _size)
		{
			_str[begin - len] = _str[begin];
			begin++;
		}
		_size -= len;
	}
}
void str::String::resize(size_t n, char ch)
{
	if (n <= _size)
	{
		_str[n] = '\0';
		_size = n;
	}
	else
	{
		reserve(n);
		while (_size < n)
		{
			_str[_size] = ch;
			++_size;
		}
		_str[_size] = '\0';
	}
}
size_t str::String::find(char ch, size_t pos)
{
	assert(pos < _size);
	for (size_t i = pos; i < _size; i++)
	{
		if (_str[i] == ch)
		{
			return i;
		}
	}
	return npos;

}
size_t str::String::find(const char* sub, size_t pos)
{
	assert(pos < _size);
	const char* p = strstr(_str + pos, sub);
	if (p)
	{
		return p - _str;
	}
	else
	{
		return npos;
	}
}
str::String str::String::substr(size_t pos, size_t len )
{
	assert(pos < _size);
	str::String s;
	size_t end = pos + len;
	if (len == npos || len + pos > _size)
	{
		len = _size - pos;
		end = _size;

	}
	s.reserve(len);
	for (size_t i = pos; i < end; i++)
	{
		s += _str[i];
	}

	return s;

}

【Test.cpp部分】：

#define _CRT_SECURE_NO_WARNINGS
#include "String.h"

void test_string2()
{
	str::String s1("hello world");
	cout << s1.c_str() << endl;
	s1.push_back(' ');
	s1.append("hello bit hello bit");

	cout << s1.c_str() << endl;

	s1 += '#';
	s1 += "*********************";
	cout << s1.c_str() << endl;

	str::String s2;
	s2 += '#';
	s2 += "*********************";
	cout << s2.c_str() << endl;
}

void test_string3()
{
	str::String s1("hello world");
	cout << s1.c_str() << endl;

	s1.Insert(5, '%');
	cout << s1.c_str() << endl;

	s1.Insert(s1.size(), '%');
	cout << s1.c_str() << endl;

	s1.Insert(0, '%');
	cout << s1.c_str() << endl;
}

void test_string4()
{
	str::String s1("hello world");
	str::String s2("hello world");

	cout << (s1 >= s2) << endl;

	//s1[0] = 'z';
	cout << (s1 >= s2) << endl;

	cout << s1 << endl;
	//cin >> s1;
	cout << s1 << endl;

}


void Test_string1()
{
	str::String s1("hello world");
	str::String s2;
	//cout << s1 << endl;
	//cout << s2 << endl;
		for (size_t i = 0; i < s1.size(); i++)
	{
		cout << s1[i] << " ";
	}
	cout << endl;

	str::String::iterator it = s1.begin();
	while (it != s1.end())
	{
		(*it)++;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto& ch : s1)
	{
		ch++;
		cout << ch << " ";
	}
	cout << endl;

	cout << s1.c_str() << endl;
}



void test_string5()
{
	str::String s1("hello world");
	s1.Insert(5, "abc");
	cout << s1 << endl;

	s1.Insert(0, "xxx");
	cout << s1 << endl;

	s1.erase(0, 3);
	cout << s1 << endl;

	s1.erase(5, 100);
	cout << s1 << endl;

	s1.erase(2);
	cout << s1 << endl;
}

void test_string6()
{
	str::String s1("hello world");
	cout << s1 << endl;

	s1.resize(5);
	cout << s1 << endl;

	s1.resize(25, 'x');
	cout << s1 << endl;
}

void test_string7()
{
	str::String s1("test.cpp.tar.zip");
	//size_t i = s1.find('.');
	//size_t i = s1.rfind('.');

	//string s2 = s1.substr(i);
	//cout << s2 << endl;

	str::String s3("https://legacy.cplusplus.com/reference/string/string/rfind/");
	//string s3("ftp://www.baidu.com/?tn=65081411_1_oem_dg");
	// 协议
	// 域名
	// 资源名

	str::String sub1, sub2, sub3;
	size_t i1 = s3.find(':');
	if (i1 != str::String::npos)
		sub1 = s3.substr(0, i1);
	else
		cout << "没有找到i1" << endl;

	size_t i2 = s3.find('/', i1 + 3);
	if (i2 != str::String::npos)
		sub2 = s3.substr(i1 + 3, i2 - (i1 + 3));
	else
		cout << "没有找到i2" << endl;

	sub3 = s3.substr(i2 + 1);

	cout << sub1 << endl;
	cout << sub2 << endl;
	cout << sub3 << endl;
}

void test_string8()
{
	str::String s1("hello world");
	str::String s2 = s1;
	cout << s1 << endl;
	cout << s2 << endl;

	str::String s3("xxxxxxxxxxxxxxxxxxx");
	s2 = s3;

	cout << s2 << endl;
	cout << s3 << endl;
}

void test_string9()
{
	str::String s1("hello world");
	cin >> s1;
	cout << s1 << endl;
	cout << s1.size() << endl;
	cout << s1.capacity() << endl;
}

int main()
{
	//Test_string1();
	//test_string1();
	//test_string2();
	//test_string3();
	//test_string4();
	//test_string6();
	//test_string7();
	//test_string8();
	//test_string9();
	return 0;
}

2.4【模拟实现中的问题】

1.【拷贝构造】

下面是老生常谈的问题了，也就是在调用拷贝构造时会出现的两个指针指向一块空间的情况，这样再调用析构函数时，就会导致同一块空间连续析构两次。

说明：

上述String类没有显式定义其拷贝构造函数与赋值运算符重载，此时编译器会合成默认的，当用s1构造s2时，编译器会调用默认的拷贝构造。最终导致的问题是，s1、s2共用同一块内存空间，在释放时同一块空间被释放多次而引起程序崩溃，这种拷贝方式，称为浅拷贝。

这里可以通过增加一个引用计数来解决，也就是说增加一个变量用来统计某块空间被多少个变量所引用。

2.【写时拷贝】

写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。
引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。

【其他参考资料】：

C++ STL string的Copy-On-Write技术 | 酷 壳 - CoolShell

C++的std::string的“读时也拷贝”技术！ | 酷 壳 - CoolShell

三、【vector】

3.1 【vector的介绍】

【参考资料】：
http://www.cplusplus.com/reference/vector/vector/
1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像静态数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质上讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小需要增加相应的存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，所以存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

3.2【vector的使用】

1.【vector的构造】

代码：

void TestConstructure()
{
	vector<int> a;//无参构造
	vector<int> arr(4, 100);//创建一个大小为4，数组元素为100的数组。
	vector<int> brr(arr.begin(), arr.end());//以arr的始迭代器和arr的末迭代器构造
	vector<int> crr(brr);//用brr拷贝构造crr
}

2.【vector中的迭代器】

begin和end

通过begin函数可以得到容器中第一个元素的正向迭代器，通过end函数可以得到容器中最后一个元素的后一个位置的正向迭代器。

rbegin和rend

通过rbegin函数可以得到容器中最后一个元素的反向迭代器，通过rend函数可以得到容器中第一个元素的前一个位置的反向迭代器。

void TestIterator()
{
		vector<int> arr(10, 0);
	vector<int>::iterator it = arr.begin();
	int i = 1;
	while (it != arr.end())
	{
		*it = i;
		cout << *it << " ";
		i++;
		it++;

	}
	cout << endl;
	int myints[] = { 16,2,77,29 };
	vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));//迭代器构造

	cout << "The reverse_contents of fifth are:" << endl;

	for (vector<int>::reverse_iterator it = fifth.rbegin(); it != fifth.rend(); ++it)
		cout << ' ' << *it;
	cout << '\n';

}

3.【容量操作】

【reserve和resize】:

1、通过reserse函数改变容器的最大容量，resize函数改变容器中的有效元素个数。

2、reserve规则：
 当所给值大于容器当前的capacity时，将capacity扩大到该值。
 当所给值小于容器当前的capacity时，什么也不做。

3、resize规则：
 当所给值大于容器当前的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则默认为0。
 当所给值小于容器当前的size时，将size缩小到该值。

void TestCapacity()
{
	int a[] = { 1,2,3,4,4,55,6,7,8,9,100 };
	int len = sizeof(a) / sizeof(int);
	vector<int> arr(a, a+len);
	cout << " arr的大小为：" << arr.size()<<endl;
	for (int i=0;i<arr.size();i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
// 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
// 注意：resize在增多元素个数时可能会扩容
	arr.resize(2 * len, 0);
	cout << " arr的大小为：" << arr.size()<<endl;
	for (auto ch : arr)
	{
		cout << ch << " ";
	}
	cout << endl;
	arr.resize(100);
	cout << " arr的大小为：" << arr.size()<<endl;

// 往vecotr中插入元素时，如果大概已经知道要存放多少个元素
// 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低
	vector<int> v;
	size_t sz = v.capacity();
	cout <<"容量为：" << v.capacity() << endl;
	v.reserve(100);// 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "容量为：" << v.capacity() << endl;
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())//相等就代表扩容，打印新的容量
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

//v.reserve(100);  // size = 0    capacity 100
//v.resize(100);     // size = 100  capacity 100

需要注意的是size和capacity的变化：

void TestChange()
{
	vector<int> v;
	cout << "v的大小为：" << v.size() << endl;
	// set some initial content:
	for (int i = 1; i < 10; i++)
		v.push_back(i);

	v.resize(5);
	cout << "v的大小为：" << v.size() << endl;
	v.resize(8, 100);
	cout << "v的大小为：" << v.size() << endl;
	v.resize(12);
	cout << "v的大小为：" << v.size() << endl;
	cout << "v contains:";
	for (size_t i = 0; i < v.size(); i++)
		cout << ' ' << v[i];
	cout << '\n';


	size_t sz;
	vector<int> V;
	sz = V.capacity();
	cout << "making V grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		V.push_back(i);
		if (sz != V.capacity())
		{
			sz = V.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

【注意点】：

1、capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
2、reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
3、resize在开空间的同时还会进行初始化，影响size。

4、reserve和resize：通过reserse函数改变容器的最大容量，resize函数改变容器中的有效元素个数。

5、reserve规则：
 当所给值大于容器当前的capacity时，将capacity扩大到该值。
 当所给值小于容器当前的capacity时，什么也不做。

6、resize规则：
 当所给值大于容器当前的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则默认为0。
 当所给值小于容器当前的size时，将size缩小到该值。

4.【增删查改】

void Add_Delete_Find_Modify()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(5);
	v.push_back(6);
	v.push_back(7);
	v.push_back(8);
	v.push_back(9);
	v.push_back(10);
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;
	auto it = v.begin();
	cout << "正向打印：";
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// vector<int>::reverse_iterator rit = v.rbegin();
	auto rit = v.rbegin();
	cout << "反向打印：";
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	// 在指定位置前插入值为val的元素，比如：8之前插入1000,如果没有则不插入
	// 1. 先使用find查找8所在位置
	// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
	it = find(v.begin(), v.end(), 8);
	v.insert(it, 1000);
	for (auto ch : v)
	{
		cout << ch<<" ";
	}
	cout << endl;
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;
	it = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据
	v.erase(it);
	for (auto ch : v)
	{
		cout << ch<<" ";
	}
	cout << endl;
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;
	// operator[]+index 和 C++11中vector的新式for+auto的遍历
    // vector使用这两种遍历方式是比较便捷的。
	v[0] = 10;
	cout << v[0] << endl;
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;
	// 1. 使用for+[]小标方式遍历


	vector<int> swapv;
	swapv.swap(v);
	cout << "交换后：" << endl;
	cout << "v data:";
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
	cout << "swapv data:";
	for (size_t i = 0; i < swapv.size(); ++i)
		cout << swapv[i] << " ";
	cout << endl;
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;


	cout << "再次交换后：" << endl;
	v.swap(swapv);
	cout << "v data:";
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
	cout << "swapv data:";
	for (size_t i = 0; i < swapv.size(); ++i)
		cout << swapv[i] << " ";
	cout << endl;
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;
	v.clear();
	cout << "clear后的数据："<<endl;
	for (auto ch : v)
	{
		cout << ch<<" ";
	}
	cout << endl;
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;
	v.shrink_to_fit();
	cout << "shrink_to_fit后："<<endl;
	cout << "v的大小为：" << v.size() << endl;
	cout << "v的容量为：" << v.capacity() << endl;

}

find函数：
1、find函数共三个参数，前两个参数确定一个迭代器区间（左闭右开），第三个参数确定所要寻找的值。
2、find函数在所给迭代器区间寻找第一个匹配的元素，并返回它的迭代器，若未找到，则返回所给的第二个参数。

3、find函数是在算法模块（algorithm）当中实现的，不是vector的成员函数。

3.3【vector的模拟实现】

这里放一篇参考博客：

C++STL详解（四）—— vector的模拟实现_在不使用编译器的情况下,分析以下代码:将一系列值存入vector<int> ,然后剔除能被2-CSDN博客

实现之前注意vector的存储结构：

【vector.h】

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <assert.h>;
#include <string>
namespace xzc
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;//定义vector的迭代器
		typedef const T* const_iterator;//定义vector的const迭代器
		size_t capacity()const
		{
			return _endofstorage - _start;
		}
		size_t size()const
		{
			return _finish - _start;
		}
		void reserve(size_t n)
		{
			size_t cp = capacity();//这里在使用capacity和size之前最好先用一个变量进行记录，因 
			size_t sz = size();//为一旦发生扩容，_start会发生改变，这样就会导致size算的是一个
			if (n > cp)//随机值
			{
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;
			}
		}
		void resize(size_t n, const T& val = T())
		{
			size_t cp = capacity();
			size_t sz = size();
			if (n <= sz)
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}
		vector()
		{}
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
	    vector(size_t n,const T& val=T())
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
//现代写法的拷贝构造，创建要构造的对象，遍历要拷贝对象的值，追加到要构造对象里
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (auto& e : v)
			{
				push_back(e);
			}
		}
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

		// v1 = v3
//现代写法vector，首先用v3拷贝构造tmp，交换v1和tmp
		vector<T>& operator=(vector<T> tmp)
		{
			swap(tmp);
			return *this;
		}
		~vector()
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}
		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}
		size_t capacity()
		{
			return _endofstorage - _start;
		}
		size_t size()
		{
			return _finish - _start;
		}
		T& operator[](size_t pos)
		{
			assert(pos < size());

			return _start[pos];
		}
		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}
		void insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos < _finish);
			size_t cp = capacity();
			size_t sz = size();
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				reserve((cp == 0) ? 4 : 2 * cp);
				pos = _start + len;
			}//插入之前检查是否需要扩容
			iterator end = _finish - 1;
			while (end >= pos)//将pos之后的数据向后挪动，并在pos处放x
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			_finish++;
		}
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it < _finish)//将pos之后的数据移动覆盖pos位置的数据
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;
			return pos;//为了防止迭代器失效，删除后返回pos之后的数据
		}
		void push_back(const T& x)
		{
			if (_finish == _endofstorage)
			{
				reserve((capacity() == 0) ? 4 : 2 * capacity());
				
			}//容量满了就扩容，并在尾部插入x
			*_finish = x;
			_finish++;
		}
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;
	};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include "vector.h"
void test_vector1()
{
	xzc::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;

	xzc::vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		*it *= 10;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector2()
{
	int i = 0;
	int j(1);
	int k = int(2);

	xzc::vector<int*> v1;
	v1.resize(10);

	xzc::vector<string> v2;
	//v2.resize(10, string("xxx"));
	v2.resize(10, "xxx");

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector3()
{
	xzc::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	v.push_back(7);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	xzc::vector<int>::iterator it = v.begin() + 2;
	v.insert(it, 30);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	//v.insert(v.begin(), 30);
	v.insert(v.begin() + 3, 30);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector4()
{
	xzc::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	v.push_back(7);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	auto pos = v.begin();
	v.erase(pos);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.erase(v.begin() + 3);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector5()
{
	//std::vector<int> v;
	xzc::vector<int> v;

	v.push_back(1);
	v.push_back(2);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.erase(it);
		}
		else
		{
			++it;
		}
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
void test_vector6()
{
	xzc::vector<string> v;
	v.push_back("111111111111111111111");
	v.push_back("111111111111111111111");
	v.push_back("111111111111111111111");
	v.push_back("111111111111111111111");
	v.push_back("111111111111111111111");


	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}


void test_vector7()
{
	xzc::vector<int> v1;
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);

	xzc::vector<int> v2(v1);

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;

	xzc::vector<int> v3;
	v3.push_back(10);
	v3.push_back(20);
	v3.push_back(30);
	v3.push_back(40);

	v1 = v3;

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector8()
{
	//vector<int> v0(10, 0);
	xzc::vector<string> v1(10, "xxxx");

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	xzc::vector<int> v2;
	v2.push_back(10);
	v2.push_back(20);
	v2.push_back(30);
	v2.push_back(40);

	xzc::vector<int> v3(v2.begin(), v2.end());

	string str("hello world");
	xzc::vector<char> v4(str.begin(), str.end());
	for (auto e : v3)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : v4)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{
	//test_vector8();
	//test_vector7();
	//test_vector6();
	//test_vector5();
	//test_vector4();
	//test_vector3();
	//test_vector2();
	//test_vector1();
	return 0;
}

3.4【实现中遇到的问题】：

1、【vector迭代器失效】

迭代器的主要作用就是让我们在使用各个容器时不用关心其底层的数据结构，并让我们能够遍历到每个数据而vector的迭代器在底层实际上就是一个指针。迭代器失效就是指迭代器底层对应指针所指向的空间被销毁了，而指向的是一块已经被释放的空间，如果继续使用已经失效的迭代器，程序可能会崩溃。

【示例1】：

void Test_Vector()
{

	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	//v: 1 2 3 4 5
	vector<int>::iterator pos = find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器
	v.insert(pos, 10); //在值为2的元素的位置插入10
	//v: 1 10 2 3 4 5
	v.erase(pos); //删除元素2 ？？？error（迭代器失效）
	//v: 1 2 3 4 5

}
/*/在该代码中，我们本意是使用元素2的迭代器在原序列中2的位置插入一个10，然后将2删除，但我们实际上获取的是指向2的指针，当我们在2的位置插入10后，该指针就指向了10，所以我们之后删除的实际上是10，而不是2。*/

【示例2删除偶数】：

void Test_Vector()
{

	vector<int> v;
	for (size_t i = 1; i <= 6; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0) //删除容器当中的全部偶数
		{
			v.erase(it);
		}
		it++;
	}
	
}

该代码看上去实际上并没有什么错误，但如果你画图仔细分析，你就会发现该代码的问题所在：

1.当it遍历到偶数时，调用erase,但是erase是将pos之后的数据向前挪动覆盖，就会导致pos位置后一个位置的数据没有被判断。

2.迭代器访问到了不属于容器的内存空间，导致程序崩溃。

因此在设计erase时直接返回pos位置的后一个数据的迭代器，从而避免迭代器失效的问题

那么对应就要改成：
 

void Test_Vector()
{

	vector<int> v;
	for (size_t i = 1; i <= 6; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0) //删除容器当中的全部偶数
		{
			it = v.erase(it); //删除后获取下一个元素的迭代器
		}
		else
		{
			it++; //是奇数则it++
		}
	}
}

当元素被删除后继续判断该位置的元素（因为该位置的元素已经更新，需要再次判断）。

2、【不使用memcpy的原因】

在关于容量的接口中：reserve中当需要进行扩容时必然会涉及数据的拷贝，那么为什么我们不使用memcpy呢？

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

比如对于以下代码如果采用memcpy进行拷贝：

int main()
{
bite::vector<bite::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}

结论： 如果vector当中存储的元素类型是内置类型（int）或浅拷贝的自定义类型（Date），使用memcpy函数进行进行拷贝构造是没问题的，但如果vector当中存储的元素类型是深拷贝的自定义类型（string），则使用memcpy函数将不能达到我们想要的效果。

3.【动态二维数组理解】

先放一道题目：. - 力扣（LeetCode）

解答：

class Solution {
public:
    vector<vector<int>> generate(int numRows) 
    {
        vector<vector<int>> vv;//定义二维vector,vv,外部vector中的数据是vector该vector中存放数 
                               //据为int
        vv.resize(numRows);//先确定行数
        for(int i=0;i<vv.size();i++)//在确定列数注意每行列数不同，并且每行的第一列和最后一列存放 
                                    //1其余都放0
        {
            vv[i].resize(i+1,0);
            vv[i][0]=vv[i][vv[i].size()-1]=1;
        }
        for(int i=0;i<vv.size();i++)
        {
            for(int j=0;j<vv[i].size();j++)
            {
                if(vv[i][j]==0)
                {
                    vv[i][j]=vv[i-1][j]+vv[i-1][j-1];//将为0的元素，改为上层两数之和
                }
            }
        }
        return vv;

    }
};

在vector中构造动态二维数组：

构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素，如果n为5时如下所示。

vv中元素填充完成之后，如下图所示：

四、【list】

4.1【list的介绍】

【参考资料】：

http://www.cplusplus.com/reference/list/list/?kw=list
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

4.2 【list的使用】

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.【 list的构造】

例子：
 

void Init_list()
{
	// list迭代器的使用
    // 注意：遍历链表只能用迭代器和范围for
	int arr[] = { 1,2,3,4,5 };
	list<int> l1; // 构造空的l1
	list<int> l2(5, 10);// l2中放5个值为10的元素
	list<int> l3(l2);//l2拷贝构造l3
	list<int> l4(arr, arr + sizeof(arr)/sizeof(int));//以数组为迭代器区间构造l4
	list<int> l5(l2.begin(), l2.end());// 用l2的[begin(), end()）左闭右开的区间构造l3
	list<int> l6{ 1,2,3,4,5 };// 列表格式初始化C++11
	list<int> l7 = { 1,2,3,4 };//隐式类型转换+赋值重载
	cout << "l1:" << endl;
	for (auto lt : l1)
	{
		cout << lt;
	}
	cout << endl;

	cout << "l2:" << endl;
	for (auto lt : l2)
	{
		cout << lt<<" ";
	}
	cout << endl;

	cout << "l3:" << endl;
	for (auto lt : l3)
	{
		cout << lt<<" ";
	}
	cout << endl;

	cout << "l4:" << endl;
	for (auto lt : l4)
	{
		cout << lt<<" ";
	}
	cout << endl;

	cout << "l5:" << endl;
	for (auto lt : l5)
	{
		cout << "l5:" << lt<<" ";
	}
	cout << endl;

	cout << "l6:" << endl;
	for (auto lt : l6)
	{
		cout << lt<<" ";
	}
	cout << endl;

	cout << "l7:" << endl;
	for (auto lt : l7)
	{
		cout << lt << " ";
	}
	cout << endl;
}

2.【list 迭代器的使用】

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

例子：

void PrintList(const list<int>& lt)
{
	// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
	//同const 指针，const迭代器本质上是不想让迭代器指向的元素被修改，而迭代器本身可以修改
	for (list<int>::const_iterator it = lt.begin(); it != lt.end(); ++it)
	{
		cout << *it << " ";
		//*it = 10;// 编译不通过
		it++;
	}

	cout << endl;
}

void list_iterator()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> lt(arr, arr + sizeof(arr) / sizeof(int));
	list<int>::iterator it = lt.begin();
	cout << "正向" << endl;
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;//这里由于链表并不能直接支持++，所以这里的++本质上是运算符重载
	}
	cout << endl;
	auto rit = lt.rbegin();
	cout << "反向" << endl;
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;


}

【注意】
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

3.【容量操作】

resize

void Test_List()
{
	list<int> lt(5, 3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //3 3 3 3 3
	lt.resize(7, 6); //将size扩大为7，扩大的值为6
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //3 3 3 3 3 6 6
	lt.resize(2); //将size缩小为2
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //3 3
	
}

resize的两种情况：

1. 当所给值大于当前的size时，将size扩大到该值，扩大的数据为第二个所给值，若未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
2. 当所给值小于当前的size时，将size缩小到该值。 

splice

void Test_List()
{
	list<int> lt1(4, 2);
	list<int> lt2(4, 6);
	lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2 

	list<int> lt3(4, 2);
	list<int> lt4(4, 6);
	lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl; //6 2 2 2 2 

	list<int> lt5(4, 2);
	list<int> lt6(4, 6);
	lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
	for (auto e : lt5)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2
	
}

splice函数用于两个list容器之间的拼接，其有三种拼接方式：

1. 将整个容器拼接到另一个容器的指定迭代器位置。
2. 将容器当中的某一个数据拼接到另一个容器的指定迭代器位置。
3. 将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置。

remove和remove if

bool single_digit(const int& val)
{
	return val < 10;
}
void Test_List()
{
	list<int> lt;
	lt.push_back(10);
	lt.push_back(4);
	lt.push_back(7);
	lt.push_back(18);
	lt.push_back(2);
	lt.push_back(5);
	lt.push_back(9);
	lt.remove(18);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //10 4 7 18 2 5 9
	lt.remove_if(single_digit); //删除容器当中值小于10的元素
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //10 18
	
}

empty和size

void list_capacity()
{
	list<int> l1;
	list<int> l2{1,2,3,4,5};
	if (l1.empty())
	{
		cout << "l1为空" << endl;
	}
	else
	{
		cout << "l1不为空" << endl;
	}
	if (l2.empty())
	{
		cout << "l2为空" << endl;
	}
	else
	{
		cout << "l2不为空" << endl;
	}
	cout << "l1的size：" << l1.size() << endl;
	cout << "l2的size：" << l2.size() << endl;

	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;

	// set some initial values:
	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);      // mylist1: 1 2 3 4

	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30

	it = mylist1.begin();
	++it;// mylist1中的it points to 2
	cout << "mylist1" << endl;
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "mylist2" << endl;
	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;

	//mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
								  // mylist2 (empty)
								  // "it" still points to 2 (the 5th element)

	//mylist1.splice(it, mylist2, ++mylist2.begin()); // mylist1: 1 20 2 3 4

	// 10:20
	mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end()); // mylist1: 1 20 30 2 3 4
	cout << "splice后的mylist1和mylist2" << endl;
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;

}

unique

unique函数用于删除容器当中连续的重复元素。

void Test_List()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 3 3 2 2 3
	lt.sort(); //将容器当中的元素排为升序
	lt.unique(); //删除容器当中连续的重复元素
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 2 3 4
}

	

注意： 若想使用unique函数做到真正的去重，还需在去重前对容器内元素进行排序。

assign

void Test_List()
{
	list<char> lt(3, 'a');
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.assign(3, 'b'); //将新内容分配给容器，替换其当前内容
	for (auto e : lt)
	{
		cout << e << " ";
	}

	cout << endl; //b b b
	string s("hello world");
	lt.assign(s.begin(), s.end()); //将新内容分配给容器，替换其当前内容
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //h e l l o   w o r l d
	
}

assign函数用于将新内容分配给容器，替换其当前内容，新内容的赋予方式有两种：

1. 将n个值为val的数据分配给容器。
2. 将所给迭代器区间当中的内容分配给容器。

4 .【list 的头和尾】

void list_front_back()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(5);
	lt.push_back(3);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "lt的头和尾分别为：" << endl;
	cout << lt.front() << endl;
	cout << lt.back() << endl;
	lt.sort();
	cout << "lt排序后：" << endl;
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.unique();
	cout << " lt去重后：" << endl;
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.remove(3);
	cout << "lt去除3后：" << endl;
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	//注意在使用去重之前要先进行排序
}

5. 【增删查改】

void list_add_delete_find_modify()
{
	int arr[] = { 1, 2, 3 };
	list<int> L(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << "L中的值：" << endl;
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;
	// 在list的尾部插入4，头部插入0
	L.push_back(4);
	L.push_front(0);
	cout << "插入4，0后：" << endl;
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;

	// 删除list尾部节点和头部节点
	L.pop_back();
	L.pop_front();
	cout << "头删和尾删后：" << endl;
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;
	//获取链表中第二个节点
	auto pos = ++L.begin();
	cout << "打印当前list的第二个节点的值："<<endl;
	cout << *pos << endl;

	// 在pos前插入值为4的元素
	L.insert(pos, 4);
	cout << "pos之前插入4以后：" << endl;
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;

	// 在pos前插入5个值为10的元素
	cout << "pos前插入5个10：" << endl;
	L.insert(pos, 5, 10);
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;

	// 在pos前插入[v.begin(), v.end)区间中的元素
	vector<int> v{ 7, 8, 9 };
	cout << "pos前插入[v.begin(), v.end()]区间中的元素：" << endl;
	L.insert(pos, v.begin(), v.end());
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;

	// 删除pos位置上的元素
	cout << "打印pos节点的值：" << endl;
	cout << *pos << endl;
	L.erase(pos);
	cout << "删除pos以后的位置" << endl;
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;

	// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
	L.erase(L.begin(), L.end());
	cout << "删除list中的值后：" << endl;
	for (auto lt : L)
	{
		cout << lt << " ";
	}
	cout << endl;



	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	cout << "打印l1：" << endl;
	for (auto lt : l1)
	{
		cout << lt << " ";
	}
	cout << endl;

	// 交换l1和l2中的元素
	list<int> l2;
	cout << "交换前l1和l2：" << endl;
	for (auto lt : l1)
	{
		cout << lt << " ";
	}
	cout << endl;
	for (auto lt : l2)
	{
		cout << lt << " ";
	}
	cout << endl;

	l1.swap(l2);
	cout << "交换后的l1和l2：" << endl;
	for (auto lt : l1)
	{
		cout << lt << " ";
	}
	cout << endl;
	for (auto lt : l2)
	{
		cout << lt << " ";
	}
	cout << endl;

	// 将l2中的元素清空
	l2.clear();
	cout << "l2中的元素清空后：" << endl;
	for (auto lt : l2)
	{
		cout << lt << " ";
	}
	cout << endl;
	cout << "l2的size：" << endl;
	cout << l2.size() << endl;
}

4.3【list的实现】

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。

1.【list的组成】

list主要分为3个部分：

1.节点：各节点的数据包括，数据，下一个节点的坐标，上一个节点的坐标

2.迭代器：用来遍历各个节点实现遍历简单化主要分为正向迭代器和反向迭代器，每种迭代器又分为两种const和非const

3.list主体：主要包括一个头结点和list的节点长度。

2.【list的迭代器】

【实现目的】

这里需要实现一个迭代器类，来遍历链表。具体形式如下

之前模拟实现string和vector时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？

因为string和vector对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。

但是对于list来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。

而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。

既然list的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。例如，当你使用list当中的迭代器进行自增操作时，实际上执行了p = p->next语句，只是你不知道而已。

总结： list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）

【迭代器分类】

而在性质上分为：

不难发现，随机迭代器是一种特殊的双向迭代器，双向迭代器是一种特殊的单向迭代器，不同种类的迭代器具有的功能不相同。

【反向迭代器】

反向迭代器就是正向迭代器的反向，它的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

以下是list反向迭代器的实现：

	template<class Iterator>
	class ReverseListIterator
	{
		// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
		// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
		// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;
	public:
		//
		// 构造
		ReverseListIterator(Iterator it) : _it(it) {}
		//
		// 具有指针类似行为
		Ref operator*() {
			Iterator temp(_it);
			--temp;
			return *temp;
		}
		Ptr operator->() { return &(operator*()); }
		//
		// 迭代器支持移动
		Self& operator++() 
		{
			--_it;
			return *this;
		}
		Self operator++(int) {
			Self temp(*this);
			--_it;
			return temp;
		}
		Self& operator--() {
			++_it;
			return *this;
		}
		Self operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}
		//
		// 迭代器支持比较
		bool operator!=(const Self& l)const { return _it != l._it; }
		bool operator==(const Self& l)const { return _it != l._it; }
		Iterator _it;
	};

3.【list的实现代码部分】

List.h:

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <iostream>
using namespace std;
namespace xzc
{
	template <class T>
	struct List_Node
	{
		List_Node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
		T _data;
		List_Node<T>* _prev;
		List_Node<T>* _next;
	};//List中的各个节点



//迭代器实现方式1
//下面是List的迭代器，它通过设计3个模板参数，能够实现普通迭代器和const迭代器两种不同的迭代器类
//由于const_iterator和iterator是两种不同的类，需要实现两种不同的模板类，但是通过下面的3个参数
//T(迭代器指向的数据类型),Ref(迭代器指向的数据引用),Ptr(迭代器指向的数据地址),能同时实现这两个
//不同的迭代器类。
	//template<class T, class Ref, class Ptr>
	//struct List_Iterator
	//{
	//	typedef List_Node<T> Node;
	//	typedef List_Iterator<T, Ref, Ptr> self;
	//	List_Iterator(Node* node)
	//		:_nodeptr(node)
	//	{}
	//	self& operator++()
	//	{
	//		_nodeptr = _nodeptr->_next;
	//		return *this;
	//	}

	//	self& operator--()
	//	{
	//		_nodeptr = _nodeptr->_prev;
	//		return *this;
	//	}

	//	self operator++(int)
	//	{
	//		self tmp(*this);
	//		_nodeptr = _nodeptr->_next;

	//		return tmp;
	//	}

	//	self operator--(int)
	//	{
	//		self tmp(*this);
	//		_nodeptr = _nodeptr->_prev;

	//		return tmp;
	//	}

	//	Ref operator*()
	//	{
	//		return _nodeptr->_data;
	//	}

	//	Ptr operator->()
	//	{
	//		return &_nodeptr->_data;
	//	}
	//	bool operator !=(const self& it )
	//	{
	//		return(this->_nodeptr != it._nodeptr);
	//	}
	//	bool operator ==(const self& it)
	//	{
	//		return (_nodeptr == it._nodeptr);
	//	}
	//	Node* _nodeptr;
	//};





//迭代器实现方式2
//这里是分别写了两个类，来实现List的迭代器下面是iterator
	template<class T>
	struct List_Iterator
	{
		typedef List_Node<T> Node;
		typedef List_Iterator<T> self;
		List_Iterator(Node* node)
			:_nodeptr(node)
		{}

		self& operator++()
		{
			_nodeptr = _nodeptr->_next;
			return *this;
		}

		self& operator--()
		{
			_nodeptr = _nodeptr->_prev;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			_nodeptr = _nodeptr->_next;

			return tmp;
		}

		self operator--(int)
		{
			self tmp(*this);
			_nodeptr = _nodeptr->_prev;

			return tmp;
		}

		T& operator*()
		{
			return _nodeptr->_data;
		}

		T* operator->()
		{
			return &_nodeptr->_data;
		}

		bool operator!=(const self& s)
		{
			return _nodeptr != s._nodeptr;
		}

		bool operator==(const self& s)
		{
			return _nodeptr == s._nodeptr;
		}
		Node* _nodeptr;
	};

//这里是const_iterator
	template<class T>
	struct List_Const_Iterator
	{
		typedef List_Node<T> Node;
		typedef List_Const_Iterator<T> self;
		Node* _nodeptr;

		List_Const_Iterator(Node* node)
			:_nodeptr(node)
		{}

		self& operator++()
		{
			_nodeptr = _nodeptr->_next;
			return *this;
		}

		self& operator--()
		{
			_nodeptr = _nodeptr->_prev;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			_nodeptr = _nodeptr->_next;

			return tmp;
		}

		self operator--(int)
		{
			self tmp(*this);
			_nodeptr = _nodeptr->_prev;

			return tmp;
		}

		// *it = 10
		const T& operator*()
		{
			return _nodeptr->_data;
		}

		// it->a1 = 10
		const T* operator->()
		{
			return &_nodeptr->_data;
		}

		bool operator!=(const self& s)
		{
			return _nodeptr != s._nodeptr;
		}

		bool operator==(const self& s)
		{
			return _nodeptr == s._nodeptr;
		}
	};





//List类的实现

	template<class T>
	class List
	{
		typedef List_Node<T> Node;
	public:
		typedef List_Iterator<T> iterator;//对不同的迭代器进行重定义这里是实现方式2
		typedef List_Const_Iterator<T> const_iterator;

		//typedef List_Iterator<T, T&, T*> iterator;这里是实现方式1
		//typedef List_Iterator<T, const T&, const T*> const_iterator;
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}//当List为空时，由于结构为带头双向循环，可以使用空初始化对其进行空初始化。

		List()//构造函数调用空初始化
		{
			empty_init();
		}

		List(const List<T>& lt)//拷贝构造现代写法
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}


		
		void swap(List<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		// lt3 = lt1
		List<int>& operator=(List<int> lt)//赋值重载现代写法
		{
			swap(lt);

			return *this;
		}

		size_t size()
		{
			return _size;
		}


		iterator begin()
		{
			//return iterator(_head->_next);//这里需要返回一个迭代器类型
			return _head->_next;//不写iterator的原因是，能够进行隐式类型转换。
		}

		iterator end()
		{
			//return iterator(_head->_next);
			return _head;
		}


		const_iterator begin()const
		{
			return _head->_next;
		}


		const_iterator end() const
		{
			return _head;
		}


		iterator insert(iterator pos, const T& x)
		{//链表的插入逻辑定义新节点，找到插入的位置，进行节点之间的连接
			Node* cur = pos._nodeptr;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
			return iterator(newnode);

		}

		iterator erase(iterator pos)
		{//链表的删除逻辑，找到要删除的位置，释放对应节点，将其前后节点进行连接

			Node* cur = pos._nodeptr;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			cur = nullptr;
			--_size;
			return iterator(next);//为了方便遍历返回删除结点的后一个节点
		}


		void clear()
		{//释放全部节点
			iterator it = begin();
			while (it != end())
			{
				it=erase(it);
			}

		}


		~ List()
		{
			clear();
			delete _head;
			_head = nullptr;
			_size = 0;
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}

	private:
		Node* _head;
		int _size;

	};
	

//const迭代器遍历不能直接定义const迭代器进行遍历，由于类型匹配的原则，普通List对象调用begin调的
//是普通的begin，要么const的begin不和普通的begin重名，要么采用下面的方式遍历
	/*template<typename Container>
	void print_container(const Container& con)
	{
		typename Container::const_iterator it = con.begin();
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，而不是静态成员变
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
		while (it != con.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}*/

}

Test.cpp:

#define _CRT_SECURE_NO_WARNINGS
#include "list.h"
#include<iostream>
#include<list>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


//void test_list4()
//{
//	list<int> lt;
//	lt.push_back(1);
//	lt.push_back(2);
//	lt.push_back(3);
//	lt.push_back(4);
//	lt.push_back(5);
//	//print_list(lt);
//	xzc::print_container(lt);
//
//	list<string> lt1;
//	lt1.push_back("1111111111111");
//	lt1.push_back("1111111111111");
//	lt1.push_back("1111111111111");
//	lt1.push_back("1111111111111");
//	lt1.push_back("1111111111111");
//	//print_list(lt1);
//	xzc::print_container(lt1);
//
//	vector<string> v;
//	v.push_back("222222222222222222222");
//	v.push_back("222222222222222222222");
//	v.push_back("222222222222222222222");
//	v.push_back("222222222222222222222");
//	//print_list(v);
//	xzc::print_container(v);
//}


struct AA
{
	AA(int a1 = 0, int a2 = 0)
		:_a1(a1)
		, _a2(a2)
	{}

	int _a1;
	int _a2;
};

void test_list3()
{
	xzc::List<AA> lt;
	lt.push_back(AA(1, 1));
	lt.push_back(AA(2, 2));
	lt.push_back(AA(3, 3));

    xzc:: List<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//cout << (*it)._a1<<" "<<(*it)._a2 << endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;


		++it;
	}
	cout << endl;

	int* p = new int;
	*p = 1;

	AA* ptr = new AA;
	ptr->_a1 = 1;

}
void test_list2()
{
	xzc::List<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	xzc::List<int> lt1(lt);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	xzc::List<int> lt2;
	lt2.push_back(10);
	lt2.push_back(200);
	lt2.push_back(30);
	lt2.push_back(40);
	lt2.push_back(50);

	lt1 = lt2;
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
}


void test1()
{
	xzc::List<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	// 封装屏蔽底层差异和实现细节
	// 提供统一的访问修改遍历方式
	xzc::List<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		*it += 20;
		cout << *it << " ";
		it++;
	}
	cout << endl;

}





int main()
{
	test_list3();
	//test_list2();
	//test1();
	//test_list4();

	return 0;
}

4.4.【实现中遇到的问题】

【list的迭代器失效】

前面说过，大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
		//其赋值
		l.erase(it);
		++it;
	}
}
// 改正
void TestListIterator()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

其他还有迭代器相关问题，在后面其他容器中再说明。

4.5【list与vector的对比】

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

五、【stack和queue】

5.1【stack】

5.1.1【stack的介绍】

与数据结构中的栈和队列相同。

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

5.1.2【stack的使用】

void Test_stack()
{
	stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);
	s.push(5);
	cout << "未弹出之前栈的大小为：" << s.size()<<endl;
	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
	cout << "弹出后栈的大小为：" << s.size()<<endl;

}

5.1.3【stack的模拟实现】

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <deque>
namespace xzc
{
	template<class T, class Container = deque<T>>
	class Stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

5.2【queue】

5.2.1【queue的介绍】

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

5.2.2【queue的使用】

void Test_queue()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);
	cout << "未弹出之前队列的大小为：" << q.size() << endl;
	while (!q.empty())
	{
		cout << q.back() << endl;
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
	cout << "弹出后队列的大小为：" << q.size() << endl;


}

5.2.3【queue的模拟实现】

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <deque>
namespace xzc
{
	template<class T, class Container = deque<T>>
	class Queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		const T& front()
		{
			return _con.front();
		}
		const T& back()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

5.3【deque的简单说明】

我们可以发现在stack和queue实现的过程中，模板参数容器部分有一个缺省参数deque。

那么什么是deque呢？下面让我们简单的了解一下。

5.3.1【deque的介绍】

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和 删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂。

如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

5.3.2 【deque的缺陷】

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

5.3.3【选择deque作为底层默认容器的原因】

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器。

主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

总结：

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque：

5.4【优先级队列】

5.4.1【priority_queue的介绍】

本质上优先级队列体现的是堆的思想

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素

pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

5.4.2【priority_queue的使用】

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用优先级队列（priority_queue）。

注意：
默认情况下priority_queue是大堆。

void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;
	// 如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
}
void Test_priority_queue()
{
	priority_queue<int> pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	

}

priority_queue的本质是堆，而默认情况下为大堆。可加入greater<int>类型参数进行修改使其变为小堆。

5.4.3【priority_queue的模拟实现】

参考资料：

STL详解（九）—— priority_queue的使用与模拟实现_priority_queue vector-CSDN博客

1.【priority_queue.h】

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <stdbool.h>
namespace xzc
{
	template<class T>
	class Less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T,class Compare=Less<T>,class Container = vector<T> >
	class priority_queue
	{
	public:
		priority_queue()
		{

		}
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator end)
			:_con(first,end)
		{
			for (size_t i=(_con.size() - 2) / 2; i >= 0; --i)
			{
				AdjustDown(i);
			}
		}
		void AdjustUp(size_t child)
		{
		    Compare compare;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if(compare(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}


				/*if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child-1) / 2 ;
				}*/


				else
				{
					break;
				}
			}
		}
		void AdjustDown(size_t parent)
		{
			Compare compare;
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				{
					child++;
				}


				if (compare(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}


				/*if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}*/


				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size()-1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

2.【Test.c】

#include "priority_queue.h"
class Date
{
public:

	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d);
private:
	int _year;
	int _month;
	int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}


template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};


template<class T>
class Less<T*>//模板特化，当参与比较的是指针指向的对象时，将指针转换为对应对象进行比较
{
public:
	bool operator()(T* x, T* y)
	{
		return *x < *y;
	}
};
void test_priority_queue()
{
	//内置类型
	xzc::priority_queue<int, vector<int>, Less<int>> pq; // 大堆

	//xzc::priority_queue<int,vector<int>,Greater<int>> pq; // 小堆
	pq.push(3);
	pq.push(1);
	pq.push(5);
	pq.push(4);
	pq.push(2);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	//自定义类型
	// 大堆，需要用户在自定义类型中提供<的重载
	xzc::priority_queue<Date> q1;
	q1.push(Date(2018, 10, 29));
	q1.push(Date(2018, 10, 28));
	q1.push(Date(2018, 10, 30));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	xzc::priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2018, 10, 29));
	q2.push(Date(2018, 10, 28));
	q2.push(Date(2018, 10, 30));
	cout << q2.top() << endl;
	//当为指针指向的自定义类型时，由于指针为内置类型，所以要使用模板特化来解决
	xzc::priority_queue<Date*, vector<Date*>,Less<Date*>> q3;
	q3.push(new Date(2018, 10, 29));
	q3.push(new Date(2018, 10, 28));
	q3.push(new Date(2018, 10, 30));
	cout << *(q3.top()) << endl;
}
int main()
{
	test_priority_queue();
	return 0;
}

5.5【容器适配器】

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

六、【map和set】

6.1【关联式容器和序列式容器】

在前面，我们已经接触过STL中的部分容器，比如：

1，序列式容器：vector、list、dequeforward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

那什么是关联式容器？它与序列式容器有什么区别？

2、关联式容器：关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。而我们该模块需要进行了解的map，set，multimap，multiset，都被称为关联式容器。

1、【树形结构和哈希结构】

根据应用场景的不同，C++STL总共实现了两种不同结构的关联式容器：树型结构和哈希结构。

其中，树型结构容器中的元素是一个有序的序列，而哈希结构容器中的元素是一个无序的序列。

2、【键值对】

用来表示数据之间具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

比如：我们现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即我们应该可以通过该英文单词，在词典中找到与其对应的中文含义。二叉搜索树中的KV模型就体现了键值对。

SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
    //first_type和second_type分别充当key和value
	T1 first;
	T2 second;
	pair() //无参构造
		: first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b)//带参构造
		: first(a), second(b)
	{}
};

6.2【set】

6.2.1【set的介绍】

1. set是按照一定次序存储元素的容器，使用set的迭代器遍历set中的元素，可以得到有序序列，说明底层使用中序遍历。

2. 在set中，存储元素的value都是唯一的，不可以重复，因此可以使用set进行去重，并且set中的元素不能在容器中修改(元素总是const)，这是因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。但是可以从容器中插入或删除它们。

3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。当不传入内部比较对象时，set中的元素默认按照小于来比较。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但set容器允许根据顺序对元素进行直接迭代。

5. set在底层是用平衡搜索树（红黑树）实现的，所以在set当中查找某个元素的时间复杂度为logN。

6.与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对，因此在set容器中插入元素时，只需要插入value即可，不需要构造键值对。

6.2.2【set的使用】

1.【set的构造】

方式一： 构造一个某类型的空容器。

set<int> s1;//构造int类型的空容器

方式二： 拷贝构造某类型set容器。

set<int> s2(s1);//用s1拷贝构造s2

方式三： 使用迭代器拷贝构造某一段内容。

string str("love you");
set <char> s3(str.begin(), str.end());//构造string对象某段,迭代器构造

方式四： 构造一个某类型的空容器，比较方式指定为大于。

set<int, greater<int>> s4;//构造int类型的空容器，比较方式指定为大于

2.【迭代器的使用】

void Test_set()
{
	//构造并初始化
	set<int> s{ 2,5,1,4,8,3 };//构造并初始化
	set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		cout << *sit << " ";
		sit++;
	}
	cout << endl;

	//构造
	set<int> s1;//构造int类型的空容器
	set<int> s2(s1);//用s1拷贝构造s2
	string str("love you");
	set <char> s3(str.begin(), str.end());//构造string对象某段,迭代器构造
	set<int, greater<int>> s4;//构造int类型的空容器，比较方式指定为大于


	//迭代器
	//1、使用迭代器进行遍历
	cout << "正序遍历" << endl;
	set<char>::iterator it = s3.begin();
	while (it != s3.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << "逆序遍历" << endl;
	set<char>::reverse_iterator rit = s3.rbegin();
	while (rit != s3.rend())
	{
		cout << *rit << " ";
		rit++;
	}

}

3.【增删查改】

void Test_set()
{
	//构造
	set<int> s1;//构造int类型的空容器
	set<int> s2(s1);//用s1拷贝构造s2
	string str("love you");
	set <char> s3(str.begin(), str.end());//构造string对象某段,迭代器构造
	set<int, greater<int>> s4;//构造int类型的空容器，比较方式指定为大于

	
	//3、增删查改

	//增
	s1.insert(1);
	s1.insert(1);
	s1.insert(1);
	s1.insert(4);
	s1.insert(4);
	s1.insert(2);
	s1.insert(7);
	s1.insert(3);
	s1.insert(3);
	//insert会返回一个pair<iterator,bool>，当插入成功时会返回真，和插入以后的迭代器
	pair<set<int>::iterator,bool> ret=s1.insert(10);
	cout << "返回的迭代器对应值为：" << *(ret.first) << " " << "是否插入成功" << ret.second << endl;
	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;
	//容器中值为2的元素个数
	cout << s1.count(2) << endl; //1
	//容器大小
	cout << s1.size() << endl; //6
	//交换两个容器的数据
	set<int> tmp{ 11, 22, 33, 44 };

	cout << "交换前" << endl;
	cout << "s1:" << endl;
	for (auto e : s1)
	{
		cout << e << " ";

	}
	cout << endl;
	cout << "tmp:" << endl;
	for (auto e : tmp)
	{
		cout << e << " ";
	}
	cout << endl;
	s1.swap(tmp); 
	//交换后

	cout << "交换后" << endl;
	cout << "s1:" << endl;
	for (auto e : s1)
	{
		cout << e << " ";

	}
	cout << endl;
	cout << "tmp:" << endl;
	for (auto e : tmp)
	{
		cout << e << " ";
	}
	cout << endl;

	s1.swap(tmp);

	//删
	cout << "开始删除" << endl;
	s1.erase(7);
	s1.erase(2);
	for (auto e : s1)
	{
		cout << e << " ";
	}
	//s1.erase(100),//当删除的为不存在的值时，就不删除。
	cout << endl;
	set<int>::iterator pos = s1.find(1); //查找值为1的元素,找不到就返回s1.end()
	if (pos != s1.end())
	{
		s1.erase(pos);
	}
	//当查找的值不存在时,会返回s1.end()即最后一个元素的下一个位置的正向迭代器
	//pos = s1.find(100);//由于迭代器左闭右开，因此无法进行访问
	//s1.erase(pos)//如果强行删除就会崩溃
	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;
	//清空容器
	cout << "clear是否成功:" << endl;
	s1.clear();
	//容器判空
	cout << s1.empty() << endl; //1
}

这里插入函数中有一个pair类型需要注意，他是一个自定义类型，具体构成如下：

他是一个可以接受两个不同类型参数的自定义类型。

这里还有两个接口需要关注：

void Test_set()
{
	set<int> myset;
	set<int>::iterator itlow, itup;

	for (int i = 1; i < 10; i++)
	{
		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
	}
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
	//itlow = myset.lower_bound(30);              //
	itlow = myset.lower_bound(25);                // >= 25值位置的iterator即30位置
	itup = myset.upper_bound(70);                 // >  70值位置的iterator即80位置
	//打印[itlow,itup]
	cout << "[itlow,itup]" << endl;
	set<int>::iterator it = itlow;
	while (it != itup)
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	// 删除[itlow,itup]
	cout << "删除[itlow,itup]区间以后" << endl;
	myset.erase(itlow, itup);                     // 10 20 70 80 90

	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
}

6.2.3.【multiset】

1.【multiset的介绍】

multiset容器与set容器的底层实现一样，都是平衡搜索树（红黑树），其次，multiset容器和set容器所提供的成员函数的接口都是基本一致的，这里就不再列举了，multiset容器和set容器的唯一区别就是，multiset允许键值冗余，即multiset容器当中存储的元素是可以重复的。

2.【multiset的使用】

只需要关注一个：

void Test_multiset()
{
	// 排序
	multiset<int> s;
	s.insert(5);
	s.insert(2);
	s.insert(6);
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(2);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	multiset<int>::iterator it = s.begin();
	// 如果有多个值，find返回中序第一个val的迭代器
	it = s.find(2);
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;


	// [>=val, >val]
	cout << "[first,second]" << endl;
	auto ret = s.equal_range(2);
	it = ret.first;
	while(it!= ret.second)
	{
		cout << *(it) << " ";
		it++;
	}
	cout << endl;
	cout << "删除[first,second]以后" << endl;
	s.erase(ret.first, ret.second);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "1被删除的个数" << endl;
	size_t n = s.erase(1);//返回被删除的个数
	cout << n << endl;
	cout << "删除后的s:" << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

6.3【map】

6.3.1【map的介绍】

1、map是关联式容器，它按照特定的次序（按照key来比较）存储键值key和值value组成的元素，使用map的迭代器遍历map中的元素，可以得到有序序列。

2、在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，并取别名为pair。

3、map容器中元素的键值key不能被修改，但是元素的值value可以被修改，因为map底层的二叉搜索树是根据每个元素的键值key进行构建的，而不是值value。即val可修改，key不可修改。

4、在内部，map中的元素总是按照键值key进行比较排序的。当不传入内部比较对象时，map中元素的键值key默认按照小于来比较。

5、map容器通过键值key访问单个元素的速度通常比unordered_map容器慢，但map容器允许根据顺序对元素进行直接迭代。

6、map容器支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

7、map在底层是用平衡搜索树（红黑树）实现的，所以在map当中查找某个元素的时间复杂度为logN。

6.3.2【map的使用】

1、【map的构造】

方式一： 指定key和value的类型构造一个空容器。

map<int,string> m;//构造一个key为int类型，value为string类型的空容器

方式二： 拷贝构造某同类型容器的复制品。

map<int, string> m1(m); //用m拷贝构造m1

方式三： 使用迭代器拷贝构造某一段内容。

map<int, string> m3(m1.begin(), m1.end()); //使用迭代器拷贝构造m1容器某段区间的复制品

方式四： 指定key和value的类型构造一个空容器，key比较方式指定为大于。

map<int, string, greater<int>> m3; //构造一个key为int类型，value为double类型的空容器，key比较方 
                                   //式指定为大于

2、【迭代器的使用】

示例：

void Test_map()
{
	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	cout << "初始" << endl;
	for (auto e : m)
	{
		cout << "<key:" <<e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;
	//用正向迭代器进行遍历
	map<int, string>::iterator it = m.begin();
	cout << "正向遍历" << endl;
	while (it != m.end())
	{
		cout << "<key:" << it->first << "," << "val:" << it->second << ">" << " " << endl;
		it++;
	}
	cout << endl; 
	map<int, string>::reverse_iterator rit = m.rbegin();
	cout << "逆向遍历" << endl;
	while (rit != m.rend())
	{
		cout << "<key:" << rit->first << "," << "val:" << rit->second << ">" << " " << endl;
		rit++;
	}
	cout << endl; 
}

注意： 编译器在编译时会自动将范围for替换为迭代器的形式，因此支持了迭代器实际上就支持了范围for。

3、【增删查改】

插入函数

我们可以发现Insert函数的第一个形式是:

pair<iterator,bool> insert (const value_type& val);

其返回值为pair<iterator，bool>，我们已经在set中使用过，但是参数类型为value_type，它实际上也是pair类型：

typedef pair<const Key, T> value_type;

因此，我们向map容器插入元素时，需要用key和value构造一个pair对象，然后再将pair对象作为参数传入insert函数。

因此我们可以像下面那样使用匿名对象进行插入：
 

void Test_map()
{
	map<int, string> m;
	//方式一：调用pair的构造函数，构造一个匿名对象插入
	m.insert(pair<int, string>(2, "one"));
	m.insert(pair<int, string>(1, "two"));
	m.insert(pair<int, string>(3, "three"));
	for (auto e : m)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
}

但是这种方式会使得我们的代码变得很长，尤其是没有直接展开命名空间的情况下，因此我们最常用的是下面的方式：

使用make_pair仿函数来显示构造pair类型，而make_pair函数可以根据传入参数的类型自动隐式进行推导，最终构造并返回一个对应的pair对象。

我们来看一下make_pair函数：
 

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

我们只需向make_pair函数传入key和value，该函数模板会根据传入参数类型进行自动隐式推导，最终构造并返回一个对应的pair对象。

void Test_map()
{
	map<int, string> m;
	//方式二：调用函数模板make_pair，构造对象插入
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	for (auto e : m)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	
}

insert函数的返回值也是一个pair对象，该pair对象中第一个成员的类型是map的迭代器类型，第二个成员的类型的一个bool类型，具体含义如下：

1、若待插入元素的键值key在map当中不存在，则insert函数插入成功，并返回插入后元素的迭代器和true。
2、若待插入元素的键值key在map当中已经存在，则insert函数插入失败，并返回map当中键值为key的元素的迭代器和false。

查找函数

map的查找函数是根据所给key值在map当中进行查找，若找到了，则返回对应元素的迭代器，若未找到，则返回容器中最后一个元素下一个位置的正向迭代器。

void Test_map()
{
	map<int, string> m;
	//方式二：调用函数模板make_pair，构造对象插入
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	map<int, string>::iterator pos = m.find(2);
	if (pos != m.end())
	{
		cout << "<key:" << pos->first << "," << "val:" << pos->second << ">" << " " << endl;
	}
}

删除函数

也就是说，我们既可以根据key值删除指定元素，也可以根据迭代器删除指定元素，若是根据key值进行删除，则返回实际删除的元素个数。

void Test_map()
{
	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	cout << "未删除之前" << endl;
	for (auto e : m)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	//方式一：根据key值进行删除
	m.erase(3);
	//方式二：根据迭代器进行删除
	map<int, string>::iterator pos = m.find(2);
	if (pos != m.end())
	{
		m.erase(pos);
	}
	cout << "删除以后" << endl;
	for (auto e : m)
    {
	   cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
    }
}

map的[ ]运算符重载

map的[ ]运算符重载函数的函数原型如下：

首先我们来看一下operator[ ]的实现方式：

(*((this->insert(make_pair(k, mapped_type()))).first)).second

具体就是下面3个步骤：

1. 调用insert函数插入键值对。
2. 拿出从insert函数获取到的迭代器。
3. 返回该迭代器位置元素的值value。

mapped_type& operator[] (const key_type& k)
{
	//1、调用insert函数插入键值对
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2、拿出从insert函数获取到的迭代器
	iterator it = ret.first;
	//3、返回该迭代器位置元素的值value
	return it->second;
}

void Test_map()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("insert", "插入"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("right", "右边")); 
	cout << "初始的dict" << endl;
	for (auto e : dict)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;
	dict["erase"];  // 插入
	cout << "插入以后，注意待插入节点不存在的时候，插入节点的value为空" << endl;
	for (auto e : dict)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;
	cout << "查找已经存在的" << endl;
	cout << dict["insert"] << endl; // 查找
	cout << "查找不存在的" << endl;
	cout << dict["love"] << endl; // 查找
	cout << "用于分割" << endl;
	cout << "观察不存在的是否插入" << endl;
	for (auto e : dict)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;
	dict["erase"] = "删除"; // 修改
	cout << "修改以后" << endl;
	for (auto e : dict)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;
	dict["test"] = "测试";  // 插入+修改
	cout << "插入+修改" << endl;
	for (auto e : dict)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;

}

总结一下：

1. 如果k不在map中，则先插入键值对<k, V()>，然后返回该键值对中V对象的引用。
2. 如果k已经在map中，则返回键值为k的元素对应的V对象的引用。

其他成员函数

void Test_map()
{
	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	//获取容器中元素的个数
	cout << m.size() << endl; //3
	//容器中key值为2的元素个数
	cout << m.count(2) << endl; //1
	//清空容器
	m.clear();
	//容器判空
	cout << m.empty() << endl; //1
	//交换两个容器中的数据
	map<int, string> tmp;
	m.swap(tmp);
}

6.3.3【multimap】

multimap容器与map容器的底层实现一样，也都是平衡搜索树（红黑树），其次，multimap容器和map容器所提供的成员函数的接口都是基本一致的，这里也就不再列举了，multimap容器和map容器的区别与multiset容器和set容器的区别一样，multimap允许键值冗余，即multimap容器当中存储的元素是可以重复的。

注意：

multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以
重复的。

void Test_multimap()
{
	multimap<int, string> mm;
	//插入元素（允许重复）
	mm.insert(make_pair(2, "two"));
	mm.insert(make_pair(2, "double"));
	mm.insert(make_pair(1, "one"));
	mm.insert(make_pair(3, "three"));
	for (auto e : mm)
	{
		cout << "<" << e.first << "," << e.second << ">" << " ";
	}
	cout << endl; //<1,one> <2,two> <2,double> <3,three>
}

由于multimap容器允许键值冗余，因此两个容器中成员函数find和count的意义也有所不同：

其次，由于multimap容器允许键值冗余，调用[ ]运算符重载函数时，应该返回键值为key的哪一个元素的value的引用存在歧义，因此在multimap容器当中没有实现[ ]运算符重载函数。

6.4【set和map的模拟实现】

1、【问题说明及解决】

我们都知道，set是K模型的容器，而map是KV模型的容器，那我们如何用一棵KV模型的红黑树同时实现map和set呢？

我们可以通过观察STL的源码可以发现，其设置了一个模板参数T用来决定红黑树中存什么，所以这里我们可以通过控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们也将红黑树第二个模板参数的名字改为T。

template<class K, class T>
class RBTree
{}；

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对pair<>。

如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key

template<class K, class V>
class map
{
public:
	//...
private:
	RBTree<K, pair<K, V>> _t;
};

但如果是map容器，那么它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对pair<K,V>：

template<class K, class V>
class map
{
public:
	//...
private:
	RBTree<K, pair<K, V>> _t;
};

而红黑树结点当中存储的数据由于模板参数的改变也会发生一些变化，现在红黑树的模板参数变成了K和T，那么红黑树结点当中存储的应该是什么呢？

前面说到，由于上层容器的不同，底层红黑树当中的K和T也是不同的：

set容器：K和T都代表键值Key。
map容器：K代表键值Key，T代表由Key和Value构成的键值对。

对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。

这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对。

因此对红黑树的节点类定义就要定义为如下形式，从而使得节点中所存的数据是T类型。

代码部分：

enum Color
{
	Red,
	Black
};
template< class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _prev;
	T _data;
	Color _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _prev(nullptr)
		, _data(data)
		, _col(Red)
	{}
};

我们知道当红黑树的节点结构改变了，也会造成一些影响，比如在进行查找逻辑时由于结点当中存储的是T，这个T可能是Key，也可能是<Key, Value>键值对。那么当我们需要进行结点的键值比较时，应该如何获取结点的键值呢，从而进行比较呢？

实际上我们可以通过提供各上层容器的仿函数，通过仿函数来获取各容器所存节点的键值来解决即可，当上层容器是set的时候T就是键值Key，直接用T进行比较即可，但当上层容器是map的时候就不行了，此时我们需要从<Key, Value>键值对当中取出键值Key后，再用Key值进行比较。

因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。

仿函数又叫做函数对象，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

这里我们实现仿函数的目的是使无论RBTree中的T类型实例化成什么类型，我们都能根据其键值进行节点间的大小比较。

看一下map的仿函数：
 

template<class K, class V>
class map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key
		{
			return kv.first;
		}
	};
public:
	//...
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

但是对于底层红黑树来说，它并不知道上层容器是map还是set，因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较。

因此，set容器也需要向底层红黑树传入一个仿函数，虽然这个仿函数单独看起来没什么用，但却是必不可少的。

template<class K>
class set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //返回键值Key
		{
			return key;
		}
	};
public:
	//...
private:
	RBTree<K, K, SetKeyOfT> _t;
};

此时，set容器传入底层红黑树的就是set的仿函数，map容器传入底层红黑树的就是map的仿函数。

这样一来，当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较，下面以红黑树的查找函数为例：

Node* Find(const T& data)
	{
		Node* cur = _root;
		KeyOfT GetKey;
		while (cur)
		{
			if (GetKey(data) < GetKey(cur->_data)) //key值小于该结点的值
			{
				cur = cur->_left; //在该结点的左子树当中查找
			}
			else if (GetKey(data) > GetKey(cur->_data)) //key值大于该结点的值
			{
				cur = cur->_right; //在该结点的右子树当中查找
			}
			else //找到了目标结点
			{
				return cur; //返回该结点
			}
		}
		return nullptr; //查找失败
	}

注意： 所有进行结点键值比较的地方，均需要通过仿函数获取对应结点的键值后再进行键值的比较。

2、【红黑树迭代器的实现】

这里为了支持set和map迭代器的功能需要对红黑树的迭代器进行实现。红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。

//正向迭代器
template<class T, class Ref, class Ptr>
struct RBTree_Iterator
{
	typedef RBTreeNode<T> Node; //节点的类型
	typedef RBTree_Iterator<T, Ref, Ptr> Self; //正向迭代器的类型

	Node* _node; //正向迭代器所封装结点的指针
};

因此，我们通过一个结点的指针便可以构造出一个正向迭代器。

RBTree_Iterator( Node* node)
		:_node(node)
	{}

当对正向迭代器进行解引用操作时，我们直接返回对应结点数据的引用即可。

	Ref& operator*()
	{
		return _node->_data;
	}

当对正向迭代器进行->操作时，我们直接返回对应结点数据的指针即可。

	Ptr operator->()
	{
		return &(_node->_data);
	}

当然，正向迭代器当中至少还需要重载==和!=运算符，实现时直接判断两个迭代器所封装的结点是否是同一个即可。

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)
	{
		return _node == s._node;
	}

上面这些都没什么，红黑树正向迭代器实现时，真正的难点实际上是++和--运算符的重载。由于红黑树并不像顺序表或者链表那样，前者通过++和--操作符就可以实现迭代器的向前或者向后移动，后者则需要需要通过对++和--操作符进行重载来实现，比如++的操作符重载为“_node=_node._next”，这里由于红黑树的结构是树形结构，所以其++和--的方式会有所不同，下面我们一起来研究。

比如下面的是一颗红黑树，假设我们从最左节点开始遍历，由于红黑树有序的原因，我们应该得到的是【1，6，8，11，13，15，17，25，22，27】，所以++应该让我们从节点1经过++后变为6，即实现红黑树的正向迭代器时，一个结点的正向迭代器进行++操作后，应该根据红黑树中序遍历的序列找到当前结点的下一个结点。

具体逻辑如下：

1. 如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。
2. 如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。

代码：

Self& operator++()
	{
		if (_node->_right)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		else
		{
			// 左子树 根 右子树
			// 右为空，找孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_prev;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_prev;
			}

			_node = parent;
		}

		return *this;
	}

同理--操作与之类似，即找到当前节点的前一个节点，如6的前一个节点就是1，实现红黑树的正向迭代器时，一个结点的正向迭代器进行--操作后，应该根据红黑树中序遍历的序列找到当前结点的前一个结点。

具体逻辑如下：

1. 如果当前结点的左子树不为空，则--操作后应该找到其左子树当中的最右结点。
2. 如果当前结点的左子树为空，则--操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。

代码：

//前置--
	Self operator--()
	{
		if (_node->_left) //结点的左子树不为空
		{
			//寻找该结点左子树当中的最右结点
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right; //--后变为该结点
		}
		else //结点的左子树为空
		{
			//寻找孩子不在父亲左的祖先
			Node* cur = _node;
			Node* parent = cur->_prev;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_prev;
			}
			_node = parent; //--后变为该结点
		}
		return *this;
	}

正向迭代器实现后，我们需要在红黑树的实现当中进行迭代器类型的typedef。需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。

然后在红黑树当中实现成员函数begin和end：

• begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
• end函数返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器。

代码：

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node; //结点的类型
public:
	typedef __TreeIterator<T, T&, T*> iterator; //正向迭代器
    typedef RBTree_Iterator<T, const T&, const T*> const_iterator;//const迭代器
	
	iterator begin()
	{
		//寻找最左结点
		Node* left = _root;
		while (left&&left->_left)
		{
			left = left->_left;
		}
		//返回最左结点的正向迭代器
		return iterator(left);
	}
	iterator end()
	{
		//返回由nullptr构造得到的正向迭代器（不严谨）
		return iterator(nullptr);
	}

    const_iterator begin() const//const版
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return const_iterator(cur);
	}

	const_iterator end() const//const版
	{
		return const_iterator(nullptr);
	}
private:
	Node* _root; //红黑树的根结点
};

实际上，上述所实现的迭代器是有缺陷的，因为理论上我们对end()位置的正向迭代器进行--操作后，应该得到最后一个结点的正向迭代器，但我们实现end()时，是直接返回由nullptr构造得到的正向迭代器的，因此上述实现的代码无法完成此操作。

C++STL库当中实现红黑树时，在红黑树的根结点处增加了一个头结点，该头结点的左指针指向红黑树当中的最左结点，右指针指向红黑树当中的最右结点，父指针指向红黑树的根结点。

在该结构下，实现begin()时，直接用头结点的左孩子构造一个正向迭代器即可，实现rbegin()时，直接用头结点的右孩子构造一个反向迭代器即可（实际是先用该结点构造一个正向迭代器，再用正向迭代器构造出反向迭代器），而实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。此后，通过对逻辑的控制，就可以实现end()进行--操作后得到最后一个结点的正向迭代器。

但实现该结构需要更改当前很多函数的逻辑，例如插入结点时，若插入到了红黑树最左结点的左边，或最右结点的右边，此时需要更新头结点左右指针的指向，这里就不进行实际实现了。

3、【set的模拟实现】

完成上述操作后，set的模拟实现也就很简单了，其中的成员函数都是调用底层红黑树的对应接口就行了，需要注意的是set中节点的Value不能被改变，所以我们在设计set的迭代器时直接使用红黑树的const迭代器，具体体现如下：
代码：

template<class K>
	class set
	{
	public:

		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;



		iterator begin() const
		{
			return _set.begin();
		}

		iterator end() const
		{
			return _set.end();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _set.Insert(key);
		}

	private:
		RBTree<K, K,SetKeyOfT> _set;
	};

4、【map的模拟实现】

map的模拟实现也是相同的道理，其成员函数也是调用底层红黑树的对应接口，但对于map来说，除了将插入函数和查找函数返回值当中的结点指针改为迭代器之外，还需要实现[]运算符的重载函数。这里我们要将map的[ ]进行重载，具体就是下面3个步骤：

1. 调用insert函数插入键值对。
2. 拿出从insert函数获取到的迭代器。
3. 返回该迭代器位置元素的值value。

代码：

	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; //正向迭代器
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
		iterator begin()
		{
			return _map.begin();
		}

		iterator end()
		{
			return _map.end();
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));//匿名结构体，如果实例化
                                       //为整形，就是0，方便完成计数功能。
			return ret.first->second;// ((ret.first).operator->())->second
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _map.Insert(kv);
		}
			
	private:
		RBTree<K, pair<const K,V>,MapKeyOfT> _map;
	};

5、【封装后的完整代码】

RBTree.hpp:

enum Color
{
	Red,
	Black
};
template< class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _prev;
	T _data;
	Color _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _prev(nullptr)
		, _data(data)
		, _col(Red)
	{}
};


template<class T, class Ref, class Ptr>
struct RBTree_Iterator
{
	typedef RBTreeNode<T> Node;//节点类型
	typedef RBTree_Iterator<T, Ref, Ptr> Self;//迭代器类型
public:
	Ref& operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &(_node->_data);
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)
	{
		return _node == s._node;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		else
		{
			// 左子树 根 右子树
			// 右为空，找孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_prev;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_prev;
			}

			_node = parent;
		}

		return *this;
	}
	//前置--
	Self operator--()
	{
		if (_node->_left) //结点的左子树不为空
		{
			//寻找该结点左子树当中的最右结点
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right; //--后变为该结点
		}
		else //结点的左子树为空
		{
			//寻找孩子不在父亲左的祖先
			Node* cur = _node;
			Node* parent = cur->_prev;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_prev;
			}
			_node = parent; //--后变为该结点
		}
		return *this;
	}
	

	RBTree_Iterator( Node* node)
		:_node(node)
	{}
	Node* _node;
};





template<class K,class T,class KeyOfT>
class RBTree
{
	
public:
	typedef RBTree_Iterator<T, T&, T*> iterator;
	typedef RBTree_Iterator<T, const T&, const T*> const_iterator;
	typedef RBTreeNode<T> Node;

	iterator begin()
	{
		//寻找最左结点
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		//返回最左结点的正向迭代器
		return iterator(left);
	}
	iterator end()
	{
		//返回由nullptr构造得到的正向迭代器（不严谨）
		return iterator(nullptr);
	}

	const_iterator begin() const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return const_iterator(cur);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}



	//增
	pair<Node*,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = Black;
			return make_pair(_root,true);
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT GetKey;
		while (cur)
		{
			if (GetKey(cur->_data) < GetKey(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (GetKey(cur->_data) > GetKey(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur,false);
			}
		}
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = Red;
		if (GetKey(parent->_data) < GetKey(data))
		{
			parent->_right = cur;
			cur->_prev = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_prev = parent;
		}
		while (parent && parent->_col == Red)
		{
			Node* uncle = nullptr;
			Node* grandparent = parent->_prev;

			if (parent == grandparent->_left)
			{
				uncle = grandparent->_right;

				//      gR
				//   fB      uB
				// cR
				if (uncle && uncle->_col == Red)
				{
					// 变色
					parent->_col = uncle->_col = Black;
					grandparent->_col = Red;

					// 继续往上更新处理
					cur = grandparent;
					parent = cur->_prev;
				}
				else//uncle不存在或者uncle->_col==Black
				{
					//进行右单旋
					//       gB                  fB
					//   fR     uB           cR       gR 
					// cR                               uB
					if (cur == parent->_left)
					{
						RotateR(grandparent);
						parent->_col = Black;
						grandparent->_col = Red;

					}
					else
					{
						//进行左右双旋
						//       gB                  gB                fB
						//   fR      uB           cR     uB        cR       gR    
						//       cR             fR                             uB
						RotateL(parent);
						RotateR(grandparent);
						grandparent->_col = Red;
						cur->_col = Black;
					}
					break;
				}
			}
			else// parent == grandfather->_right
			{

				uncle = grandparent->_left;
				//      g
				//   u      f
				//            c
				if (uncle && uncle->_col == Red)
				{
					// 变色
					parent->_col = uncle->_col = Black;
					grandparent->_col = Red;
					// 继续往上更新处理
					cur = grandparent;
					parent = cur->_prev;
				}

				else//uncle不存在或者uncle->_col==Black
				{
					if (cur == parent->_right)
					{
						RotateL(grandparent);
						parent->_col = Black;
						grandparent->_col = Red;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);
						grandparent->_col = Red;
						cur->_col = Black;
					}
					break;
				}
			}
		}
		_root->_col = Black;
		return make_pair(newnode, true);
	}

	//删
	bool Erase(const T& data)
	{
		if (_root == nullptr)
		{
			return false;
		}
		Node* delcur = Find(data);

		//按照二叉搜索树的规则进行查找

		if (delcur == nullptr)
		{
			return false;
		}
		else
		{
			Node* delparent = delcur->_prev;
			//del是唯一的根节点
			if ((delcur == _root) && (delcur->_left == nullptr) && (delcur->_right == nullptr))
			{
				delete _root;
				_root = nullptr;
				return true;
			}
			//delcur有两个孩子
			if (delcur->_left != nullptr && delcur->_right != nullptr)
			{
				//找后序替代删除
				Node* minParent = delcur;
				Node* minRight = delcur->_right;
				while (minRight->_left)
				{
					minParent = minRight;
					minRight = minRight->_left;
				}
				delcur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key
				delcur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value
				delparent = minParent; //标记实际删除结点的父结点
				delcur = minRight; //标记实际删除的结点
			}
			//delcur只有一个孩子
			if ((delcur->_left != nullptr && delcur->_right == nullptr) || (delcur->_right != nullptr && delcur->_left == nullptr))
			{
				//只有一个孩子,父亲一定为黑，孩子一定为红
				//1.将红色节点的值赋值给父亲
				//2.将删除节点转换成删除红色叶子节点
				Node* child = delcur->_left == nullptr ? delcur->_right : delcur->_left;
				delcur->_kv.first = child->_kv.first;
				delcur->_kv.second = child->_kv.second;
				delparent = delcur;
				delcur = child;
			}

			//调整
			if (delcur->_col == Black)
			{
				AdjustRBTreeBalance(delcur, delparent);
			}

			//删除
			Node* parent = delcur->_prev;
			if (delcur == parent->_left)
			{
				parent->_left = nullptr;
			}
			else
			{
				parent->_right = nullptr;
			}
			delete delcur;
			return true;
		}
	}
	//查
	Node* Find(const T& data)
	{
		Node* cur = _root;
		KeyOfT GetKey;
		while (cur)
		{
			if (GetKey(data) < GetKey(cur->_data)) //key值小于该结点的值
			{
				cur = cur->_left; //在该结点的左子树当中查找
			}
			else if (GetKey(data) > GetKey(cur->_data)) //key值大于该结点的值
			{
				cur = cur->_right; //在该结点的右子树当中查找
			}
			else //找到了目标结点
			{
				return cur; //返回该结点
			}
		}
		return nullptr; //查找失败
	}

	RBTree()
		:_root(nullptr)
	{}
	RBTree(const RBTree<K, T, KeyOfT>& rbt)
	{
		_root = _Copy(rbt._root, nullptr);
	}
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> rbt)
	{
		swap(_root, rbt._root);
		return *this; //支持连续赋值
	}
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}


private:


	//拷贝树
	Node* _Copy(Node* root, Node* parent)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* copyNode = new Node(root->_data);
		copyNode->_parent = parent;
		copyNode->_left = _Copy(root->_left, copyNode);
		copyNode->_right = _Copy(root->_right, copyNode);
		return copyNode;
	}

	//析构函数子函数
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
	
	void AdjustRBTreeBalance(Node* delcur, Node* delparent)
	{
		while (delparent)
		{
			Node* brother = (delparent->_left == delcur) ? (delparent->_right) : (delparent->_left);

			//兄弟节点为黑色
			if (brother->_col == Black)
			{
				Node* bl = brother->_left;
				Node* br = brother->_right;
				//且在左侧
				if (brother == delparent->_left)
				{

					if ((brother->_left != nullptr) && (brother->_left->_col == Red))
					{
						//右单旋
						brother->_col = delparent->_col;
						delparent->_col = bl->_col = Black;
						RotateR(delparent);
						break;
					}
					//uncle的右节点为红色，且左节点为黑色或者空
					else if (((br != nullptr) && (br->_col == Red)) && ((bl == nullptr) || (bl->_col == Black)))
					{
						brother->_col = Red;
						br->_col = Black;
						RotateL(brother);
					}
					else
					{
						brother->_col = Red;
						if (delparent->_col == Red)
						{
							delparent->_col = Black;
							break;
						}
						else
						{
							delcur = delparent;
							delparent = delcur->_prev;
						}
					}
				}
				else//在右侧
				{

					if ((br != nullptr) && (brother->_right->_col == Red))
					{
						//左单旋
						brother->_col = delparent->_col;//兄弟旋转后取代父亲节点颜色
						delparent->_col = br->_col = Black;//父亲和侄节点变黑
						RotateL(delparent);
						break;
					}
					else if (((bl != nullptr) && (brother->_left->_col == Red)) && ((br == nullptr) || (br->_col == Black)))
					{
						brother->_col = Red;
						bl->_col = Black;
						RotateR(brother);
					}
					else
					{
						brother->_col = Red;
						if (delparent->_col == Red)
						{
							delparent->_col = Black;
							break;
						}
						else
						{
							delcur = delparent;
							delparent = delcur->_prev;
						}
					}
				}
			}
			else//兄弟节点为红色
			{
				if (brother == delparent->_left)//在左侧
				{
					brother->_col = Black;
					delparent->_col = Red;
					RotateR(delparent);
				}
				else//在右侧
				{
					RotateL(delparent);
					brother->_col = Black;
					delparent->_col = Red;
				}
			}
		}

	}


	//左旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_prev;

		parent->_prev = subR;
		if (subRL)
			subRL->_prev = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_prev = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_prev = parentParent;
		}
	}

	//右旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_prev = parent;

		Node* parentParent = parent->_prev;

		subL->_right = parent;
		parent->_prev = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_prev = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_prev = parentParent;
		}
	}

	Node* _root = nullptr;
};

Set.hpp:
 

#pragma once
#include "RBTree.hpp"
namespace bit
{
	template<class K>
	class set
	{
	public:

		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;



		iterator begin() const
		{
			return _set.begin();
		}

		iterator end() const
		{
			return _set.end();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _set.Insert(key);
		}

	private:
		RBTree<K, K,SetKeyOfT> _set;
	};
}

Map.hpp:

#pragma once
#include "RBTree.hpp"
namespace bit
{
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; //正向迭代器
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
		iterator begin()
		{
			return _map.begin();
		}

		iterator end()
		{
			return _map.end();
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;// ((ret.first).operator->())->second
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _map.Insert(kv);
		}
			
	private:
		RBTree<K, pair<const K,V>,MapKeyOfT> _map;
	};
}

Test.hpp:

#include<iostream>
#include<vector>
#include<string>
using namespace std;

#include"RBTree.hpp"
#include "Map.hpp"
#include "Set.hpp"

void test_set()
{
	bit::set<int> s;
	s.insert(4);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(2);
	s.insert(0);
	s.insert(10);
	s.insert(5);

	bit::set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *(it.operator->()) << " ";
		++it;
	}
	cout << endl;

	 //key޸
	it = s.begin();

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_map()
{
	bit::map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("right", "右边"));

	bit::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		cout << (*it).first << ":" << it->second << endl;
		++it;
	}
	cout << endl;

	string arr[] = { "a","a","s","s","a"};
	bit::map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
	}

	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;
}

int main()
{
	test_map();
	//test_set();

	return 0;
}

七、【unordered_map和unordered_set】

unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时的效率可达到O(logN)，即最差情况下需要比较红黑树的高度次，当树中的结点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。我们在介绍map和set的部分中已经知道map和set采用的是树形结构，而这里要讲的unordered_map和unordered_set所采用的则是哈希结构。

7.1、【unordered_set】

7.1.1【unordered_set的介绍】

1、在unordered_set中，元素的值同时也是唯一地标识它的key。
2、在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中。
3、unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。
4、它的迭代器至少是前向迭代器。

5、unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素。

7.1.2【unordered_set的使用】

1、【unordered_set的定义】

主要有以下3种方式：

void test_unordered_set()
{

   	//方式一： 构造一个某类型的空容器。
	unordered_set<int> us1; //构造int类型的空容器
	//方式二： 拷贝构造某同类型容器的复制品。
	unordered_set<int> us2(us1); //拷贝构造同类型容器us1的复制品
	//方式三： 使用迭代器拷贝构造某一段内容。
	string str("abcedf");//通过string的迭代器区间进行构造。
	unordered_set<char> us3(str.begin(), str.end()); //构造string对象某段区间的复制品
	
}

2、【函数接口】

unordered_set当中迭代器相关函数如下：

使用示例：

void test_unordered_set()
{

	unordered_set<int> us1; //构造int类型的空容器
	unordered_set<int> us2(us1); //拷贝构造同类型容器us1的复制品

	string str("abcedf");//通过string的迭代器区间进行构造。
	unordered_set<char> us3(str.begin(), str.end()); //构造string对象某段区间的复制品



	unordered_set<int> us;
	//插入元素（去重）
	us.insert(1);
	us.insert(4);
	us.insert(3);
	us.insert(3);
	us.insert(2);
	us.insert(2);
	us.insert(3);
	//遍历容器方式一（范围for）
	for (auto e : us)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 3 2
	//删除元素方式一(直接删除)
	us.erase(3);
	//删除元素方式二（通过迭代器删除）
	unordered_set<int>::iterator pos = us.find(1); //查找值为1的元素
	if (pos != us.end())
	{
		us.erase(pos);
	}
	//遍历容器方式二（迭代器遍历）
	unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl; //4 2
	//容器中值为2的元素个数
	cout << us.count(2) << endl; //1
	//容器大小
	cout << us.size() << endl; //2
	//清空容器
	us.clear();
	//容器判空
	cout << us.empty() << endl; //1
	//交换两个容器的数据
	unordered_set<int> tmp{ 11, 22, 33, 44 };
	us.swap(tmp);
	for (auto e : us)
	{
		cout << e << " ";
	}
	cout << endl; //11 22 33 44

}

3、【unordered_multiset】

unordered_multiset容器与unordered_set容器的底层数据结构是一样的，都是哈希表，其次，它们所提供的成员函数的接口都是基本一致的，这里就不再列举了，这两种容器唯一的区别就是，unordered_multiset容器允许键值冗余，即unordered_multiset容器当中存储的元素是可以重复的。
使用示例：

void test_multi_ordered_set()
{
	unordered_multiset<int> ums;
	//插入元素（允许重复）
	ums.insert(1);
	ums.insert(4);
	ums.insert(3);
	ums.insert(3);
	ums.insert(2);
	ums.insert(2);
	ums.insert(3);
	for (auto e : ums)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 3 3 3 2 2
	cout << ums.count(2) << endl; //1
	//容器大小
	cout << ums.size() << endl; //2
	//清空容器
	ums.clear();
	//容器判空
	cout << ums.empty() << endl; //1
	//交换两个容器的数据
	unordered_multiset<int> tmp{ 11, 22, 33, 44 };
	ums.swap(tmp);
	for (auto e : ums)
	{
		cout << e << " ";
	}
	cout << endl; //11 22 33 44
}

由于unordered_multiset容器允许键值冗余，因此该容器中成员函数find和count的意义与unordered_set容器中的也有所不同：

7.2、【unordered_map】

7.2.1【unordered_map的介绍】

1、unordered_map是存储<key, value>键值对的关联式容器，其允许通过key值快速的索引到与其对应是value。
2、在unordered_map中，键值通常用于唯一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3、在内部，unordered_map没有对<key, value>按照任何特定的顺序排序，为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4、unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5、unordered_map实现了直接访问操作符（operator[]），它允许使用key作为参数直接访问value。
6、它的迭代器至少是前向迭代器。

7.2.2【unordered_map的使用】

1、【unordered_map的定义】

主要也是3种方式：

void test_unordered_map()
{
	//方式一： 指定key和value的类型构造一个空容器。
	unordered_map<int, double> um1; //构造一个key为int类型，value为double类型的空容器
	//方式二： 拷贝构造某同类型容器的复制品
	unordered_map<int, double> um2(um1); //拷贝构造同类型容器um1的复制品
	//方式三： 使用迭代器拷贝构造某一段内容。
	unordered_map<int, double> um3(um2.begin(), um2.end()); //使用迭代器拷贝构造um2容器某段区间的复制品

}

2、【函数接口】

unordered_map当中常用的成员函数如下：

除了上述的成员函数之外，unordered_map容器当中还实现了[ ]运算符重载函数，该重载函数的功能非常强大：[key]

      1、若当前容器中已有键值为key的键值对，则返回该键值对value的引用。
      2、若当前容器中没有键值为key的键值对，则先插入键值对<key, value()>，然后再返回该键值对中value的引用。

unordered_map当中迭代器相关函数如下：

使用示例：

void test_unordered_map()
{
	//方式一： 指定key和value的类型构造一个空容器。
	unordered_map<int, double> um1; //构造一个key为int类型，value为double类型的空容器
	//方式二： 拷贝构造某同类型容器的复制品
	unordered_map<int, double> um2(um1); //拷贝构造同类型容器um1的复制品
	//方式三： 使用迭代器拷贝构造某一段内容。
	unordered_map<int, double> um3(um2.begin(), um2.end()); //使用迭代器拷贝构造um2容器某段区间的复制品



	unordered_map<int, string> um;
	//插入键值对方式一：构造匿名对象插入
	um.insert(pair<int, string>(1, "one"));
	um.insert(pair<int, string>(2, "two"));
	um.insert(pair<int, string>(3, "three"));
	//遍历方式一：范围for
	for (auto e : um)
	{
		cout << e.first << "->" << e.second << " ";
	}
	cout << endl; //1->one 2->two 3->three
	//插入键值对方式二：调用make_pair函数模板插入
	um.insert(make_pair(4, "four"));
	um.insert(make_pair(5, "five"));
	um.insert(make_pair(6, "six"));
	//遍历方式二：迭代器遍历
	unordered_map<int, string>::iterator it = um.begin();
	while (it != um.end())
	{
		cout << it->first << "->" << it->second << " ";
		it++;
	}
	cout << endl; //1->one 2->two 3->three 4->four 5->five 6->six
	//插入键值对方式三：利用[]运算符重载函数进行插入（常用）
	um[7] = "seven";
	um[8] = "eight";
	um[9] = "nine";
	for (auto e : um)
	{
		cout << e.first << "->" << e.second << " ";
	}
	cout << endl; //9->nine 1->one 2->two 3->three 4->four 5->five 6->six 7->seven 8->eight
	//删除键值对方式一：根据key值删除
	um.erase(5);
	//删除键值对方式二：根据迭代器删除
	unordered_map<int, string>::iterator pos = um.find(7); //查找键值为7的键值对
	if (pos != um.end())
	{
		um.erase(pos);
	}
	for (auto e : um)
	{
		cout << e.first << "->" << e.second << " ";
	}
	cout << endl; //9->nine 1->one 2->two 3->three 4->four 6->six 8->eight
	//修改键值对方式一：通过find获得迭代器，通过迭代器修改
	pos = um.find(1);
	if (pos != um.end())
	{
		pos->second = "one/first";
	}
	//修改键值对方式二：利用[]运算符重载函数进行修改（常用）
	um[2] = "two/second";
	for (auto e : um)
	{
		cout << e.first << "->" << e.second << " ";
	}
	cout << endl; //9->nine 1->one/first 2->two/second 3->three 4->four 6->six 8->eight
	//容器中key值为3的键值对的个数
	cout << um.count(3) << endl;
	//容器的大小
	cout << um.size() << endl;
	//清空容器
	um.clear();
	//容器判空
	cout << um.empty() << endl;
	//交换两个容器的数据
	unordered_map<int, string> tmp{ { 2021, "before" }, { 2022, "now" } };
	um.swap(tmp);
	for (auto e : um)
	{
		cout << e.first << "->" << e.second << " ";
	}
	cout << endl; //2021->before 2022->now





	cout << "计数功能" << endl;

	string arr[] = { "a","a","s","s","a" };
	unordered_map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
	}

	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;

}

3、unordered_multimap

unordered_multimap容器与unordered_map容器的底层数据结构是一样的，都是哈希表，其次，它们所提供的成员函数的接口都是基本一致的，这里就不再列举了，这两种容器唯一的区别就是，unordered_multimap容器允许键值冗余，即unordered_multimap容器当中存储的键值对的key值是可以重复的。

使用示例：

void test_unordermultimap()
{
	unordered_multimap<int, string> umm;
	//插入键值对（允许键值重复）
	umm.insert(make_pair(2022, "吃饭"));
	umm.insert(make_pair(2022, "睡觉"));
	umm.insert(make_pair(2022, "敲代码"));
	for (auto e : umm)
	{
		cout << e.first << "->" << e.second << " ";
	}
	cout << endl; //2022->吃饭 2022->睡觉 2022->敲代码

}

由于unordered_multimap容器允许键值对的键值冗余，因此该容器中成员函数find和count的意义与unordered_map容器中的也有所不同：

其次，由于unordered_multimap容器允许键值对的键值冗余，调用[ ]运算符重载函数时，应该返回键值为key的哪一个键值对的value的引用存在歧义，因此在unordered_multimap容器当中没有实现[ ]运算符重载函数。

7.3、【unordered_map和unordered_set的模拟实现】

1、【问题及其说明】

上面我们用红黑树封装出来了map和set，那么unordered_map和unordered_set底层采用了什么数据结构呢？

其实是采用哈希桶来实现的，与红黑树一样只需要用一个模板参数T来记录节点存储的数据类型（主要包括两种K类型和KV类型两种类型结构）

而哈希结点的模板参数也应该由原来的K、V变为T：

• 上层容器是unordered_set时，传入的T是键值，哈希结点中存储的就是键值。
• 上层容器是unordered_map时，传入的T是键值对，哈希结点中存储的就是键值对。

更改模板参数后，哈希结点的定义如下：

//哈希结点的定义
template<class T>
struct Hash_Node
{
	T _data;
	Hash_Node<T>* _next;

	//构造函数
	Hash_Node(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

这里同样需要实现仿函数来获得元素的键值，然后通过哈希函数计算出对应的哈希地址进行映射。现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。

因此，unordered_map容器需要向底层哈希表提供一个仿函数，该仿函数返回键值对当中的键值。而虽然unordered_set容器传入哈希表的T就是键值，但是底层哈希表并不知道上层容器的种类，底层哈希表在获取键值时会统一通过传入的仿函数进行获取，因此unordered_set容器也需要向底层哈希表提供一个仿函数。

//unordered_map的仿函数
    struct MapKeyOfT
	{
		const K& operator()(const pair<K,V>& kv)
		{
			return kv.first;
		}
	};

//unordered_set的仿函数
    struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

因此，底层哈希表的模板参数现在需要增加一个，用于接收上层容器提供的仿函数。

注意：这里的HashFunc主要是用来处理其他并不能直接支持进行取模操作的数据类型进行取模的，从而实现映射关系。

还需要对哈希桶实现一个迭代器来封装出相应的功能，当然其中还有很多要注意的点请耐心观看。

2、【哈希桶迭代器的实现】

哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，可能需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中都应该存储哈希表的地址。

这里我们主要看前置++的逻辑实现：

++运算符重载函数的实现逻辑并不是很难，我们只需要知道如何找到当前结点的下一个结点即可。

• 若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点。
• 若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点。

//前置++
Self& operator++()
{
	if (_node->_next) //该结点不是当前哈希桶中的最后一个结点
	{
		_node = _node->_next; //++后变为当前哈希桶中的下一个结点
	}
	else //该结点是当前哈希桶中的最后一个结点
	{
		KeyOfT kot;
		HashFunc hf;
		size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通过哈希函数计算出当前所处哈希桶编号index（除数不能是capacity）
		index++; //从下一个位置开始找一个非空的哈希桶
		while (index < _pht->_table.size()) //直到将整个哈希表找完
		{
			if (_pht->_table[index]) //当前哈希桶非空
			{
				_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点
				return *this;
			}
			index++; //当前哈希桶为空桶，找下一个哈希桶
		}
		_node = nullptr; //哈希表中已经没有空桶了，++后变为nullptr
	}
	return *this;
}

迭代器的完整代码：

//哈希桶类的声明
template<class K, class T, class GetKey, class HashFunc>
class HashBucket;

//哈希桶迭代器的实现
template<class K, class T, class Ref, class Ptr, class GetKey, class Hash >
struct HashBucket_Iterator
{
	typedef Hash_Node<T> Node; //哈希结点的类型
	typedef HashBucket<K, T, GetKey, Hash> HB; //哈希表的类型
	typedef HashBucket_Iterator<K, T,  Ref, Ptr, GetKey, Hash> Self; //正向迭代器的类型
	
		//构造函数
	HashBucket_Iterator(Node* node, HB* phb)
		:_node(node) //结点指针
		, _phb(phb) //哈希表地址
	{}
	HashBucket_Iterator(Node* node, const HB* phb)
		:_node(node) //结点指针
		, _phb(phb) //哈希表地址
	{}
	Ref operator*()
	{
		return _node->_data; //返回哈希结点中数据的引用
	}

	Ptr operator->()
	{
		return &_node->_data; //返回哈希结点中数据的地址
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node; //判断两个结点的地址是否不同
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node; //判断两个结点的地址是否相同
	}
	//前置++
	Self& operator++()
	{
		if (_node->_next != nullptr)
		{
			_node = _node->_next;
		}
		else
		{
			GetKey kot;
			Hash hf;
			size_t index = hf(kot(_node->_data)) % (_phb->_bucket.size());
			index++;
			while (index < _phb->_bucket.size())
			{
				if (_phb->_bucket[index] != nullptr)
				{
					_node = _phb->_bucket[index];
					return *this;
					//break;
				}
				index++;
			}
			/*if (index == _phb->_bucket.size())
			{
				_node = nullptr;
			}*/
			_node = nullptr;
		}
		return *this;
	}


	Node* _node;
	const HB* _phb;
};

这里仍然存在几个问题首先为什么我们的迭代器上方有一份哈希桶类的声明？

这是因为哈希桶类和迭代器类具有相互依赖的关系，主要体现为迭代器的成员当中有一个成员是哈希桶类，由于编译器在编译过程中只会向上查找，而哈希桶类在迭代器类的下面，所以我们需要写份声明来告诉编译器，哈希桶类存在。

其次为什么我们的哈希桶成员要定义成const类型，以及为什么要多写一份const类型的构造？

这个问题需要在实现const类型的begin和const类型的end进行说明。

注意： 哈希桶的迭代器类型是单向迭代器，没有反向迭代器，即没有实现 “- -” 运算符的重载，若是想让哈希桶支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。

正向迭代器实现后，我们需要在哈希桶的实现当中进行如下操作：

进行正向迭代器类型的typedef，需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。
由于正向迭代器中++运算符重载函数在寻找下一个结点时，会访问哈希表中的成员变量_bucket，而_bucket成员变量是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希桶类的友元。将哈希表中查找函数返回的结点指针，改为返回由结点指针和哈希表地址构成的正向迭代器。
将哈希表中插入函数的返回值类型，改为由正向迭代器类型和布尔类型所构成的键值对。
然后我们就可以在哈希表中实现迭代器相关的成员函数了：

• begin函数： 返回哈希表中第一个非空哈希桶中的第一个结点的正向迭代器。
• end函数： 返回空指针的正向迭代器。

	iterator begin()
	{
		size_t i = 0;
		while (i < _bucket.size()) //找到第一个非空哈希桶
		{
			if (_bucket[i]) //该哈希桶非空
			{
				return iterator(_bucket[i], this); //返回该哈希桶中的第一个结点的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中无数据，返回end()
	}


	iterator end()
	{
		return iterator(nullptr, this); //返回nullptr的正向迭代器
	}




	const_iterator begin() const
	{
		size_t i = 0;
		while (i < _bucket.size()) //找到第一个非空哈希桶
		{
			if (_bucket[i]) //该哈希桶非空
			{
				return const_iterator(_bucket[i], this); //返回该哈希桶中的第一个结点的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中无数据，返回end(
	}

	// this-> const HashTable<K, T, KeyOfT, Hash>*
	const_iterator end() const
	{
		return const_iterator(nullptr, this);
	}

现在我们来解决那个问题，为什么我们的哈希桶成员要定义成const类型，以及为什么要多写一份const类型的构造？

我们可以看到我们实现了const类型的begin和end，需要注意的是我们在用（nullptr,this）构造const迭代器时，这里的this指针使用const修饰的，所以如果我们使用普通迭代器进行构造的话，会导致使用const类型构造非const类型，从而导致权限的放大。因此我们需要使用const类型的构造，由于构造函数中的phb是const类型，为了防止const类型初始化非const类型（这种权限的放大），我们将成员变量也变为const类型从而达到匹配的目的。

3、【unordered_set的模拟实现】

实现unordered_set的各个接口时，就只需要调用底层哈希表对应的接口就行了。这里插入函数需要特殊说明一下：

这里主要涉及到一个迭代器转换的问题，我们要知道普通迭代器和const迭代器之间不能随意转换的，我们更不能单纯的认为这里的问题仅仅是权限的问题，其实不是，这里主要的问题是，const类型的迭代器和普通迭代器是两个不同的类，所以不能进行相互转换。我们知道unordered_set是不支持修改value的所以我们应该使用const类型的迭代器封unordered_set的迭代器像下面这样：

而我们这里unordered_set的插入函数是调用哈希桶的插入函数，两者的迭代器类型不同，不能相互转换，体现为如下形式：

那为什么，我们在实现set和map时没有这种问题，主要是因为它们的迭代器我们当时采用的是单个成员变量，Node*，所以可以直接通过Node*来实现构造const类型的迭代器。

完整代码：

template<class K, class Hash = HashFunc<K>>
class my_unordered_set
{

	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	//现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取
	typedef typename HashBucket<K, K, SetKeyOfT,Hash>::const_iterator iterator;
	//typedef typename HashBucket<K, K, SetKeyOfT,Hash>::const_iterator const_iterator;

	iterator begin() const
	{
		return _hb.begin();
	}

	iterator end() const
	{
		return _hb.end();
	}

	//插入函数
	pair<iterator, bool> insert(const K& key)
	{
		/*auto ret = _hb.Insert(key);
		return pair<iterator, bool>(iterator(ret.first._node, ret.first._phb), ret.second);*/
		return _hb.Insert(key);
	}
	//删除函数
	bool erase(const K& key)
	{
		return _hb.Erase(key);
	}
	//查找函数
	iterator find(const K& key)
	{
		return _hb.Find(key);
	}
private:
	HashBucket<K,  K,SetKeyOfT,Hash> _hb;
};

4、【unordered_map的模拟实现】

实现unordered_map的各个接口时，也是调用底层哈希表对应的接口就行了，此外还需要实现  “[ ]” 运算符的重载。具体与map实现方式相同。

【完整代码】

#include "Hash_Bucket.hpp"
template<class K, class V, class Hash = HashFunc<K>>
class my_unordered_map
{
public:
	struct MapKeyOfT
	{
		const K& operator()(const pair<K,V>& kv)
		{
			return kv.first;
		}
	};

	typedef typename HashBucket<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
	iterator begin()
	{
		return _hb.begin();
	}
	iterator end()
	{
		return _hb.end();
	}
	//插入函数
	pair<iterator, bool> insert(const pair<K, V>& kv)
	{
		return _hb.Insert(kv);
	}
	//赋值运算符重载
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert(make_pair(key, V()));
		iterator it = ret.first;
		return it->second;
	}
	const V& operator[](const K& key) const
	{
		pair<iterator, bool> ret = _hb.Insert(make_pair(key, V()));
		return ret.first->second;
	}
	//删除函数
	bool erase(const K& key)
	{
		return _hb.Erase(key);
	}
	//查找函数
	iterator find(const K& key)
	{
		return _hb.Find(key);
	}
private:
	HashBucket<K, pair<const K,V>, MapKeyOfT, Hash> _hb;
};

5、【封装后的完整代码】

HashBucket.hpp:

#include <iostream>
#include <vector>
using namespace std;




template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};


//HashFunc<string>
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		//cout << key << ":" << hash << endl;
		return hash;
	}
};


template<class T>
struct Hash_Node
{
	T _data;
	Hash_Node<T>* _next;
	Hash_Node(const T& data)
		:_data(data),
		_next(nullptr)
	{ }
};

template<class K, class T, class GetKey, class HashFunc>
class HashBucket;
template<class K, class T, class Ref, class Ptr, class GetKey, class Hash >
struct HashBucket_Iterator
{
	typedef Hash_Node<T> Node; //哈希结点的类型
	typedef HashBucket<K, T, GetKey, Hash> HB; //哈希表的类型
	typedef HashBucket_Iterator<K, T,  Ref, Ptr, GetKey, Hash> Self; //正向迭代器的类型
	
		//构造函数
	HashBucket_Iterator(Node* node, HB* phb)
		:_node(node) //结点指针
		, _phb(phb) //哈希表地址
	{}
	HashBucket_Iterator(Node* node, const HB* phb)
		:_node(node) //结点指针
		, _phb(phb) //哈希表地址
	{}
	Ref operator*()
	{
		return _node->_data; //返回哈希结点中数据的引用
	}

	Ptr operator->()
	{
		return &_node->_data; //返回哈希结点中数据的地址
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node; //判断两个结点的地址是否不同
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node; //判断两个结点的地址是否相同
	}
	//前置++
	Self& operator++()
	{
		if (_node->_next != nullptr)
		{
			_node = _node->_next;
		}
		else
		{
			GetKey kot;
			Hash hf;
			size_t index = hf(kot(_node->_data)) % (_phb->_bucket.size());
			index++;
			while (index < _phb->_bucket.size())
			{
				if (_phb->_bucket[index] != nullptr)
				{
					_node = _phb->_bucket[index];
					return *this;
					//break;
				}
				index++;
			}
			/*if (index == _phb->_bucket.size())
			{
				_node = nullptr;
			}*/
			_node = nullptr;
		}
		return *this;
	}


	Node* _node;
	const HB* _phb;
};

template<class K, class T, class GetKey, class Hash = HashFunc<K>>
class HashBucket
{

public:
	typedef  Hash_Node<T>  Node;

	//友元类
	template<class K, class T, class Ref, class Ptr, class GetKey, class Hash>
	friend struct HashBucket_Iterator;//友元类，因为_bucket定义的是类的私有成员变量，而迭代器中需要使用到_bucket，将其定义为友元，方便访问，需要注意的是带模板的友元需要连其模板参数一起进行定义。
	//友元类
	typedef HashBucket_Iterator<K, T, T&, T*, GetKey, Hash> iterator;
	typedef HashBucket_Iterator<K, T, const T&, const T*, GetKey, Hash> const_iterator;


	HashBucket()
	{
		_bucket.resize(10);
	}
	~HashBucket()
	{
		for (size_t i = 0; i < _bucket.size(); i++)
		{
			Node* cur = _bucket[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_bucket[i] = nullptr;
		}
	}

	iterator begin()
	{
		size_t i = 0;
		while (i < _bucket.size()) //找到第一个非空哈希桶
		{
			if (_bucket[i]) //该哈希桶非空
			{
				return iterator(_bucket[i], this); //返回该哈希桶中的第一个结点的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中无数据，返回end()
	}


	iterator end()
	{
		return iterator(nullptr, this); //返回nullptr的正向迭代器
	}




	const_iterator begin() const
	{
		size_t i = 0;
		while (i < _bucket.size()) //找到第一个非空哈希桶
		{
			if (_bucket[i]) //该哈希桶非空
			{
				return const_iterator(_bucket[i], this); //返回该哈希桶中的第一个结点的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中无数据，返回end(
	}

	// this-> const HashTable<K, T, KeyOfT, Hash>*
	const_iterator end() const
	{
		return const_iterator(nullptr, this);
	}
	

	iterator Find(const K& key)
	{
		GetKey kot;
		Hash hf;
		if (_bucket.size() == 0)
		{
			return end();
		}
		size_t index = hf(key) % _bucket.size();
		Node* cur = _bucket[index];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return iterator(cur, this);
			}
			cur = cur->_next;
		}
		return end();
	}
	pair<iterator, bool> Insert(const T& data)
	{
		GetKey kot;
		Hash hf;
		iterator ret = Find(kot(data));
		if (ret != end())
		{
			return make_pair(ret, false);
		}
		else
		{

			if (_n == _bucket.size())
			{
				//扩容
				vector<Node*> newbucket;
				size_t newsize = _bucket.size() * 2;
				newbucket.resize(newsize);
				for (size_t i = 0; i < _bucket.size(); i++)
				{
					Node* cur = _bucket[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t index = hf(kot(cur->_data)) % newbucket.size();
						cur->_next = newbucket[index];
						newbucket[index] = cur;
						cur = next;
					}
					_bucket[i] = nullptr;
				}
				_bucket.swap(newbucket);
			}
			size_t index = hf(kot(data)) % _bucket.size();
			Node* newnode = new Node(data);
			newnode->_next = _bucket[index];
			_bucket[index] = newnode;
			_n++;
			return make_pair(iterator(newnode, this), true);
		}
	}
	bool Erase(const K& key)
	{
		Hash hf;
		GetKey kot;
		Node* ret = Find(key);
		if (ret == nullptr)
		{
			return false;
		}
		else
		{
			size_t index = hf(key) % _bucket.size();
			Node* cur = _bucket[index];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_bucket[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;

		}
	}
	void Some()
	{
		size_t bucketSize = 0;
		size_t maxBucketLen = 0;
		size_t sum = 0;
		double averageBucketLen = 0;

		for (size_t i = 0; i < _bucket.size(); i++)
		{
			Node* cur = _bucket[i];
			if (cur)
			{
				++bucketSize;
			}

			size_t bucketLen = 0;
			while (cur)
			{
				++bucketLen;
				cur = cur->_next;
			}

			sum += bucketLen;

			if (bucketLen > maxBucketLen)
			{
				maxBucketLen = bucketLen;
			}
		}

		averageBucketLen = (double)sum / (double)bucketSize;

		printf("all bucketSize:%d\n", _bucket.size());
		printf("bucketSize:%d\n", bucketSize);
		printf("maxBucketLen:%d\n", maxBucketLen);
		printf("averageBucketLen:%lf\n\n", averageBucketLen);
	}

private:
	vector<Node*> _bucket;
	size_t _n = 0;
};

注意：友元的问题

unorder_set.hpp:

#include "Hash_Bucket.hpp"
template<class K, class Hash = HashFunc<K>>
class my_unordered_set
{

	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	//现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取
	typedef typename HashBucket<K, K, SetKeyOfT,Hash>::const_iterator iterator;
	//typedef typename HashBucket<K, K, SetKeyOfT,Hash>::const_iterator const_iterator;

	iterator begin() const
	{
		return _hb.begin();
	}

	iterator end() const
	{
		return _hb.end();
	}

	//插入函数
	pair<iterator, bool> insert(const K& key)
	{
		auto ret = _hb.Insert(key);
		return pair<iterator, bool>(iterator(ret.first._node, ret.first._phb), ret.second);
	}
	//删除函数
	bool erase(const K& key)
	{
		return _hb.Erase(key);
	}
	//查找函数
	iterator find(const K& key)
	{
		return _hb.Find(key);
	}
private:
	HashBucket<K,  K,SetKeyOfT,Hash> _hb;
};

unorder_map.hpp:

#include "Hash_Bucket.hpp"
template<class K, class V, class Hash = HashFunc<K>>
class my_unordered_map
{
public:
	struct MapKeyOfT
	{
		const K& operator()(const pair<K,V>& kv)
		{
			return kv.first;
		}
	};

	typedef typename HashBucket<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
	iterator begin()
	{
		return _hb.begin();
	}
	iterator end()
	{
		return _hb.end();
	}
	//插入函数
	pair<iterator, bool> insert(const pair<K, V>& kv)
	{
		return _hb.Insert(kv);
	}
	//赋值运算符重载
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert(make_pair(key, V()));
		iterator it = ret.first;
		return it->second;
	}
	const V& operator[](const K& key) const
	{
		pair<iterator, bool> ret = _hb.Insert(make_pair(key, V()));
		return ret.first->second;
	}
	//删除函数
	bool erase(const K& key)
	{
		return _hb.Erase(key);
	}
	//查找函数
	iterator find(const K& key)
	{
		return _hb.Find(key);
	}
private:
	HashBucket<K, pair<const K,V>, MapKeyOfT, Hash> _hb;
};

Test.cpp:

#include "unorder_set.hpp"
#include "unorder_map.hpp"

void test_map()
{
	my_unordered_map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("string","ַ字符串"));
	dict.insert(make_pair("insert", "插入"));

	for (auto& kv : dict)
	{
		//kv.first += 'x';
		//kv.second += 'x';

		cout << kv.first << ":" << kv.second << endl;
	}

	cout << endl;

	string arr[] = { "a","a","s","s","a" };
	my_unordered_map<string, int> count_map;
	for (auto& e : arr)
	{
		count_map[e]++;
	}

	for (auto& kv : count_map)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;
}



void test_set()
{
	// 17:05
	my_unordered_set<int> us;
	us.insert(5);
	us.insert(15);
	us.insert(52);
	us.insert(3);

	my_unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		//*it += 5;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : us)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{
	//test_map();
	test_set();
	return 0;
}

7.4【map/set和unordered_set/unordered_map的区别】

xxx容器与unordered_xxx容器对上层所提供函数接口的名字和功能虽然一致，但它们的底层实现却大不相同，xxx容器和unordered_xxx容器的区别如下：

1、map/set与unordered_map/unordered_set底层数据结构的区别

我们知道xxx容器采用红黑树实现，也就意味着它们存储的数据在底层的存储方式是按照红黑树的结构进行存储，是通过比较，旋转等措施实现维护，而unordered_xxx容器底层是哈希桶，是哈希结构，相比之下后者是通过哈希函数将数据进行映射。

如果体现在编译器上，区别就在于xxx容器不管插入时顺序是如何，打印出来都是默认按照升序的方式，而unordered_xxx则没有特定的顺序：

#include <iostream>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <time.h>
using namespace std;
void Test_set()
{
	int arr[] = { 2,5,1,6,8,9,4,3,7 };
	set<int> st;
	unordered_set<int> ost;
	for (auto e : arr)
	{
		st.insert(e);
		ost.insert(e);
	}
	set<int>::iterator it = st.begin();
	cout << "set：";
	while (it != st.end())
	{
		cout  << *it << " ";
		++it;
	}
	
	cout <<endl<< "unordered_set：";
	for (auto e : ost)
	{
		cout  << e << " ";
	}
	cout << endl;
}
void Test_map()
{

	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	cout << "map：" <<endl;
	for (auto e : m)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;
	
	unordered_map<int, string> om;
	om.insert(make_pair(2, "two"));
	om.insert(make_pair(1, "one"));
	om.insert(make_pair(3, "three"));
	cout << "om："<<endl;
	for (auto e : om)
	{
		cout << "<key:" << e.first << "," << "val:" << e.second << ">" << " " << endl;
	}
	cout << endl;
}
int main()
{
	Test_set();
	Test_map();
	return 0;
}

实际上由于unordered_xxx容器采用的是哈希结构，所以其性能会更胜一筹。

2、map/set与unordered_map/unordered_set的性能测试

map容器与unordered_map容器的差别和set容器与unordered_set容器的差别类似，下面我们以set容器和unordered_set容器的测试为例。

说到一个容器的性能，我们最关心的实际就是该容器增删查改的效率。我们可以通过下列代码测试set容器和unordered_set容器insert、find以及erase的效率。

下面让我们对1000个数做增删查改操作：

void Test_speed()
{
	int N = 1000;
	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(NULL));
	//随机生成N个数字
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	/****************插入效率测试****************/
	//将这N个数插入set容器
	set<int> s;
	clock_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	clock_t end1 = clock();

	//将这N个数插入unordered_set容器
	unordered_set<int> us;
	clock_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	clock_t end2 = clock();

	//分别输出插入set容器和unordered_set容器所用的时间
	cout << "set insert: " << end1 - begin1 << endl;
	cout << "unordered_set insert: " << end2 - begin2 << endl;

	/****************查找效率测试****************/
	//在set容器中查找这N个数
	clock_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	clock_t end3 = clock();

	//在unordered_set容器中查找这N个数
	clock_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	clock_t end4 = clock();

	//分别输出在set容器和unordered_set容器中查找这N个数所用的时间
	cout << "set find: " << end3 - begin3 << endl;
	cout << "unordered_set find: " << end4 - begin4 << endl;

	/****************删除效率测试****************/
	//将这N个数从set容器中删除
	clock_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	clock_t end5 = clock();

	//将这N个数从unordered_set容器中删除
	clock_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	clock_t end6 = clock();

	//分别输出将这N个数从set容器和unordered_set容器中删除所用的时间
	cout << "set erase: " << end5 - begin5 << endl;
	cout << "unordered_set erase: " << end6 - begin6 << endl;

}

int main()
{
	//Test_set();
	//Test_map();
	Test_speed();
	return 0;
}

当N为1000时，set容器和unordered_set容器增删查改的效率差异并不大，在Debug版本下的测试结果如下：

在Release版本下，set容器和unordered_set容器对1000个数做增删查改操作所用的时间更是被优化到了接近0毫秒。

接下来我们增加数据个数，将数据增加到10000000个数做增删查改操作：

而当N为10000000时，set容器和unordered_set容器增删查改的效率的差异就很明显了，在Debug版本下的测试结果如下：

而经过Release版本优化后，unordered_set容器对10000000个数做查找和删除操作所用的时间还是被优化到了接近0毫秒，插入操作所用的时间也仅仅是0.1秒左右。但是set容器对10000000个数做增删查改操作所用的时间还是需要1秒左右，与unordered_set容器相比就占了下风。

注意： 这里给出的N值仅作参考，在不同的测试环境下可能不同。

测试结论

根据测试结果可以得出以下结论：

• 当处理数据量小时，map/set容器与unordered_map/unordered_set容器增删查改的效率差异不大。
• 当处理数据量大时，map/set容器与unordered_map/unordered_set容器增删查改的效率相比，unordered系列容器的效率更高。

因此，当处理数据量较小时，选用xxx容器与unordered_xxx容器的差异不大；当处理数据量较大时，建议选用对应的unordered_xxx容器。

补充一点： 当需要存储的序列为有序时，应该选用map/set容器。

八、【位图】

8.1【位图的介绍】

【引入】

在我们了解了哈希及的思想以后，我们知道哈希对于搜索问题来说有极大的优势，由于哈希结构是通过某种映射关系来实现对元素的搜索，这样可以使搜索的时间复杂度达到O（1），

那我们来看下面这样一个问题，来看一下应该如何用哈希的思想来解决。

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？

要判断一个数是否在某一堆数中，我们可能会想到如下方法：

• 将这一堆数进行排序，然后通过二分查找的方法判断该数是否在这一堆数中。
• 将这一堆数插入到unordered_set容器中，然后调用find函数判断该数是否在这一堆数中。

单从方法上来看，这两种方法都是可以，而且效率也不错，第一种方法的时间复杂度是O(N*logN)，第二种方法的时间复杂度是O(N)。

但问题是这里有40亿个数，若是我们要将这些数全部加载到内存当中，那么将会占用16G的空间，空间消耗是很大的。因此从空间消耗来看，上面这两种方法实际都是不可行的。

我们看一下下面这种思想：

实际在这个问题当中，我们只需要判断一个数在或是不在，即只有两种状态，那么我们可以用一个比特位来表示数据是否存在，如果比特位为1则表示存在，比特位为0则表示不存在。比如：

无符号整数总共有232个，因此记录这些数字就需要232个比特位，也就是512M的内存空间，内存消耗大大减少。

【概念】

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

就像上面叙述的那样，通过比特位中存放的是1或者是0，来确定某个数是否存在，比如我们在位图中查找7这个数字，首先我们找到7这个数字对应的比特位，为1则存在，反之不存在。至于如何将7对应的位置变为1，以及如何开辟足够的比特位来标记数据是否存在，都会在下面的实现环节进行讲解。

8.2【位图的使用】

1、【定义方式】

//三种定义方式
	bitset<16> bs1; //0000000000000000,方式一： 构造一个16位的位图，所有位都初始化为0。
	bitset<16> bs2(0xfa5); //0000111110100101,方式二： 构造一个16位的位图，根据所给值初始化位图的前n位。
	bitset<16> bs3(string("10111001")); //0000000010111001,方式三： 构造一个16位的位图，根据字符串中的0/1序列初始化位图的前n位。

2、【函数接口】

bitset中常用的成员函数如下：

使用示例：

void use_of_bitset()
{

	bitset<8> bs;
	bs.set(2); //设置第2位
	bs.set(4); //设置第4位
	cout << bs << endl; //00010100

	bs.flip(); //反转所有位
	cout << bs << endl; //11101011
	cout << bs.count() << endl; //6

	cout << bs.test(3) << endl; //1

	bs.reset(0); //清空第0位
	cout << bs << endl; //11101010

	bs.flip(7); //反转第7位
	cout << bs << endl; //01101010

	cout << bs.size() << endl; //8

	cout << bs.any() << endl; //1

	bs.reset(); //清空所有位
	cout << bs.none() << endl; //1

	bs.set(); //设置所有位
	cout << bs.all() << endl; //1
}

注意： 使用成员函数set、reset、flip时，若指定了某一位则操作该位，若未指定位则操作所有位。

3、【bitset运算符的使用】

bitset中>>、<<运算符的使用
bitset容器对>>、<<运算符进行了重载，我们可以直接使用>>、<<运算符对biset容器定义出来的对象进行输入输出操作。

int main()
{
	bitset<8> bs;
	cin >> bs; //10110
	cout << bs << endl; //00010110
	return 0;
}

bitset中赋值运算符、关系运算符、复合赋值运算符、单目运算符的使用

bitset容器中不仅对赋值运算符和一些关系运算符进行了重载，而且对一些复合赋值运算符和单目运算符也进行了重载，我们可以直接使用这些运算符对各个位图进行操作。

包括如下运算符：

• 赋值运算符：=。
• 关系运算符：==、!=。
• 复合赋值运算符：&=、|=、^=、<<=、>>=。
• 单目运算符：~。

int main()
{

	bitset<8> bs1(string("10101010"));
	bitset<8> bs2(string("10101010"));
	bs1 >>= 1;
	cout << bs1 << endl; //01010101

	bs2 |= bs1;
	cout << bs2 << endl; //11111111
	return 0;
	
}

bitset中位运算符的使用

bitset容器中同时也对三个位运算符进行了重载，我们可以直接使用&、|、^对各个位图进行操作。

int main()
{
	bitset<8> bs1(string("10101010"));
	bitset<8> bs2(string("01010101"));

	cout << (bs1 & bs2) << endl; //00000000
	cout << (bs1 | bs2) << endl; //11111111
	cout << (bs1 ^ bs2) << endl; //11111111
	return 0;
	
}

bitset中[ ]运算符的使用。
bitset容器中对[ ]运算符进行了重载，我们可以直接使用[ ]对指定位进行访问或修改。

int main()
{

	bitset<8> bs(string("00110101"));
	cout << bs[0] << endl; //1
	bs[0] = 0;
	cout << bs << endl; //00110100
	return 0;
}

8.3【位图的模拟实现】

1、【构造函数】

在构造位图时，我们需要根据所给位数N，创建一个N位的位图，并且将该位图中的所有位都初始化为0。

一个整型有32个比特位，因此N个位的位图就需要用到N/32个整型，但是实际我们所需的整型个数是N/32+1，因为所给非类型模板参数N的值可能并不是32的整数倍。

例如，当N为40时，我们需要用到两个整型，即40/32+1=2。

//构造函数
		bitset()
		{
			_bits.resize(N / 32 + 1, 0);
		}

2、【成员函数】

【set】

set成员函数用于设置位。

设置位图中指定的位的方法如下：

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位后与第 i 个整数进行或运算即可。

其中我们要知道一个整型是4个字节，8各比特位，那么结案设我们要将7这个位标记为1， 那么我们要先计算出7在位图的位置，计算方式是，让7/32得到7在位图的第0个整数（也就是在第一个32位之中），即i为0，在用72得到7在第i个整数的第7位，即j为7，所以将第0个整数的第7位设置为1即可，主要方法就是，将1左移7位以后，与第0个整数进行或运算。

代码：

	    void set(size_t pos)
		{
			assert(pos < N);

			//算出pos映射的位在第i个整数的第j个位
			int i = pos / 32;
			int j = pos % 32;
			_bits[i] |= (1 << j); //将该位设置为1（不影响其他位）
		}

【reset】

reset成员函数用于清空位。

清空位图中指定的位的方法如下：

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。

这里假设将上面设置的7进行清空位操作那么只需要将1左移7位，进行按位取反，再与位图进行按位与运算即可。

代码如下：

//清空位
		void reset(size_t pos)
		{
			assert(pos < N);

			//算出pos映射的位在第i个整数的第j个位
			int i = pos / 32;
			int j = pos % 32;
			_bits[i] &= (~(1 << j)); //将该位设置为0（不影响其他位）
		}

【filp】

flip成员函数用于反转位。

反转位图中指定的位的方法如下：

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位后与第 i 个整数进行异或运算即可。

代码如下：

//反转位
void flip(size_t pos)
{
	assert(pos < N);

	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] ^= (1 << j); //将该进行反转（不影响其他位）
}

【test】

test成员函数用于获取位的状态。

获取位图中指定的位的状态的方法如下：

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位后与第 i 个整数进行与运算得出结果。
3. 若结果非0，则该位被设置，否则该位未被设置。

代码如下：

		//获取位的状态
		bool test(size_t pos)
		{
			assert(pos < N);

			//算出pos映射的位在第i个整数的第j个位
			int i = pos / 32;
			int j = pos % 32;
			if (_bits[i] & (1 << j)) //该比特位被设置
				return true;
			else //该比特位未被设置
				return false;
		}

【size】

size成员函数用于获取位图中可以容纳的位的个数。

我们直接将所给非类型模板参数进行返回即可。

//获取可以容纳的位的个数
size_t size()
{
	return N;
}

【count】

count成员函数用于获取位图中被设置的位的个数。

获取位图中被设置的位的个数，也就是统计位图中1的个数，我们只需要依次统计每个整数二进制中1的个数，然后将其相加即可得到位图中1的个数。

统计二进制中1的个数的方法如下：

1. 将原数 n 与 n - 1 进行与运算得到新的 n 。
2. 判断 n 是否为0，若 n 不为0则继续进行第一步。

如此进行下去，直到 n 最终为0，此时该操作进行了几次就说明二进制中有多少个1。

因为该操作每进行一次就会消去二进制中最右边的1，例图如下：

代码如下：

//获取被设置位的个数
size_t count()
{
	size_t count = 0;
	//将每个整数中1的个数累加起来
	for (auto e : _bits)
	{
		int num = e;
		//计算整数num中1的个数
		while (num)
		{
			num = num&(num - 1);
			count++;
		}
	}
	return count; //位图中1的个数，即被设置位的个数
}

【any】

any成员函数用于判断位图中是否有位被设置。

我们只需遍历每一个整数，若这些整数全部都为0，则说明位图中没有位被设置过。
虽然位图可能并没有包含最后一个整数的全部比特位，但由于我们构造位图时是将整数的全部比特位都初始化成了0，因此不会对此处判断造成影响。

代码如下：

//判断位图中是否有位被设置
bool any()
{
	//遍历每个整数
	for (auto e : _bits)
	{
		if (e != 0) //该整数中有位被设置
			return true;
	}
	return false; //全部整数都是0，则没有位被设置过
}

【all】

all成员函数用于判断位图中是否全部位都被设置。

判断过程分为两步：

1. 先检查前n-1个整数的二进制是否为全1。
2. 再检查最后一个整数的前N2个比特位是否为全1。

需要注意的是，如果位图没有包含最后一个整数的全部比特位，那么最后一个整数的二进制无论如何都不会为全1，所以在判断最后一个整数时应该只判断位图所包含的比特位。

none

none成员函数用于判断位图中是否全部位都没有被设置。

位图中是否全部位都没有被设置，实际上就是位图中有位被设置的反面，因此none成员函数直接调用any成员函数，然后将返回值取反后再进行返回即可。

//判断位图中是否全部位都没有被设置
bool none()
{
	return !any();
}

【打印函数】

以实现一个打印函数，便于检查我们上述代码的正确性，打印位图时遍历位图所包含的比特位进行打印即可，在打印位图的过程中可以顺便统计位图中位的个数count，将count与我们传入的非类型模板参数N进行比较，可以判断位图大小是否是符合我们的预期。

//打印函数
		void Print()
		{
			int count = 0;
			size_t n = _bits.size();
			//先打印前n-1个整数
			for (size_t i = 0; i < n - 1; i++)
			{
				for (size_t j = 0; j < 32; j++)
				{
					if (_bits[i] & (1 << j)) //该位被设置
						cout << "1";
					else //该位未被设置
						cout << "0";
					count++;
				}
			}
			//再打印最后一个整数的前N2位
			for (size_t j = 0; j < N % 32; j++)
			{
				if (_bits[n - 1] & (1 << j)) //该位被设置
					cout << "1";
				else //该位未被设置
					cout << "0";
				count++;
			}
			cout << " " << count << endl; //打印总共打印的位的个数
		}

8.4【位图的应用】

题目一：给定100亿个整数，设计算法找到只出现一次的整数。

我们标记整数时可以将其分为三种状态：

1. 出现0次。
2. 出现1次。
3. 出现2次及以上。

一个位只能表示两种状态，而要表示三种状态我们至少需要用两个位，因此我们可以开辟两个位图，这两个位图的对应位置分别表示该位置整数的第一个位和第二个位。

我们可以将着三种状态分别定义为00、01、10，此时当我们读取到重复的整数时，就可以让其对应的两个位按照00→01→10的顺序进行变化，最后状态是01的整数就是只出现一次的整数。

为了方便演示，下面我们直接从vector中读取若干整数进行模拟处理：

#include <iostream>
#include <vector>
#include <assert.h>
#include <bitset>
using namespace std;

int main()
{
	//此处应该从文件中读取100亿个整数
	vector<int> v{ 12, 33, 4, 2, 7, 3, 32, 3, 3, 12, 21 };
	//在堆上申请空间
	bitset<4294967295>* bs1 = new bitset<4294967295>;
	bitset<4294967295>* bs2 = new bitset<4294967295>;
	for (auto e : v)
	{
		if (!bs1->test(e) && !bs2->test(e)) //00->01
		{
			bs2->set(e);
		}
		else if (!bs1->test(e) && bs2->test(e)) //01->10
		{
			bs1->set(e);
			bs2->reset(e);
		}
		else if (bs1->test(e) && !bs2->test(e)) //10->10
		{
			//不做处理
		}
		else //11（理论上不会出现该情况）
		{
			assert(false);
		}
	}
	for (size_t i = 0; i < 4294967295; i++)
	{
		if (!bs1->test(i) && bs2->test(i)) //01
			cout << i << endl;
	}
	return 0;
}

需要注意的是：

存储100亿个整数大概需要40G的内存空间，因此题目中的100亿个整数肯定是存储在文件当中的，代码中直接从vector中读取数据是为了方便演示。
为了能映射所有整数，位图的大小必须开辟为232位，也就是代码中的4294967295，因此开辟一个位图大概需要512M的内存空间，两个位图就要占用1G的内存空间，所以代码中选择在堆区开辟空间，若是在栈区开辟则会导致栈溢出。

题目二：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？

方案一：（一个位图需要512M内存）

1. 依次读取第一个文件中的所有整数，将其映射到一个位图。
2. 再读取另一个文件中的所有整数，判断在不在位图中，在就是交集，不在就不是交集。

方案二：（两个位图刚好需要1G内存，满足要求）

1. 依次读取第一个文件中的所有整数，将其映射到位图1。
2. 依次读取另一个文件中的所有整数，将其映射到位图2。
3. 将位图1和位图2进行与操作，结果存储在位图1中，此时位图1当中映射的整数就是两个文件的交集。

说明一下： 对于32位的整型，无论待处理的整数个数是多少，开辟的位图都必须有 2 32 2^32个比特位，也就是512M，因为我们要保证每一个整数都能够映射到位图当中，因此这里位图的空间消耗是固定的。

题目三：一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数。

该题目和题目一的方法是一样的，在该题目中我们标记整数时可以将其分为四种状态：

1. 出现0次。
2. 出现1次。
3. 出现2次。
4. 出现2次以上。

一个整数要表示四种状态也是只需要两个位就够了，此时当我们读取到重复的整数时，就可以让其对应的两个位按照00→01→10→11的顺序进行变化，最后状态是01或10的整数就是出现次数不超过2次的整数。

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

int main()
{
	vector<int> v{ 12, 33, 4, 2, 7, 3, 32, 3, 3, 12, 21 };
	//在堆上申请空间
	bitset<4294967295>* bs1 = new bitset<4294967295>;
	bitset<4294967295>* bs2 = new bitset<4294967295>;
	for (auto e : v)
	{
		if (!bs1->test(e) && !bs2->test(e)) //00->01
		{
			bs2->set(e);
		}
		else if (!bs1->test(e) && bs2->test(e)) //01->10
		{
			bs1->set(e);
			bs2->reset(e);
		}
		else if (bs1->test(e) && !bs2->test(e)) //10->11
		{
			bs2->set(e);
		}
		else //11->11
		{
			//不做处理
		}
	}
	for (size_t i = 0; i < 4294967295; i++)
	{
		if ((!bs1->test(i) && bs2->test(i)) || (bs1->test(i) && !bs2->test(i))) //01或10
			cout << i << endl;
	}
	return 0;
}

总结

看到这里本篇博客就结束了，其实除了STL中的空间配置器，没有特别说明以外，仿函数，配接器，迭代器，容器，算法，我们都有所了解，如果大家对空间配置器有兴趣，还请自行学习，下面我将附上一张总结图。

---

............................................................................................醒来后哭着笑了，醒来后继续活着

                                                                                                                     ————《醒来》