C++之STL

 1.简述

STL 是“Standard Template Library"的缩写，中文译为“标准模板库”。STL是C++标准库的一部分，位于各个C++ 的头文件中，即它并非以二进制代码的形式提供，而是以源代码的形式提供。STL体现了泛型编程的思想，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形，为我们提供了一个可扩展的应用框架，高度体现了程序的可复用性。STL的一个重要特点是数据结构和算法的分离。

STL的头文件都不加扩展名，且打开std命名空间。

包含了六大组件：

 2.容器

主要分两大类：
1.序列性容器：元素的位置取决于插入顺序，元素按照插入顺序排列。
2.关联性容器：元素位置取决于特定的排序规则，与插入顺序无关，类似key-value。
容器类自动申请和释放内存，无需new和delete操作。

序列性容器

2.1 array

array 容器是 C++11 标准中新增的序列容器，简单地理解，它就是在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。在使用上，它比普通数组更安全，且效率并没有因此变差。

array 容器以类模板的形式定义在 <array> 头文件，并位于命名空间 std 中，array容器的初始化：

std::array<int,10> values {1,2,3,5,0,1};//剩下的初始化成0

1.array是一个固定大小的容器，它的大小在编译时就确定。可以通过 size() 方法直接获取。

2.array支持标准容器接口，可以像其他容器（如vector、list）一样使用。

3.array类型安全，普通数组的访问容易导致越界访问，且没有自动的边界检查。array 提供了 at() 方法，该方法会进行越界检查，如果访问的元素超出范围，它会抛出 out_of_range 异常。

4.支持直接复制，但要保证两个数组类型和元素数目一致：

   std::array<int, 3> arr1 = {1, 2, 3};
   std::array<int, 3> arr2 = arr1;//直接复制

require:

#include<array>

using namespace std;

array容器成员函数汇总

2.2 list链表

STL链表是序列性容器的模板类，它将其元素保持在线性排列中，链式结构，并允许在序列中的任何位置进行有效的插入和删除。
特点：list在任何指定位置动态的插入删除效率不变，时间复杂度为O(1)，操作相比于vector比较方便。但其查找效率为O(n)，若想访问、查看、读取数据使用vector。

注：STL中为双向循环链表，且不能通过end()++回到表头。

双向循环链表：

require:

#include<list>

using namespace std;

list(size_type Count)。list(size_type Count,const Type& Val)。构造链表长度并设置初始值。有默认值。

	//list<int> lst(3);     //指定链表长度，且有默认的初始值(初始值为 0 )
	//list<int> lst(3, 4);  //指定链表长度，且指定了初始值(初始值为 4 )
	list<int> lst{ 1,2,3,4 };
	list<int>::iterator ite = lst.begin();
	while (ite != lst.end())
	{
		cout << *ite << " "; //1 2 3 4
		ite++;
	}
	cout << endl;

1. begin()：获取头结点的迭代器。end():获取尾节点的迭代器
2. front()：返回头结点里的值。 back():返回尾结点里的值。
3. clear()：清空链表。
4. size()： 返回链表的长度、元素的数量。
5. bool empty()：链表是否为空。
6. erase()：删除指定迭代器位置的节点，返回的是删除节点的下一个节点的迭代器。 insert():指定迭代器位置插入一个元素，返回的是插入的元素的迭代器。
7. push_back()、push_front()、pop_back()、pop _front()：链表头尾添加、删除。
8. remove(const Type& Val )：将值为val的所有节点删除.。
9. unique()：将连续而相同的节点移除只剩一个。
10.sort()：对链表元素进行排序，默认升序。如果要指定排序规则，需要指定排序规则函数。bool func(Type,Type);或 greater<>()降序，less<>()升序。
11.reverse()：链表进行翻转。
12.splice(iterator Where, list& Right)：将 Right链表整个结合到另一个链表where位置之前，这是一个“剪切"操作，Right 链表将为空。

	list<int> lst1{ 1,2,3,4 };
	list<int> lst2{ 5,6,7,8 };

	list<int>::iterator ite = lst1.begin();
	advance(ite,3); //迭代器做偏移，支持正向、反向偏移
	lst1.splice(ite,lst2);
	for (int v : lst1) cout << v << " "; cout << endl; //1 2 3 5 6 7 8 4
	cout << "lst2的长度：" << lst2.size() << endl; //lst2的长度：0（相当于剪切操作，lst2将为空）

