【CPP】CPP的STL(前篇)

这里是oldking呐呐,感谢阅读口牙!先赞后看,养成习惯!
个人主页:oldking呐呐
专栏主页:深入CPP语法口牙

12 STL(前篇)

12.1 什么是STL

• 简单来说:CPP在有了模板之后,很多重复性质的代码就不需要自己手撕很多遍了,甚至说有前人做了一个库,把常见的算法,数据结构啥的放进库里面,这些数据结构,算法啥的全都采用了模板类和模板函数的形式,使得这个库里的代码复用率极高,况且写这个库的人都是大佬级别的大佬,效率也很不错,所以在CPP实际开发中,就不需要自己再造轮子了,调用这个库里的玩意就行

• STL目前有两个需要去学习的版本,一个是微软家的PJ版,一个是GCC(Linux)的SGI版,这俩调用的效果都是一样的,只是底层不一样,需要了解一下

• STL的六大组件

  • 容器
  • 算法
  • 迭代器
  • 函数对象
  • 适配器
  • 分配器

• 这些组件咱日后都会聊到

12.2 string类

12.2.1 什么是string

• 简单来说,string类就是原来的字符串,底层就是字符顺序表,用来存储和管理字符数组,只不过不需要再去用头文件中的函数,类中就已经内置了很多成员函数(或者说方法)

• 内存开辟在堆上

• 如果要使用类,需要包头文件

#include<string>
1

12.2.2 string类的构造函数