splice(iterator Where,list& Right,iterator First):将Riqht链表的First位置节点结合到 this 链表的where位置之前，这是一个“剪切"操作。this 和 Right 可以为同一个链表。

	list<int> lst1{ 1,2,3,4 };
	list<int> lst2{ 5,6,7,8 };

	list<int>::iterator ite = lst1.begin();
	advance(ite,3); //迭代器做偏移，支持正向、反向偏移
	cout << *ite << endl; //4
	lst1.splice(ite,lst2,lst2.begin());
	for (int v : lst1) cout << v << " "; cout << endl; //1 2 3 5 4
	cout << "lst2的长度：" << lst2.size() << endl; //lst2的长度：3

splice(iterator Where,list& Right,iterator First,iterator Last):将Right链表的First位置到Last位置的一段元素[First,Last)，不包含Last，结合到this链表的where位置之前，这是一个“剪切"操作。this 和 Right 可以为同一个链表，但Where不能位于[First,Last) 内。

	list<int> lst1{ 1,2,3,4 };
	list<int> lst2{ 5,6,7,8 };

	list<int>::iterator ite = lst1.begin();
	advance(ite,3); //迭代器做偏移，支持正向、反向偏移
	cout << *ite << endl; //4
	lst1.splice(ite,lst2,lst2.begin(),lst2.end());
	for (int v : lst1) cout << v << " "; cout << endl; //1 2 3 5 6 7 8 4
	cout << "lst2的长度：" << lst2.size() << endl; //lst2的长度：0

13.merge(list& Right, Traits Comp)；将 Right 链表合并到this链表上，this 和 Right 必须经过排序两者或都为递增、或都为递减，Comp 描述了递增合并还是递减合并，若this 和 Right为升序，那么Comp也必须为升序。可以自定义排序规则 bool func(Type,Type)或 greater<>() 降序，less<>()升序。这是一个“剪切"操作，Right 将为空链表。

	list<int> lst1{ 5,4,3,2 };
	list<int> lst2{ 4,3,2,1 };
	lst1.merge(lst2, greater<>());
	//lst1.merge(lst2, func); //也可以自定义排序规则
	for (int v : lst1) cout << v << " "; cout << endl; //5 4 4 3 3 2 2 1

14.swap( list& Right);交换两个链表。

	list<int> lst1{ 5,4,3,2 };
	list<int> lst2{ 4,3,2,1 };

	lst1.swap(lst2);
	//swap(lst1, lst2); //两种都可以
	for (int v : lst1) cout << v << " "; cout << endl; //4 3 2 1

15.advance(_InIt& _Where, _Diff _Off);迭代器做偏移，支持正向、反向偏移

	list<int> lst1{ 1,2,3,4 };
	list<int>::iterator ite = lst1.begin();
	advance(ite,3); //迭代器做偏移，支持正向、反向偏移
	cout << *ite << endl; //4

关于list迭代器失效 

对于list，删除当前迭代器指向的元素会使迭代器失效。一般list插入操作不会导致迭代器失效。

2.3 vector向量

vector 的行为类似于数组(array)，但是其容量会随着需求自动增长。向量在尾部的push和pop操作时间是恒定的。在向量的中间insert或erase元素需要线性时间，在序列结尾插入、删除操作比在开始位置性能要优越。

当向量元素增加超过当前的存储容量时，会发生重新分配操作。重载了 [ ] 操作符，就意味着它可以像数组一样使用【下标】访问元素。

特点：数据的存储访问比较方便，可以像数组一样使用 [index] 访问或修改值，适用于对元素修改和查看比较多的情况，对于 insert 或 erase 比较多的操作，很影响效率，不建议使用vector。

 require:

#include<vector>

using namespace std;

vector(size_type Count)。 vector(size_type Count,const Type& Val)。构造函数，构造指定长度的向量并设定初始值。有默认值。
1. begin()，end()，返回向量头尾元素的迭代器。
2. front()，back()，返回头尾元素中的值。
3.size()，返回向量的使用量，capacity()，返回向量的容量,
4. push_back()，pop_back()，在向量头、尾添加删除，当用 push_back 向 vector 尾部加元素的时候，如果当前的空间不足，会重新申请一块更大的空间。pop_back 删除时，使用量减少，但容量不会减少。不同于list，vector并没有提供 push_front 和 pop_front。
5.insert(const_iterator Where,const Type& Val) ，向量的某个位置之前插入指定值。insert(const_ iterator Where, size_type Count, const Type& Val)。向量的某个位置之前插入count个指定值。
返回插入元素的迭代器，size会增加。
6.erase(const_iterator Where)，删除迭代器指向的元素，返回的是删除元素的下一个元素的迭代器。size 减少，capacity 不变。
7.clear()，清空向量元素，size 使用量为0，capacity 不变。

	vector<int> vec{ 1,2,3,4 };
	vec.clear();
	cout << vec.capacity() << " " << vec.size() << endl;  //4 0
	vec.shrink_to_fit(); //将vector容量缩到和使用量一样
	cout << vec.capacity() << " " << vec.size() << endl;  //0 0

8.empty()，向量是否为空，描述的是使用量。
9.resize(size_type Newsize)，resize(size_type _Newsize,Type_Val)。为向量指定新的使用量，如果使用量减少，元素按顺序截取，但容量不变，如果使用量增加大于原容量，则扩展容量，并可以指定新扩展元素的值。
10.swap(vector& Right)，交换两个向量的元素，同时使用量和容量也交换。

	vector<int> vec{ 1,2,3,4 };
	vector<int>{1, 2}.swap(vec);
	for (int v : vec) cout << v << " "; cout << endl; //1 2

对比 list 和 vector

1.vector 是连续性空间，顺序存储，底层是动态数组；list 链式结构体，链式存储，底层是双向循环链表。
2.vector在非尾部插入、删除节点会导致其他元素的拷贝移动，list则不会影响其他节点元素。3.vector 一次性分配好内存，容量不够时，申请内存重新分配。list每次插入新节点时都会申请内存。
4.vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。
5.vector 具有容量和使用量的概念，而list只有使用量(即长度)概念。

6.vector与list都是非线程安全的容器，如果多个线程同时操作一个容器，必须使用同步机制（如互斥锁）保证线程安全。 

关于vector迭代器失效

1.插入元素失效：当用insert向vector插入元素时，可能会发生内存重新分配，特别是当vector已满时，此时所有迭代器都可能失效。

原因：1.vector会分配一个新的、更大的内存块，并将所有元素复制到新内存中。2.插入的元素会放到新的内存块，旧的内存块被释放，这样就导致所有指向原来位置的迭代器失效。

解决：1.insert之后返回新的迭代器，如 it = vec.insert(it,5);2.可以使用 reserve() 提前为vector分配足够的内存，避免在插入时发生重新分配。

2.删除元素失效 ：当erase删除一个元素时，当前位置的后面的元素向前移动（相当于把当前位置元素覆盖），此时指向这些元素的迭代器失效。当调用clear删除所有元素时，vector会释放其内存，此时所有迭代器都会失效。

解决：1.erase之后返回新的迭代器，如 it = vec.erase(it);2.如果此时正在循环遍删除某个元素，需要判断当前位置元素是否删除，如果删除了，不执行it++，举例：

迭代器失效：

	vector<int>v{ 1,2,3,3,4,5 };
	auto it = v.begin();
	for (; it != v.end(); it++)
	{
		if (*it == 3)
		{
			it = v.erase(it);
		}
	}
	for (auto i : v)
	{
		cout << i << endl;
	}//1 2 3 4 5

更正后：

	vector<int>v{ 1,2,3,3,4,5 };
	auto it = v.begin();
	for (; it != v.end();)
	{
		if (*it == 3)
		{
			it = v.erase(it);
		}
		else
		{
			it++;
		}
	}
	for (auto i : v)
	{
		cout << i << endl;
	}//1 2 4 5

面试题：vector的动态扩容为什么是1.5倍或者2倍？

vector是如何进行扩容的？

简单来说，分为开辟新空间，拷贝元素，释放旧空间。

扩容会导致效率低下，那如何避免动态扩容呢？

可以使用 reserve() 提前为vector分配足够的内存，避免在插入时发生重新分配。

为什么选择以1.5倍或者2倍方式进行扩容？而不是3倍4倍扩容？

扩容原理为：申请新空间，拷贝元素，释放旧空间，理想的分配方案是在第N次扩容时如果能复用之前N-1次释放的空间就太好了，如果按照2倍方式扩容，第i次扩容空间大小如下：

可以看到，每次扩容时，前面释放的空间都不能使用。比如：第4次扩容时，前2次空间已经释放，第3次空间还没有释放(开辟新空间、拷贝元素、释放旧空间)，即前面释放的空间只有1 + 2 = 3，假设第3次空间已经释放才只有1+2+4=7，而第四次需要8个空间，因此无法使用之前已释放的空间，但是按照小于2倍方式扩容，多次扩容之后就可以复用之前释放的空间了。如果倍数超过2倍(包含2倍)方式扩容会存在：