int main()
{
	string st1; //默认构造
	string st2("oldkingnana"); //默认构造
	string st3(st2); //拷贝构造

	//因为类里面已经重载好了<<和>>,所以我们可以直接拿来用
	cout << st1 << endl; //因为调用了没有参数的默认构造，所以里面就只有'\0'
	cout << st2 << endl;
	cout << st3 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 以上三个构造函数都是比较常用的几个,熟悉一下就好了,剩下的知道有这么回事就行,忘了再查

int main()
{
	string s1("oldkingnana");
	
	//这个构造是取子字符串,从你想开始的地方(第二个参数,且是下标),取几个字符到s2里(第三个参数是len,长度)
	string s2(s1, 7, 2); 

	//这个构造函数和上面一样,第三个参数是有缺省值的,所以不填的话会默认帮你一直取到最后一个字符
	string s3(s1, 7);
	//(值得一提的是,如果第三个参数超长度了,效果和用缺省值的这个是一样的)

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

	//这个构造是取字符串的前n(第二个参数)个字符
	string s4("oldkingnana", 7);

	//这个构造是初始化成n(第一个参数)个'X'(第二个参数,类型为字符)
	string s5(10, 'H');

	cout << s4 << endl;
	cout << s5 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

12.2.3 string类的析构函数

• 其实没啥好说的,就是释放资源,也没有很多变种,就一个类型,详见图
  

12.2.4 string类的[]重载

• string类中特地重载了两个[],可以像字符串一样访问其中的字符

• 因为返回的是引用,所以可以直接更改其中的值

int main()
{
	string s1("oldkinganan");

	s1[1] = 'H';

	cout << s1 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10

• 当然,要是加了const当然就不能访问啦

• 底层里是通过断言提示越界的,所以一旦越界了就会报错

12.2.5 string类的迭代器的简单了解

• 一般情况下,我们遍历string可以用[]+下标去遍历

int main()
{
	string s1("oldkingnana");

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

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 除此之外我们还可以通过一个叫迭代器的玩意来遍历string类

	string::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
1
2
3
4
5
6
7

• 什么是迭代器?我们可以暂时理解为是一个指针,我们说,string的底层就是字符顺序表

• 我们先来解构一下上面的代码

	string::iterator it = s1.begin();
//  |     类型     |变量名|需要赋的值|   
// |string里的迭代器| 名  |返回string最开始字符的迭代器|
1
2
3

	//s1.end()用于返回string最后一个有效字符的下一个字符的迭代器,即'\0'的迭代器

	//当it不等于`\0`的迭代器的时候就继续循环
	while (it != s1.end())
	{
		cout << *it << " "; //像指针解引用一样使用迭代器
		it++; //同样可以像指针一样++
	}
1
2
3
4
5
6
7
8

• 虽然迭代器使用起来和指针一样,但底层是不是指针,这个要取决于当前编译器标准库里的底层是怎么写的,当然,即便它不是指针,我们只需要重载*或者++等等运算符,就能实现指针一样的效果

• 迭代器最最厉害的地方在于,包括string,所有的容器都可以用迭代器实现遍历或者访问,并且访问方式都是一样的,极大地降低了学习成本

12.2.6 auto关键字

• 严格来说auto不应该现在拿出来说,因为auto根本不是咱的重点,但他可以搭配另一个东西使用,所以咱现在提一下

• 虽然在C中就有了auto这个关键字,但其功能太垃圾所以存在感极低,几乎不用,所以在C++11后被改成了一个看起来更高级的关键字

• auto最厉害的点在于它可以自动识别几乎任何类型,甚至是迭代器等等

int main()
{
	string s1("oldkingnana");

	//迭代器类型写起来很长很不方便
	string::iterator it = s1.begin();

	//auto短小写着容易
	auto ait = s1.begin();

	cout << *ait << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• auto会自动识别类型,向上面的例子就是auto识别了返回值为迭代器类型,于是变量ait的类型就是string::iterator

• 当然,auto还可以识别其他的类型,等等,不过一般情景,都是因为它比较短小才写他

• 虽然可以自动识别类型,而且短小好写,但缺点就是可读性很差,看起来很膈应

• 所以一般auto都会用在另外一个场景叫做"范围for"

• 注意几个要点:

  1. 用了auto的变量一定要初始化,否则无法识别类型
  2. auto不可以用在函数参数上
  3. 虽然auto可以用在返回值上,但极其不推荐,多个带auto的函数嵌套会导致找返回值的具体类型变得极为困难
  4. auto不支持形如auto a = 10, b = 1.0;的形式,但auto a = 10, b = 1;可以
  5. auto后面可以跟*和&
  6. auto不能用来定义数组

• 几个要点了解一下就行,一般很少用auto的

12.2.7 范围for

• 范围for提供了一种遍历容器或者数组的极为方便的方式

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		cout << arr[i] << endl;
	}

	cout << "---------------" << endl;

	//CPP用范围for访问arr
	for (auto it : arr)
	{
		cout << it << endl;
	}
1
2
3
4
5
6
7
8
9
10
11
12

• 这个范围for会帮我们依次取出数组中的值,第一次取第一个值,第二次取第二个值这样以此类推,所以每次循环it所代表的值都不一样

• 范围for和迭代器很相似,但又不太一样

int main()
{
	string s1("oldkingnana");
	for (string::iterator it = s1.begin(); it != s1.end(); it++)
	{
		*it += 2;
	}
	cout << s1 << endl;

	string s2("oldkingnana");
	for (auto it : s2)
	{
		it += 2;
	}
	cout << s2 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 不难发现,虽然我的确对范围for里的it做出了更改,但却丝毫影响不到原始对象s2,因为从底层来讲,范围for就是用的迭代器,但范围for的it只是接受了迭代器解引用后的值得拷贝,使得修改范围for的it根本改不了s2的值,而迭代器本身就几乎是照着指针写的,所以能够直接修改s1的值

• 如果想要范围for的it能做到修改原先对象的值,就得加&,让it接收其引用而不是拷贝

int main()
{
	string s2("oldkingnana");
	for (auto& it : s2)
	{
		it += 2;
	}
	cout << s2 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

• 还有一个点,不难发现,这里范围for中it的类型是auto,意味着用它遍历咱不需要考虑变量类型,可以更加无脑地遍历,当然,咱也可以考虑变量类型

int main()
{
	string s2("oldkingnana");
	for (char& it : s2)
	{
		it += 2;
	}
	cout << s2 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

• 虽然可以这么写,但实际写的时候用auto还是会更多一些,毕竟少动脑子嘛,简单遍历,不用考虑底层的遍历就可以用范围for + auto,考虑底层或者复杂的遍历的话的话就用迭代器就行了

12.2.8 反向迭代器 – reverse

• 反向迭代器是一种迭代器类型,我们可以看以下情景

int main()
{
	string s1("oldkingnana");

	string::reverse_iterator it = s1.rbegin();
	while (it != s1.rend())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 顾名思义,就是用来反向迭代/遍历容器的
• 对于反向迭代器来说,倒过来遍历才算是正向,所以对于it咱才会使用++

12.2.9 const迭代器

• 对于只读对象,咱们一样可以使用const迭代器进行遍历

int main()
{
	const string s1("oldkingnana");

	//const正向迭代器
	string::const_iterator cit = s1.cbegin();
	while (cit != s1.cend())
	{
		cout << *cit << " ";
		cit++;
	}
	cout << endl;

	//const反向迭代器
	string::const_reverse_iterator crit = s1.crbegin();
	while (crit != s1.crend())
	{
		cout << *crit << " ";
		crit++;
	}
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• const迭代器不允许用户修改迭代器指向的值,但迭代器本身可以修改
  

• 被const修饰的迭代器不允许用户修改迭代器本身的值,但可以修改迭代器指向的值
  

• 被const修饰的const迭代器不允许用户修饰迭代器本身的值,也不允许用户修改迭代器指向的值
  

12.2.10 CPPstring类的容量开辟机制

• capacity()可以用来返回容量,具体可看下一小节

• 我们先简单创建一个string类对象

int main()
{
	string s1("oldkingnana");
	return 0;
}
1
2
3
4
5

• 通过调试可以看到更多的底层细节
• PS:VS在调试中为了了方便用户查看,展开之后最开始看到的并不是底层细节,底层细节被包括在了"原始视图"中

• 其中有个叫_Buf的成员变量

• 底层上,如果我们在string类中字符的数据(包括'\0')小于等于16字节,就会放在开辟在栈上的_Buf中,如果string类中字符的数据(包括'\0')大于16字节,就会挪到堆中,指向堆的指针叫_Ptr,咱们也可以在监视中看到

• 现在我们修改一下代码

int main()
{
	string s1("oldkingnana");

	//+=可以用来扩容充字符串
	s1 += "HHHHHHHHHHHHHHHHHHHHHHHHHH";

	return 0;
}
1
2
3
4
5
6
7
8
9

• 我们能看到修改之后的内容被挪到堆上去了

• 现在我们再修改一下代码

• 在以下的这部分代码中,我们显示的将string类容量的变化过程打印出来,并结合监视窗口,以便了解开辟机制

int main()
{
	string s1("oldkingnana");

	int capa = s1.capacity();
	cout << capa << endl;

	for (int i = 0; i < 1000; i++)
	{
		s1 += "HHHHHHHHHHHHHH";

		if (capa != s1.capacity())
		{
			capa = s1.capacity();
			cout << capa << endl;
		}
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 最开始,容量为15,在打印15的时候,数据还在_Buf上,也就是在栈上
  

• 当我们添加字符后总容量超过了15,于是编译器就把数据数据从栈的成员变量里挪到堆上了,通过图上也不难发现,后期在堆上容量大小的增长趋势是以几乎1.5倍的速度增长的,而从栈挪到堆上的增长幅度为2倍,也就是说,在VS2022下,string类底层容量的开辟机制是:第一次扩容以2倍扩容,后面所有的扩容以1.5倍扩容

• PS:为什么不是标准的1.5倍/2倍扩容?因为这里的capacity只计算了有效字符,如果把无效字符'\0'也算上的话,那就是标准的2倍扩容和1.5倍扩容

  • 第一次:(15 + 1) * 2 = 31 + 1
  • 第二次:(31 + 1) * 1.5 = 47 + 1
  • …

• 而且不难发现,在VS2022下,不管我们如果扩容string类,这个string类开辟的大小始终只有固定大小
  

• 值得一提的是,在linux,G++4.8编译器下,所有的数据默认都开辟在堆上,没有_Buf这一说,不初始化对象的话,最开始的容量是0,有了第一个字符之后为1,后面扩容均以2倍扩容的机制扩容

12.2.11 string类关于容量的成员函数

• size()可以返回其长度

int main()
{
	string s1("oldkingnana");

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

	return 0;
}
1
2
3
4
5
6
7
8

• 除了size(),lenth()一样可以返回长度,但stl为了统一使用规范,在其他的树什么的里面就没有lenth(),对一树讲lenth()也不太合理对吧,所以一般都用size(),不过lenth()依旧因为向前兼容的原因而被保留了下来

• capacity()可以用来返回容量

int main()
{
	string s1("oldkingnana");

	cout << s1.capacity() << endl; //返回容量
	
	return 0;
}
1
2
3
4
5
6
7
8

• 前面的都是小喽喽,接下来才是重头戏,我们来讲一个重量级的函数

• reserve – 储备

• 先来看以下代码

int main()
{
	string s1;
	cout << s1.capacity() << endl;

	s1.reserve(100);
	cout << s1.capacity() << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10

• 不难发现,当我们试图扩容100个size的时候,编译器自动给我们扩到了111个size

• reserve()在扩容上有规定,CPP规定,reverse()扩容的时候,至少得扩到用户标定的那么大,可以更大,但不能小,VS2022可能是为了取整对齐或者其他什么的,就扩到了111个size

• 在G++4.8中,用户指定扩100,编译器就只会扩100,不会额外扩

• 再来看以下代码

int main()
{
	string s1;
	cout << s1.capacity() << endl;

	s1.reserve(100); //扩到100
	cout << s1.capacity() << endl;

	s1 += "oldkingnana"; //存一个字符串进去

	s1.reserve(5); //试图缩容到5
	cout << s1.capacity() << endl;

	s1.reserve(40); //试图缩容到40
	cout << s1.capacity() << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 不难看出来,在VS2022下缩容,编译器并不会执行

• CPP规定,如果在reserve()中输入的数字小于现有字符串的长度,允许缩容,但容量大小至少要保证不会修改现有字符串的内容

• 至于如果情况是输入的数字大于现有字符串的长度,又小于现有容量的这种缩容,编译器可以根据自身优化方式进行,不做强制要求

• 在G++4.8下,扩容因为按2倍扩的原因,会向2的指数倍对齐,如果输入的数字小于字符串的长度的话,会直接缩到现有字符串的长度,如果是输入的数字大于现有字符串的长度,又小于现有容量的这种缩容,G++也会毫不犹豫地缩到用户指定的大小去

• clear – 清除

• clear一般只会清除数据,不会清除容量

int main()
{
	string s1;
	cout << s1.capacity() << endl;

	s1.reserve(100);
	cout << s1.capacity() << endl;

	s1 += "oldkingnana";

	s1.reserve(5);
	cout << s1.capacity() << endl;

	s1.reserve(40);
	cout << s1.capacity() << endl;

	s1.clear();
	cout << s1.capacity() << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 可以看到,VS2022下是不清容量的,只清除数据,包括在g++4.8下也是不清空间的

• shrink_to_fit() – 缩容

• 这个缩容不像reserve()的缩容,reserve()的缩容是不受约束力的,编译器可以缩也可以不缩,但shrink_to_fit()向编译器发送的请求是一定具有约束力的,编译器一定会缩容,但缺点是不能传任何值进去,不能指定缩容的大小,具体大概是缩到大于等于size,一般就是size的大小,当然可能略大于size,这个取决于编译器的底层

int main()
{
	string s1("oldkingnana");

	s1.reserve(100);
	cout << s1.capacity() << endl;

	s1.shrink_to_fit();
	cout << s1.capacity() << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

12.2.12 string类关于字符串修改的成员函数

• operator+=

int main()
{
	string s1("oldkingnana");

	string s2("HHH");

	//string类重载了+=
	s1 += s2; 
	s1 += "///";
	s1 += 'h';

	cout << s1 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• push_back

int main()
{
	string s1("oldkingnana");

	//尾插单个字符
	s1.push_back('H');

	return 0;
}
1
2
3
4
5
6
7
8
9

• insert()
• insert()允许在任意位置插入

int main()
{
	string s1("oldkingnana");

	string s2("HHH");

	//插入
	s1.insert(0, s2);

	cout << s1 << endl;

	s1.insert(0, "hhhh");

	cout << s1 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 一般咱就用insert()头插(尽量少头插,效率太低),其他很少用

• erase()

• erase()允许用户删除某个字符/某串字符

int main()
{
	string s1("oldkingnana");

	string s2("HHH");

	//删除
	s1.erase(0, 2);
	cout << s1 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

• erase()一样不推荐用在头删,消耗太大了

• replace – 替换

• replace允许用户用单字符/字符串/字符串的一部分替换另一个字符串中的一部分

int main()
{
	string s1("oldkingnana");

	s1.replace(0, 2, "HHH");
	cout << s1 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9

• 替换如果涉及到字符串前/后移的话一样很吃性能,谨慎使用

• swap() – 交换

• swap()允许用户交换两个string对象的内容(所有内容)

int main()
{
	string s1("oldkingnana");

	string s2("HHH");

	s1.swap(s2);
	cout << s1 << endl;
	cout << s2 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 因为string对象比较大的部分都在堆上,交换只用交换指针,所以swap()效率非常高

12.2.13 string类的其他成员函数

• c_str
• c_str允许用户返回底层字符串的指针,用于兼容C语言写的很妥协的函数

int main()
{
	string s1("oldkingnana");

	printf("%s", s1.c_str());

	return 0;
}
1
2
3
4
5
6
7
8

• find()系列

• find()允许用户正向查找第一个用户所需要找的字符,返回的是第一个匹配字符的下标

• rfind()允许用户逆向查找第一个用户所需要找的字符,返回的是第一个匹配字符的下标

• find_first_of允许用户在一个字符串里正向查找另一个字符串所包含的所有字符,返回的是第一个匹配字符的下标

• find_last_of允许用户在一个字符串里逆向查找另一个字符串所包含的所有字符,返回的是第一个匹配字符的下标

• find_first_not_of允许用户在一个字符串里正向查找另一个字符串所不包含的所有字符,返回的是第一个匹配字符的下标

• find_last_not_of允许用户在一个字符串里逆向查找另一个字符串所不包含的所有字符,返回的是第一个匹配字符的下标

int main()
{
string s1(“oldkingnana”);

cout << s1.find('a') << endl;
cout << s1.rfind('a') << endl;
cout << s1.find_first_of("aeiou") << endl;
cout << s1.find_last_of("aeiou") << endl;
cout << s1.find_first_not_of("aeiou") << endl;
cout << s1.find_last_not_of("aeiou") << endl;

return 0;
1
2
3
4
5
6
7
8

}

12.2.14 string类的其他非成员函数

• operator+
• operator+重载在全局,目的是为了兼容字符串加string

int main()
{
	string s1("oldkingnana");

	string s2 = "HH" + s1;
	string s3 = s1 + "HH";

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

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 比较运算符重载
  

• getline()

• 标准输入输出流中,输入会因为有空格而停止

int main()
{
	string s1;
	cin >> s1;
	cout << s1 << endl;

	return 0;
}
1
2
3
4
5
6
7
8

• CPP提供了一个函数,让输入的时候规避空格,只以换行作为分隔

int main()
{
	string s1;
	
	getline(cin, s1);

	cout << s1 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10

• 它甚至可以允许你自己定义终止符

int main()
{
	string s1;
	
	getline(cin, s1, 'e');

	cout << s1 << endl;

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11

12.3 vector – 顺序表

• vector 正经翻译应该是"向量",但实际上指的是"顺序表"

12.3.1 对于vector的简单介绍

• 简单来说vector就是一个模板类,模板参数包含一个类型(T)和一个空间配置器(Alloc),空间配置器暂且不用管,咱后面的章节会提到

12.3.2 vector的实例化和遍历

void vectortest1()
{
	vector<int> v1; // 无参构造
	vector<int> v2(10, 2); // 初始化10个2
	vector<int> v3(v2.begin() + 1, v2.end() - 1); // 用迭代器初始化(其他类型迭代器也可以)
	vector<int> v4(v3); // 拷贝构造
 
	for (auto it : v1) // vector也可以用范围for遍历
	{
		cout << it << " ";
	}
	cout << endl;

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

	for (auto it : v3)
	{
		cout << it << " ";
	}
	cout << endl;

	for (auto it : v4)
	{
		cout << it << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

void vectortest2()
{
	vector<int> v1(10, 2);

	for (size_t i = 0; i < v1.size(); i++) //用[]加下标遍历
	{
		cout << v1[i] << " ";
	}
	cout << endl;

	for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) //用迭代器遍历
	{
		cout << *it << " ";
	}
	cout << endl;

	for (auto it : v1) //用范围for遍历
	{
		cout << it << " ";
	}
	cout << endl;

	for (const auto& it : v1) //加引用可以减少拷贝构造,对于自定义类型来说能提升效率
	{
		cout << it << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

12.3.3 vector的扩容机制

12.3.3.1 reserve手动扩容机制

void vectortest3()
{
	vector<int> v1(10, 1);
	cout << v1.capacity() << endl;

	v1.reserve(100);
	cout << v1.capacity() << endl;

	v1.reserve(30);
	cout << v1.capacity() << endl;

	v1.reserve(5);
	cout << v1.capacity() << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 可以看到,vector中用reserve扩容机制和string是一样的,手动扩就一定会扩(vector不会像string一样对齐),但用reserve缩容是和string完全不一样,string会有缩容请求(虽然不受约束),但vector中用reserve缩容是一定不会有请求的,意思是官方规定不能缩

  • string - reserve - 缩不缩随意,但不能删数据
  • vector - reserve - 禁止缩容

• CPP规定vector中用reserve手动扩容至少要开出用户输入的大小的空间,至于要不要向上对齐啥的,随意随意

12.3.3.2 自动扩容机制

void vectortest3()
{
	vector<int> v1(10, 1);
	cout << v1.capacity() << endl;

	size_t capa = v1.capacity();

	for (int i = 0; i < 1000; i++)
	{
		v1.push_back(i);

		if (capa != v1.capacity())
		{
			capa = v1.capacity();
			cout << v1.capacity() << endl;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 不难发现这就是一个标准的1.5倍扩容(VS2022)
• 而在Linux的g++4.8下则是标准的2倍扩容

12.3.4 vector的resize机制

• 我们先看文档中的定义

• resize即重新设定size

  • 如果用户传进的n小于size,则会缩减size至n,只保留前n个数据,其余的数据全部丢弃
  • 如果用户传进的n大于size,则会不断尾插用户规定的值(第二个参数),直至使size等于n,如果用户没有手动规定值,就用对象的默认构造创建默认对象来尾插
  • 如果capacity不够了就会再开空间

• 补充:value_type其实就是模板中类型T的typedef
  

class A
{
public:
	A(int val1 = 114, double val2 = 5.14)
		:_val1(val1)
		,_val2(val2)
	{
	}

	void print()
	{
		cout << _val1 << ',' << _val2 << "  ";
	}

private:
	int _val1;
	double _val2;
};


void vectortest4()
{
	//用自定义类型创建vector
	vector<A> v1{ {1, 1}, {4, 5}, {1, 4} };
	cout << "size:" << v1.size() << ' ';
	cout << "capa:" << v1.capacity() << ' ';
	cout << endl;

	for (auto it : v1)
	{
		it.print();
	}
	cout << endl;
	cout << endl;

	//缩size到1
	v1.resize(1);
	cout << "size:" << v1.size() << ' ';
	cout << "capa:" << v1.capacity() << ' ';
	cout << endl;

	for (auto it : v1)
	{
		it.print();
	}
	cout << endl;
	cout << endl;

	//扩size到2,手动给值
	v1.resize(2, {6, 6.6});
	cout << "size:" << v1.size() << ' ';
	cout << "capa:" << v1.capacity() << ' ';
	cout << endl;

	for (auto it : v1)
	{
		it.print();
	}
	cout << endl;
	cout << endl;

	//扩size到10,不手动给值
	v1.resize(10);
	cout << "size:" << v1.size() << ' ';
	cout << "capa:" << v1.capacity() << ' ';
	cout << endl;

	for (auto it : v1)
	{
		it.print();
	}
	cout << endl;
	cout << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

12.3.5 vector的头尾插删

void vectortest5()
{
	// 实例化
	vector<int> v1{1, 2, 3, 4, 5, 6, 7};
	for (auto it : v1)
	{
		cout << it;
	}
	cout << endl;

	// 尾插8
	v1.push_back(8);
	for (auto it : v1)
	{
		cout << it;
	}
	cout << endl;

	//尾删
	v1.pop_back();
	for (auto it : v1)
	{
		cout << it;
	}
	cout << endl;

	// 头插0
	v1.insert(v1.begin(), 0); //insert只支持迭代器
	for (auto it : v1)
	{
		cout << it;
	}
	cout << endl;

	// 头删
	v1.erase(v1.begin()); //erase也只支持迭代器
	for (auto it : v1)
	{
		cout << it;
	}
	cout << endl;

	// erase也可以用来删一个迭代器区间
	v1.erase(v1.begin() + 2, v1.end() - 2);
	for (auto it : v1)
	{
		cout << it;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

12.3.6 用vector模拟二维数组

void vectortest6()
{
	vector<vector<int>> v2{ {1,2,3},{4,5,6},{7,8,9} };

	for (auto it1 : v2)
	{
		for (auto it2 : it1)
		{
			cout << it2 << " ";
		}
		cout << endl;
	}
	cout << endl;
	
	//他甚至可以像二维数组一样访问(其实就是[]的连续调用罢了)
	cout << v2[1][1] << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

12.3.7 vector底层剖析

#include<iostream>
#include<assert.h>
#include<string>

using namespace std;

namespace oldking
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator; //迭代器
		typedef T const* const_iterator; //const迭代器

		//默认构造
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
		}

		//拷贝构造
		vector(const vector<T>& v) //构造一定要初始化
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(v.size());
			for (auto& it : v) //引用减少拷贝
			{
				push_back(it);
			}
		}

		//多个值构造
		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (n > 0)
			{
				push_back(val);
				--n;
			}
		}

		//第二个版本的多个值构造
		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (n > 0)
			{
				push_back(val);
				--n;
			}
		}

		//可以用任意容器的迭代器初始化
		//这种方式会在某些地方出现问题,比方说我想初始化10个1,例如testvector5,
		//编译器会认为这里不需要转换,很方便,就进了模板函数,而没有进上面的构造函数里
		//所以我们需要手动给编译器更好的选择,比方说在上面写另外一个更更匹配实际参数的版本
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			//注意不等于号 
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//vector<T>& operator=(const vector<T>& v)
		//{
		//	if (this != &v)
		//	{
		//		clear();

		//		reserve(v.size());
		//		for (auto it : v)
		//		{
		//			push_back(it);
		//		}
		//	}
		//	
		//	return *this;
		//}

		void swap(vector<T>& v)
		{
			//要用std的swap
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

		//现代写法
		vector<T>& operator=(vector<T> tmp)
		{
			swap(tmp);
		
			return *this;
		}

		//析构函数
		~vector()
		{
			if (_start)
			{
				delete[] _start;

				_start = nullptr;
				_finish = nullptr;
				_end_of_storage = nullptr;
			}
		}

		//返回容量
		size_t capacity() const
		{
			return (size_t)(_end_of_storage - _start);
		}

		//返回大小
		size_t size() const
		{
			return (size_t)(_finish - _start);
		}

		//清除数据，不清空间
		void clear()
		{
			_finish = _start;
		}

		//重新分配空间
		void reserve(size_t n)
		{
			iterator tmp = new T[n];
			size_t old_size = size();
			for (size_t i = 0; i < size(); i++)
			{
				// 这里必须通过手动赋值完成深拷贝,否则在需要深拷贝的场景就会出问题
				tmp[i] = _start[i];
			}
			//memcpy(__tmp, _start, size() * sizeof(T));
			//memcpy是浅拷贝,是错误代码不要使用
			
			delete[] _start;
			
			_start = tmp;
			_finish = _start + old_size;
			_end_of_storage = _start + n;
		}

		//尾插
		void push_back(const T& val)
		{
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : 4 * capacity());
			}

			*_finish = val;
			++_finish;
		}

		//尾删
		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

		//插入，迭代器
		void insert(iterator pos, const T& val)
		{
			assert(_start <= pos);
			assert(pos <= _finish);

			//注意迭代器失效
			//一旦涉及到重新分配空间的，分配空间后的迭代器我们一致认为失效，需要更新迭代器
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : 4 * capacity());
				pos = _start + len;
			}

			iterator end = _finish;
			while (pos < end)
			{
				*end = *(end - 1);
				--end;
			}

			*pos = val;
			++_finish;
		}

		//删除，迭代器
		void erase(iterator pos)
		{
			assert(_start <= pos);
			assert(pos < _finish);

			iterator begin = pos + 1;

			while (begin < _finish)
			{
				*(begin - 1) = *(begin);
				++begin;
			}

			--_finish;
		}

		//空间分配
		void resize(size_t n, T val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while(_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

		//判空
		bool empty() const
		{
			return _finish == _start;
		}

		//begin迭代器
		iterator begin()
		{
			return _start;
		}

		//end迭代器
		iterator end()
		{
			return _start + size();
		}

		//begin迭代器const版本
		const_iterator begin() const
		{
			return _start;
		}

		//end迭代器const版本
		const_iterator end() const
		{
			return _finish;
		}

		//重载方括号
		T& operator[](size_t n)
		{
			assert(n < size());
			return *(_start + n);
		}

		//重载方括号const版本
		const T& operator[](size_t n) const
		{
			assert(n < size());
			return *(_start + n);
		}

	private:
		iterator _start; //空间起始位置
		iterator _finish; //有效数据终止位置
		iterator _end_of_storage; //空间终止位置
	};

	//打印函数
	template<class T>
	void print_vector(const vector<T>& v)
	{
		//auto it = v.begin();
		typename vector<T>::const_iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;

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

	}

	//--------------------------------------------------------
	//以下都是测试用函数

	void testvector1()
	{
		vector<int> v1;

		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);

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

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

		print_vector(v1);
	}

	void testvector2()
	{
		vector<int> v1;

		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		
		//注意迭代器失效
		v1.insert(v1.begin() + 1, 100);
		
		for (auto it : v1)
		{
			cout << it << " ";
		}
		cout << endl;

		v1.erase(v1.begin() + 1);

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

	void testvector3()
	{
		vector<int> v1;
	
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);

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

		vector<int> v2 = v1;

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

		vector<int> v3;
		v3.push_back(1);
		v3.push_back(2);
		v3.push_back(3);
		v3 = v1;

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

	//此段代码会报错,原因是在reverse中没有使用深拷贝,在析构delete的时候会报错
	//只实测在VS2022下,debug下会出现这样的问题,release就不会有,这里纯属埋坑不要模仿,错误已修正
	//这样的问题可能会出现在map等其他容器中
	void testvector4() 
	{
		vector<string> v1;

		v1.push_back("oldking");
		v1.push_back("oldking");
		v1.push_back("oldking");
		v1.push_back("oldking");
		v1.push_back("oldking");

		cout << v1.size() << " " << v1.capacity() << endl;

		for (auto it : v1)
		{
			cout << it << " ";
		}
		cout << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429

12.4 list – 链表

• 咱们前面有提到过,STL大部分容器的成员函数的效果都差不多,所以一般效果和使用方法相同的函数咱们就不再提了

12.4.1 list介绍

• 底层上list就是一个带头双向循环链表,用户在list中插入或者删除值的时间复杂度都是O(1)()

12.4.2 迭代器的种类与性质

• 前部分内容咱详细讲过迭代器的种类,这里就只列举一下

  • iterator 正向迭代器
  • reverse_iterator 反向迭代器
  • const_iterator 只读正向迭代器
  • const_reverse_iterator 只读反向迭代器

• 比较重要的就是迭代器的性质

• 迭代器的性质取决于容器在物理内存的构造

• 比方说在链表中,允许对当前node进行++操作(其实就是指向下一个节点),但一定不允许对node进行+的操作,node + 1到底是个啥?
  

• 所以我们对迭代器的性质进行了划分

  • 只读/写迭代器: none --只读/写迭代器是一个抽象概念,实际上没有数据结构会有这种迭代器
  • 单向迭代器: forward_list(单链表) 支持: ++
  • 双向迭代器: list(双向链表) 支持: ++/–
  • 随机迭代器: vector(顺序表) 支持: ++/–/+/-

• 很多算法库中的算法就对于传入的迭代器做了一定要求
  

• 比方说sort就只能传随机迭代器进去

• PS:要求的迭代器向下兼容,比方说一个接口要求传单向迭代器,意味着双向迭代器也支持,随机迭代器也支持

12.4.3 emplace()系列

void list_test1()
{
	list<A> lt1;

	A a1(2, 2);
	lt1.push_back(a1); //用已有值构造
	lt1.push_back(A(3, 3)); //用匿名对象构造


	list<A> lt2;
	A a2(4, 4);
	lt2.emplace_back(a1); //用已有值构造
	lt2.emplace_back(A(5, 5)); //用匿名对象构造
	//支持直接传入构造A类型对象的参数，实现的效果是一样的
	lt2.emplace_back(6, 6);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 目前阶段咱们只需要知道emplace_back支持直接传入构造A类型对象的参数,实现的效果和push_back是一样的,咱们可以理解为emplace_back就是升级版的push_back

• 少数情况下emplace_back效率更高一丢丢

12.4.5 list的指定值访问

• 假设我想访问一个list的下标为4的位置的值,我只能手动遍历迭代器到指定位置(因为不能使用+或-)

void list_test2()
{
	list<int> lt1;

	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);
	lt1.push_back(7);

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

	auto ilt = lt1.begin();
	size_t jk = 4;
	while (jk--)
	{
		ilt++;
	}

	lt1.insert(ilt, 100);

	for (auto it : lt1)
	{
		cout << it << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

12.4.6 list中特有的成员函数

void list_test3()
{
	list<int> lt1;

	lt1.push_back(1);
	lt1.push_back(1100);
	lt1.push_back(33);
	lt1.push_back(66666);
	lt1.push_back(5);

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

	lt1.reverse(); //逆置
	cout << "逆置:";

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

	lt1.sort(); //排序，底层是归并
	cout << "排序:";

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

	list<int> lt2;
	lt2.push_back(3);
	lt2.push_back(32);
	lt2.push_back(322);
	lt2.push_back(3222);
	lt2.push_back(32222);

	lt1.merge(lt2); //合并，lt2的值全部会被转移到lt1里，转移之后lt1一定是有序的
	cout << "合并:";

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

	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(322);
	lt1.sort();
	cout << "去重前:";
	for (auto it : lt1)
	{
		cout << it << " ";
	}
	cout << endl;

	lt1.unique(); //去重，去重前的链表必须是有序的，否则会出问题
	cout << "去重后:";

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

	lt1.push_back(1);

	cout << "移除1前:";
	for (auto it : lt1)
	{
		cout << it << " ";
	}
	cout << endl;

	lt1.remove(1); //移除，移除所有匹配的值

	cout << "移除1后:";
	for (auto it : lt1)
	{
		cout << it << " ";
	}
	cout << endl;

	list<int> lt3;
	lt3.push_back(4);
	lt3.push_back(5);
	lt3.push_back(6);
	lt3.push_back(7);

	auto it = lt1.begin();
	size_t jk = 3;
	while (jk--)
	{
		it++;
	}

	lt1.splice(it, lt3); //粘接，可以把一个链表的一部分剪切并且黏贴给另一个链表的指定位置(也可以把自己的一部分剪切并黏贴到自己的另一个位置)

	cout << "粘接:";
	for (auto it : lt1)
	{
		cout << it << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

12.4.7 关于list中的sort()

• list自带的sort()真的很垃圾,除了调用很方便以外,效率上真不高,如果说数据量比较少,那倒还可以用一用,到了10w往上量级的数据,甚至还没有通过assign()拷给一个vector,排完序再拷回来的效率高

12.4.8 list的模拟实现

• list.h:

#pragma once

#include<iostream>
#include<assert.h>

using namespace std;

namespace oldking
{
	template<class T>
	struct List_Node
	{
	public:
		List_Node<T>* _prev;
		T _val;
		List_Node<T>* _next;

		//不确定的类型给缺省值要给匿名对象
		List_Node(const T& val = T())
			:_val(val)
			, _prev(nullptr)
			, _next(nullptr)
		{
		}
	};

	//单独封装一个iterator模拟实现迭代器
	//template<class T>
	//struct List_Iterator
	//{
	//public:
	//	typedef List_Node<T> Node;
	//	typedef List_Iterator self;

	//	//用operator模拟实现迭代器++/--/*/!=
	//	self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}

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

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

	//	self operator--(int)
	//	{
	//		self tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}

	//	T& operator*()
	//	{
	//		return _node->_val;
	//	}

	//	bool operator!=(const self& iterator) const
	//	{
	//		return _node != iterator._node;
	//	}

	//	bool operator==(const self& iterator) const
	//	{
	//		return _node == iterator._node;
	//	}

	//	T* operator->()
	//	{
	//		return &(_node->_val);
	//	}

	//	List_Iterator(Node* node = nullptr)
	//		:_node(node)
	//	{
	//	}

	//public:
	//	Node* _node;
	//};

	//const迭代器则是单独对读取做限制就行
	//template<class T>
	//struct List_const_Iterator
	//{
	//public:
	//	typedef List_Node<T> Node;
	//	typedef List_const_Iterator self;

	//	//用operator模拟实现迭代器++/--/*/!=
	//	self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}

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

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

	//	self operator--(int)
	//	{
	//		self tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}

	//	const T& operator*()
	//	{
	//		return _node->_val;
	//	}

	//	bool operator!=(const self& iterator) const
	//	{
	//		return _node != iterator._node;
	//	}

	//	bool operator==(const self& iterator) const
	//	{
	//		return _node == iterator._node;
	//	}

	//	const T* operator->()
	//	{
	//		return &(_node->_val);
	//	}

	//	List_const_Iterator(Node* node = nullptr)
	//		:_node(node)
	//	{
	//	}

	//public:
	//	Node* _node;
	//};

	//这个模板类和上面手动实现两个本质上没有任何区别,T控制里面值的类型
	//因为上面两个类本质区别只有传参上的区别,所以我们用Ref和Ptr控制传参类型
	template<class T, class Ref, class Ptr>
	struct List_Iterator
	{
	public:
		typedef List_Node<T> Node;
		typedef List_Iterator<T, Ref, Ptr> self;

		//用operator模拟实现迭代器++/--/*/!=
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

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

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

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

		bool operator!=(const self& iterator) const
		{
			return _node != iterator._node;
		}

		bool operator==(const self& iterator) const
		{
			return _node == iterator._node;
		}

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

		List_Iterator(Node* node = nullptr)
			:_node(node)
		{
		}

	public:
		Node* _node;
	};


	template<class T>
	class List
	{
		//node默认为private
		typedef List_Node<T> Node;
	public:
		typedef List_Iterator<T, T&, T*> iterator;
		typedef List_Iterator<T, const T&, const T*> const_iterator;


		void empty_init()
		{
			//不确定的类型要给匿名对象
			_phead = new Node(T());
			_phead->_prev = _phead;
			_phead->_next = _phead;
			_size = 0;
		}

		List()
			:_phead(nullptr)
			,_size(0)
		{
			empty_init();
		}

		List(const List<T>& lt)
			:_phead(nullptr)
			, _size(0)
		{
			empty_init();
			
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		~List()
		{
			clear();
			delete _phead;
			_phead = nullptr;
		}

		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				//别忘了修正it
				it = erase(it);
			}
		}

		void push_back(const T& val)
		{
			Node* newnode = new Node(val);
			newnode->_prev = _phead->_prev;
			newnode->_next = _phead;
			_phead->_prev->_next = newnode;
			_phead->_prev = newnode;
			++_size;
		}

		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* prev = pos._node->_prev;

			Node* newnode = new Node(val);
			newnode->_prev = prev;
			newnode->_next = cur;

			cur->_prev = newnode;
			prev->_next = newnode;

			++_size;

			return prev;
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* next = pos._node->_next;
			Node* prev = pos._node->_prev;

			delete pos._node;

			next->_prev = prev;
			prev->_next = next;

			--_size;

			return next;
		}

		size_t size()const
		{
			return _size;
		}

		bool empty()
		{
			return _size == 0;
		}

		iterator begin()
		{
			//可以用匿名对象,甚至可以用隐式类型转换
			return iterator(_phead->_next);
		}

		const_iterator begin()const
		{
			//可以用匿名对象,甚至可以用隐式类型转换
			return const_iterator(_phead->_next);
		}

		iterator end()
		{
			return iterator(_phead);
		}

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

		List<T>& operator = (List<T> lt)
		{
			swap(lt);
			return *this;
		}

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



	private:
		Node* _phead;
		size_t _size;
	};

	//------------------------------------------------------------------------------
	//以下是测试代码

	void testlist1()
	{
		List<int> lt;

		cout << lt.size() << endl;
		cout << lt.empty() << endl;

		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

		cout << lt.size() << endl;
		cout << lt.empty() << endl;

		cout << *(++lt.begin()) << endl;
		cout << *(--lt.end()) << endl;

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

		for (auto it = lt.begin(); it != lt.end(); ++it)
		{
			cout << *it << " ";
		}
		cout << endl;

		lt.insert(lt.begin(), 100);

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

	void testlist2()
	{
		List<int> lt;

		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.push_back(6);
		lt.push_back(7);
		lt.push_back(8);
		lt.push_back(9);
		lt.push_back(10);
		lt.push_back(11);

		lt.erase(lt.begin());
		lt.pop_back();
		lt.pop_front();

		List<int>::iterator it = lt.begin();

		size_t k = 4;
		while (k--)
		{
			it++;
		}

		lt.insert(it, 100);

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

	}

	class AA
	{
	public:
		AA(int a = 1, int b = 1)
			:_aa(a)
			,_bb(b)
		{
		}

	public:
		int _aa;
		int _bb;
	};

	void testlist3()
	{
		List<AA> lt;

		

		lt.push_back(AA(1, 2));
		lt.push_back(AA(2, 3));
		lt.push_back(AA(3, 4));

		auto it = lt.begin();

		//注意,这里省略了一个箭头
		cout << it->_aa << endl;
		cout << it->_bb << endl;
		//这个->的调用原本应该长这样
		cout << it.operator->()->_aa << endl;
		//`it.operator->()`取到val的地址
		//然后因为val的指针是一个自定义类型的指针,所以可以使用->再取其中的成员
		//这里CPP为了考虑正常调用的可读性,把其中的一个箭头省略了

	}

	//注意按需实例化 -- 当模板没有被实例化成函数的时候
	//明显的语法错误才能被检测出来
	//很多细枝末节的错误是检查不出来的
	//比方说虽然是const对象,但没有实例化函数的时候,下面的(*it)++就检测不出来
	template<class contaner>
	void PrintContaner(const contaner& con)
	{
		for (auto it : con)
		{
			//(*it)++;
			cout << it << " ";
		}
		cout << endl;
	}

	void testlist4()
	{
		List<AA> lt1;
		List<int> lt2;

		lt2.push_back(1);
		lt2.push_back(2);
		lt2.push_back(3);
		lt2.push_back(4);
		lt2.push_back(5);

		PrintContaner(lt2);
	
	}

	void testlist5()
	{
		List<int> lt;

		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

		PrintContaner(lt);
		
		auto it = lt.begin();
		
		size_t k = 3;
		while (k--)
		{
			//使用erase的时候注意迭代器失效,list的insert不会有迭代器失效的问题
			//有没有迭代器失效的问题取决于内存空间有没有改变,这方面链表具有先天优势
			it = lt.erase(it);
		}

		PrintContaner(lt);
	}

	void testlist6()
	{
		List<int> lt1;

		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);
	
		List<int> lt2(lt1);

		PrintContaner(lt2);

		List<int> lt3;

		lt3.push_back(10);
		lt3.push_back(20);
		lt3.push_back(30);
		lt3.push_back(40);
		lt3.push_back(50);

		lt2 = lt3;
		
		PrintContaner(lt2);
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586

12.5 stack 和 queue

• 栈和队列的成员函数啥的实在过于简单,所以查查资料做做题就行了,本小节主要模拟实现以下栈和队列,和其他相关内容

12.5.1 容器适配器

• 适配器是设计模式的一种,这种模式可以把容器的接口转换为用户需要的接口,设计模式总共包含20多种,适配器和迭代器都是设计模式中的一种

• 这里的deuqe就是适配器的一种

• 栈和队列严格来说不算是容器,而是容器适配器,所以很多很多容器中有的接口在栈和队列里就没有

12.5.2 容器适配器与栈和队列

• 其实在之前数据结构的学习中能够发现,栈和队列的实现方式可以很多样,比方说栈既可以用顺序表实现,又可以用链表实现,带头/不带头,循环/不循环,单项/双向,这些都可以,并且STL对于这些容器的接口的调用方式全都进行了统一,使得你可以很轻松地用当中大部分容器实现栈

• 既然不同容器的接口的使用方法都一样,那么有没有一个模板参数,能通过我传入的容器类型,改变栈的底层结构呢?这个模板参数我们就称为适配器

• 栈的模拟实现

//stack.h:

#pragma once
#include<list>
#include<vector>
#include<deque>

namespace oldking
{
	//container可以给缺省参数,注意这个deque,后面会提到
	template<class T, class container = deque<T>>
	class stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_back();
		}

		size_t size() const
		{
			return _con.size();
		}

		const T& top() const
		{
			return _con.back();
		}

		bool empty() const
		{
			return _con.empty();
		}

	private:
		container _con;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

• 模拟栈的调用

//test.cpp:

#include<iostream>
#include"stack.h"

using namespace std;

int main()
{
	oldking::stack<int, list<int>> st_lt;
	oldking::stack<int, vector<int>> st_vc;

	st_lt.push(1);
	st_lt.push(2);
	st_lt.push(3);
	st_lt.push(4);

	st_vc.push(1);
	st_vc.push(2);
	st_vc.push(3);
	st_vc.push(4);
	st_vc.push(5);
	st_vc.push(6);


	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

• 此时我们打开调试

• 不难发现,这里st_lt是一个栈,底层是list,st_vc也是一个栈,底层却是vector,这就是适配器的效果

12.5.3 deque – 双端队列

• 了解deque之前,我们先来探讨一下为什么需要一个deque

• vector

  • 优势:
    • 对于下标的访问速度非常快,支持任意查找以O(1)的速度访问
    • 因为访问空间连续,且没有指针,所以空间存储率极高
  • 劣势:
    • 需要不断扩容,每次扩容对于效率上的消耗将进一步升级
    • 对于任意位置元素的删除和插入效率很低,因为需要挪动数据

• list

  • 优势:
    • 对于任意位置的元素的删除和插入效率都是O(1)
    • 因为储存空间不连续,是分为一个个Node,所以无需整体扩容
  • 劣势:
    • list不支持下标,任意位置的查找效率都十分低下
    • list因为每个节点都带有指针,所以空间存储率比较低

• 总结:对于vector和list,其两者几乎属于互补,但如果我想兼顾其两者的优势,就需要重新设计一个数据结构,此时deque就诞生了

• 当然,deque的诞生并不是革命性的,deque也拥有致命的缺点,替代不了vector和list,但deque的诞生至少能让我们有除了vector和list的另外的方式可选

• deque的主要构成为三个部分

  • 中控器:本质是个指针数组,指向各个缓冲区,用于管理各个缓冲区,中控器中有效指针的开辟会从中间开始,向两边延伸,核心是为了解决vector头插效率极低的问题
  • 缓冲区:数据物理上会存储的地方,他物理上是一片一片的,每一片都可以存储复数个数字而非list的一个,但又像list一样,每个缓冲区在物理上是分散的,仅靠中控器的连接,使得逻辑上是连续的,并且缓冲区的每一片的大小都是一样的,申请空间的效率也不会太低
  • 迭代器:用于遍历deque,其中的first和last用于管理当前迭代器指向的具体是哪个缓冲区,cur则用于管理具体是指向的缓冲区的哪个位置,而node用于指向中控器中当前缓冲区所对应的指针,方便遍历的时候导致的缓冲区更替,注意,deque的迭代器是随机迭代器

• 此外,deque的成员中还设计了两个迭代器start和finish始终指向deque的第一个值和最后一个值,方便进行头插和尾插,以及[]访问

• 关于下标访问:因为缓冲区的每一片大小都一样,所以我们可以通过相除的方式算出所需值具体在哪个缓冲区,又因为缓冲区的空间连续,可以通过取模的方式算出具体在缓冲区的哪个位置,因为1需要计算位置的缘故,虽然效率相比vector略低一些,但也不是不能接受

• 至此,我们解决了vector和list中几个比较重要的缺陷

  • 支持下标访问,速度还算凑合
  • 访问空间连续但不完全连续,指针有但不多,空间利用率也还算凑合,也不需要整体扩容,不需要整体调整物理位置
  • 因为有start,finish,以及中控器双向延申的设计,对于头插尾插来说效率非常高

• 但相对的,因为这样的设计,会导致往容器稍稍中间的部分删除和插入值会造成极大的损耗,一旦往中间部分插入或者删除值,一样会需要像vector一样挪动数据,消耗极大,但对于栈和队列这种只需要头尾增删的适配器来说,那就是顶中顶,所以像stack和queue这样的适配器,在官方设计的模板参数中,就采用了deque的方案

• PS:deque的下标访问效率虽然不错,但依旧不如vector那么极致,在排序算法中,效率约是vector的两倍,不如拷贝给vector排序完再拷贝回来

12.5.4 priority_queue – 优先级队列

• 优先级队列也是一个容器适配器

• 优先级队列的使用方式和普通队列差不多,但区别在于每一个数都存在优先级,对于pop()和top()这两个函数来说,他们需要取优先级高的数,默认是大的数优先级最高,要控制优先级分配的逻辑就需要用到一个叫仿函数的东西,这个东西以后面再提

• 可以看出来,优先级队列很像一个堆,事实上,它的底层就是拿堆来实现的,所以它的默认适配容器是拿的vector

• 手撕priority_queue

#pragma once

#include<iostream>
#include<cassert>
#include<vector>

using namespace std;

//这个类称为仿函数,里面重载了一个`()`,当我们实例化这个类之后,就可以向函数一样调用这个类了
//创造这么个东西的意图在于替代非常麻烦的函数指针,根本上这个东西就是一个回调
template<class T>
struct Less
{
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

template<class T>
struct Greater
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

namespace oldking
{
	//可以专门搞一个模板参数用于比较,传不同的仿函数进来就可以实现不同的比较方式
	template<class T, class container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(size_t pos)
		{
			assert(pos < _con.size());
			
			//实例化仿函数
			Compare com;

			//实际调用的时候和调用普通函数没什么不同
			while ((pos - 1) / 2 < _con.size() && com(_con[(pos - 1) / 2], _con[pos]))
			{
				swap(_con[(pos - 1) / 2], _con[pos]);
				pos = (pos - 1) / 2;
			}
		}

		void AdjustDown(size_t pos)
		{
			assert(pos < _con.size());
			Compare com;

			size_t parentpos = pos;
			size_t childpos = pos * 2;
			if (childpos + 1 < _con.size() && com(_con[childpos], _con[childpos + 1]))
			{
				++childpos;
			}

			while (childpos < _con.size() && com(_con[parentpos], _con[childpos]))
			{
				swap(_con[parentpos], _con[childpos]);
				parentpos = childpos;

				size_t childpos = parentpos * 2;
				if (childpos + 1 < _con.size() && com(_con[childpos], _con[childpos + 1]))
				{
					++childpos;
				}
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);

			AdjustUp(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			AdjustDown(0);
		}

		const T& top()
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		container _con;
	};

	void priority_queue_test1()
	{
		priority_queue<int, vector<int>, Greater<int>> pq;

		pq.push(1);
		pq.push(4);
		pq.push(2);
		pq.push(8);
		pq.push(3);

		cout << pq.size() << endl;
		cout << pq.empty() << endl;
		cout << pq.top() << endl;

		pq.pop();

		cout << pq.size() << endl;
		cout << pq.empty() << endl;
		cout << pq.top() << endl;

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131