1.空间浪费可能会比较高，比如：扩容后申请了64个空间，但只存了33个元素，有接近一半的空间没有使用。

2.无法使用到前面已释放的内存。

vs为什么选择1.5倍，linux为什么选择2倍？

windows扩容底层：windows中堆管理系统会对释放的堆块进行合并,因此vs下的vector扩容机制选择使用1.5倍的方式扩容,这样多次扩容之后,就可以使用之前已经释放的空间。

linux扩容底层：在Linux系统中，2倍扩容可以更好的利用内存页，减少内存碎片的产生。

具体来说，linux中引入伙伴系统为内核提供了一种用于分配连续的页而建立的一种高效分配策略，伙伴系统是将整个内存区域构建成基本大小basicSize的1倍、2倍、4倍、8倍、16倍等，即要求内存空间分区链均对应2的整次幂倍大小的空间，整齐划一，有规律的而不是乱糟糟的。
在分配和释放空间时，可以通过log2(request/basicSize)向上取整的哈希算法快速找到对应内存块。通过伙伴系统管理空闲分区的了解，可以看到在伙伴系统中的每条空闲分区链中挂的都是2^i的页面大小，通过哈希思想进行空间分配与合并，非常高效。

2.4 deque双端队列

deque 没有容量的观念。它是动态以分段连续空间组合而成，一旦有必要，在deque 的首端和尾端增加新空间，串接在整个deque 的首端或尾端，deque 的迭代器不是普通的指针，其复杂度比vector 复杂的多。除非必要，我们应该尽量选择使用 vector 而非 deque。

deque 是一种双向开口的连续性空间，可以在首尾两端分别做元素的插入和删除操作。

deque 容器和 vector 容器一样也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。同样 deque 容器也可以根据需要修改自身的容量和大小。

和 vector 不同的是，deque 还擅长在序列头部添加或删除元素（时间复杂度为O(1)），而 vector在头部添加或删除元素时间复杂度为O(n)，对于需要频繁在头部添加或删除元素时，应选用deque而非vector。

deque的迭代器中的四个指针的作用分析： 

require:

#include<deque>

using namespace std;

deque(size_type Count)，deque(size_type_Count,const Type& Val)，构造函数，构造指定长度的向量并设定初始值。有默认值。
1. push back()、push front()、pop back()、pop front()。
2. begin()、end()、back()、front()、erase()、insert()。
3.size()，empty()，clear()，支持[]下标访问。

关联性容器

2.5 map/multimap

map 的特性是，所有元素都会根据元素的键值自动被排序，map的所有元素都是pair，同时拥有键值(key)和实值(value)。pair的第一元素被视为键值，第二元素被视为实值。map 不允许两个元素拥有相同的键值，map 的键值关系到map的元素的排列规则，任意改变map元素键值将严重破坏map的组织。所以不可以通过map 的迭代器来改变map 的键值。但是可以通过迭代器来修改元素的实值。
查找效率:O(log2^n)，内部实现红黑树。

注：加上multi意味着可以重复键值对。

require:

#include<map>

using namespace std; 

multimap也使用此头文件。 

 map容器常用成员方法

2.6 set/multiset

所有元素都会根据元素的键值自动被排序，set 的元素不像map那样可以同时拥有实值和键值，set 元素的键值就是实值，实值就是键值。set 不允许两个元素有相同的键值，因为set 元素值就是其键值，关系到 set 元素的排列规则。如果任意改变set 的元素值，会严重的破坏set组织。
查找效率:O(log2^n)，内部实现红黑树。

注：加上multi意味着可以重复键值对。

require:

#include<set>

using namespace std;

multiset也使用此头文件。  

set容器常用成员方法

2.7 unordered_map/unordered_multimap

unordered_map 容器和 map 容器一样，以键值对（pair类型）的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。

require:

#include <unordered_map>
using namespace std;

2.8 unordered_set/unordered_multiset

unordered_set 即为“无序set”，和set容器的区别在于set容器会自行对存储的数据进行排序，而unordered_set不会。并且 unordered_set 底层采用的是哈希表存储结构。

require:

#include <unordered_set>
using namespace std;

红黑树实现和哈希表实现的这四个容器的区别：

1.map始终保证遍历的时候是按key的大小顺序的，这是一个主要的功能上的差异。（有序无序）2.时间复杂度上，红黑树的插入删除查找性能都是O(logN)，而哈希表的插入删除操作的理论上时间复杂度是O(1)，这有个前提就是哈希表不发生数据碰撞。在发生碰撞的最坏的情况下，哈希表的插入和删除时间复杂度最坏能达到O(n)。注释：最坏情况就是所有的哈希值全部都在同一个链表上
3.map可以做范围查找，而unordered_map不可以。
4.unordered_map内存占用比map高。
5. 扩容导致迭代器失效。 map的iterator除非指向元素被删除，否则永远不会失效。unordered_map的iterator在对unordered_map修改时有时会失效。因为在操作 unordered_map 容器过程（尤其是向容器中添加新键值对）中，一旦当前容器的负载因子超过最大负载因子（默认值为 1.0），该容器就会适当增加桶的数量（通常是翻一倍），并自动执行 rehash() 成员方法，重新调整各个键值对的存储位置（此过程又称“重哈希”），此过程很可能导致之前创建的迭代器失效。

3.空间分配器

作用：用于容器的内存分配。

在C++中，内存分配和操作通过new和delete完成。
new中包含两个操作，第一步是使用operator new分配内存，第二步是调用构造函数；
delete中包含两个操作，第一步是调用析构函数，第二步是使用operator delete释放内存。

注：new分配内存本质上是通过调用malloc来实现的。

malloc内存分配器是怎样实现的？

调用malloc时，内存分配器通过遍历找到我们需要的空闲内存块，内存块中包含信息头header（32bit）和负载payload，其中header包含块大小以及1bit的标志位（用于标识当前内存块是否使用过），剩下的负载payload才是可供分配的内存块。通过当前位置加上当前块大小就能找到下一个内存块，malloc返回的就是可供分配的内存块起始指针位置。

三种查找策略：

1.First Fit：最简单的就是每次从头开始找起，找到第一个满足要求的就返回。

2.Next Fit：这个策略和First Fit很相似，是说我们别总是从头开始找了，而是从上一次找到合适的空闲内存块的位置找起，因为上一次找到某个合适的内存块的地方很有可能剩下的内存块能满足接下来的内存分配请求，由于不需要从头开始搜索，因此Next Fit将远快于First Fit。然而也有研究表明Next Fit方法内存使用率不及First Fit。

3.Best Fit：First Fit和Next Fit都是找到第一个满足要求的内存块就返回，但Best Fit不是这样。Best Fit算法会找到所有的空闲内存块，然后将所有满足要求的并且大小为最小的那个空闲内存块返回，这样的空闲内存块才是最Best的，因此被称为Best Fit。

调用free时，会检查相邻内存块是否是空闲内存块，如果是 ，将当前内存块与相邻空闲内存块合并，如何找到上一个内存块和下一个内存块？为了快速找到上一个内存块，在内存块中新增加了footer，当前位置加上块大小即可找到下一个内存块位置，当前位置向上移动四字节就能得到上个内存块信息。

4.迭代器

迭代器是算法和容器之间的桥梁，算法通过迭代器访问容器中的data，进而操作。

各种容器的iterator_category：

另外有两种比较特殊，他们各自仅包含了一种迭代器：

5.容器适配器

STL所提供的各种适配器中：

1.改变仿函数接口者，称为函数适配器；
2.改变容器接口者，称为容器适配器；
3.改变迭代器接口者，称为迭代器适配器。

函数适配器举例：bind2nd、not1

容器适配器举例：queue和stack。stack的底层由deque构成，stack封锁住了所有的deque对外接口，只开放符合stack原则的几个函数；queue的底层也由deque构成，queue封锁住了所有的deque对外接口，只开放符合queue原则的几个函数。

迭代器适配器举例：

1.reverse_iterator
可以通过一个双向顺序容器调用rbegin()和rend()来获取相应的逆向迭代器。只要双向顺序容器提供了begin()和end()，它的rbegin()和rend()就如同下面的形式。
单向顺序容器slist不可使用reserve_iterators。有些容器如stack、queue、priority_queue并不提供begin()和end()，当然也就没有rbegin()和rend()。

2.insert_iterator
可以将一般迭代的赋值操作转变为插入操作，insert iterators实现的主要观念是：

每一个insert iterators内部都维护有一个容器（必须由用户指定）。容器当然有自己的迭代器，于是，当客户端对insert iterators做赋值操作时，就在insert iterators中被转为对该容器的迭代器做插入操作（也就是说，调用底层容器的push_front()或push_back()或insert()）。

6. 算法

以函数的形式呈现，需要头文件 #include<algorithm>。