cpp之STL

STL原理

STL ⼀共提供六⼤组件，包括容器，算法，迭代器，仿函数，适配器和空间配置器，彼此可以组合套⽤。容器通过配置器取得数据存储空间，算法通过迭代器存取容器内容，仿函数可以协助算法完成不同的策略变化，适配器可以应⽤于容器、 仿函数和迭代器。

容器：各种数据结构，如 vector，list，deque，set，map，⽤来存放数据， 从实现的⻆度来讲是⼀种类模板。

算法：是用来操作容器中的数据的模板函数，如 sort（插⼊，快排，堆排序），search（⼆分查找）， 从实现的⻆度来讲是⼀种⽅法模板。

迭代器：提供了访问容器中对象的方法。从实现的⻆度来看，迭代器是⼀种将 operator*，operator->，operator++，operator-- 等指针相关操作赋予重载的类模板，所有的 STL 容器都有⾃⼰的迭代器。

仿函数：从实现的⻆度看，仿函数是⼀种重载了 operator() 的类或者类模板，可以帮助算法实现不同的策略。

适配器：⼀种⽤来修饰容器或者仿函数或迭代器接⼝的东⻄。简单的说就是一种接口类，专门用来修改现有类的接口，提供一种新的接口，或调用现有的函数来实现所需要的功能。

空间配置器：负责空间配置与管理，从实现的⻆度讲，配置器是⼀个实现了动态空间配置、空间管理，空间释放的类模板。

常见容器及其原理

容器可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是模板类，分为顺序容器、关联式容器、容器适配器三种类型，三种类型容器特性分别如下：

1. 顺序式容器

   容器并非排序的，元素的插入位置同元素的值无关。包含vector、deque、list，具体实现原理如下：

   （1）vector

   动态数组。元素在内存连续存放，随机存取任何元素都能在常数时间完成，在尾端增删元素具有较佳的性能。

   （2）deque

   双向队列。元素在内存连续存放**，**随机存取任何元素都能在常数时间完成（仅次于vector），在两端增删元素具有较佳的性能（大部分情况下是常数时间）。

   （3）list

   双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成，不支持随机存取。无成员函数，给定一个下标i，访问第i个元素的内容，只能从头部挨个遍历到第i个元素。

2. 关联式容器

   元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现。包含set、multiset、map、multimap，具体实现原理如下：

   （1）set/multiset

   set 即集合。set中不允许相同元素，multiset中允许存在相同元素。

   （2）map/multimap

   map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first，另一个名为second。map根据first值对元素从小到大排序，并可快速地根据first来检索元素。

   注意：map同multimap的不同在于是否允许存在first值相同的元素。

3. 容器适配器

   封装了一些基本的容器，使之具备了新的函数功能，比如把deque封装一下变为一个具有stack功能的数据结构。新得到的数据结构就叫适配器，包含stack, queue, priority_queue，具体实现原理如下：

   （1）stack

   栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项），后进先出。

   （2）queue

   队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行，先进先出。

   （3）priority_queue

   优先级队列。内部维持某种有序，然后确保优先级最高的元素总是位于头部，最高优先级元素总是第一个出列。

迭代器

什么是迭代器？

Iterator（迭代器）模式又称游标（Cursor）模式，用于提供一种方法顺序访问一个聚合对象中各个元素，而又不需暴露该对象的内部表示。 或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。 由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展Iterator。

#include <vector>
#include <iostream>
using namespace std;int main() {vector<int> v; //一个存放int元素的数组，一开始里面没有元素v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::const_iterator i; //常量迭代器for (i = v.begin(); i != v.end(); ++i) //v.begin()表示v第一个元素迭代器指针，++i指向下一个元素cout << *i << ","; //*i表示迭代器指向的元素cout << endl;vector<int>::reverse_iterator r; //反向迭代器for (r = v.rbegin(); r != v.rend(); r++)cout << *r << ",";cout << endl;vector<int>::iterator j; //非常量迭代器for (j = v.begin();j != v.end();j++)*j = 100;for (i = v.begin();i != v.end();i++)cout << *i << ",";return 0;
}/*    运行结果：1,2,3,4,4,3,2,1,100,100,100,100,
*/                

容器的end()方法返回一个迭代器，需要注意：这个迭代器不指向实际的元素，而是表示末端元素的下一个元素，这个迭代器起一个哨兵的作用，表示已经处理完所有的元素。因此，在查找的时候，返回的迭代器不等于end()，说明找到了目标；等于end()，说明检查了所有元素，没有找到目标。

迭代器的作用

（1）用于指向顺序容器和关联容器中的元素

（2）通过迭代器可以读取它指向的元素

（3）通过非const迭代器还可以修改其指向的元素

迭代器和指针的区别

迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，重载了指针的一些操作符，–>、++、–等。迭代器封装了指针，是一个可遍历STL容器内全部或部分元素的对象，本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，–等操作。

迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

迭代器产生的原因

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

迭代器什么时候会失效？迭代器如何删除元素？

对于顺序式容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。

对于关联式容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。

容器	容器上的迭代器类别
vector	随机访问
deque	随机访问
list	双向
set/multiset	双向
map/multimap	双向
stack	不支持迭代器
queue	不支持迭代器
priority_queue	不支持迭代器

vector原理

Vector在堆中分配了⼀段连续的内存空间来存放元素，随着元素的加⼊，它的内部机制会⾃⾏扩充空间以容纳新元素。vector 维护的是⼀个连续的线性空间，⽽且普通指针就可以满⾜要求，能作为 vector 的迭代器。

vector 的数据结构中其实就是三个迭代器构成的，⼀个指向⽬前使⽤空间头的 iterator，⼀个指向⽬前使⽤空间尾的iterator，⼀个指向⽬前可⽤空间尾的 iterator。当有新的元素插⼊时，如果⽬前容量够⽤则直接插⼊，如果容量不够，则容量扩充⾄两倍，如果两倍容量不⾜， 就扩张⾄⾜够⼤的容量。

扩充的过程并不是直接在原有空间后⾯追加容量，⽽是重新申请⼀块连续空间，将原有的数据拷⻉到新空间中，再释放原有空间，完成⼀次扩充。需要注意的是，每次扩充是重新开辟的空间，所以扩充后，原有的迭代器将会失效。

新增元素

Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，再插入新增的元素。插入新数据可以通过最后插入push_back和通过迭代器在任何位置插入insert()。通过迭代器与第一个元素的距离知道要插入的位置，即int index = iter - begin()，这个元素后面的所有元素都向后移动一个位置，在空出来的位置上存入新增的元素。

//新增元素
void insert(const_iterator iter, const T &t){int index = iter - begin();if (index < size_){if (size_ == capacity_){int capa = calculateCapacity();newCapacity(capa);}memmove(buf + index + 1, buf + index, (size_ - index) * sizeof(T));buf[index] = t;size_++;}
}

删除元素

删除也分两种：删除最后一个元素pop_back和通过迭代器删除任意一个元素erase(iter)。通过迭代器删除要先找到要删除元素的位置，即int index = iter - begin()，这个位置后面的每个元素都想前移动一个元素的位置。erase不释放内存，只初始化成默认值。

删除全部元素clear：只是循环调用了erase，所以删除全部元素的时候不释放内存，内存是在析构函数中释放的。

//删除元素
iterator erase(const_iterator iter){int index = iter - begin();if (index < size_ && size_ > 0){memmove(buf + index, buf + index + 1, (size_ - index) * sizeof(T));buf[--size_] = T();}return iterator(iter);
}

push_back和emplace_back

如果要将一个临时变量push到容器的末尾，push_back()需要先构造临时对象，再将这个对象拷贝到容器的末尾，最后销毁临时对象。而emplace_back() 会在容器中原地创建一个对象，减少临时对象拷贝、销毁的步骤，所以性能更高。

如果插入vector的类型的构造函数接受多个参数，那么push_back只能接受该类型的对象，而emplace_back还能接受该类型的构造函数的参数。如果只有一个构造参数，push_back在c++11就支持只把单个的构造参数传进去了（写法更简洁，效果、性能跟传对象是一模一样的），会进行类型自动转换。

在性能上，对于内置类型性能都一样，而对于用户自定义的类，emplace_pack仅在通过使用构造参数传入的时候更高效。

1. 若通过构造参数向vector中插入对象，emplace_back更高效：

std::vector<A> a;
a.emplace_back(1);  
a.push_back(2);

emplace_back：仅调用有参构造函数 A (int x_arg) ；

push_back：（1）调用有参构造函数 A (int x_arg) 创建临时对象；（2）调用移动构造函数 A (A &&rhs) 到vector中；（3）调用析构函数销毁临时对象；

2. 插入临时对象，二者一样，调用移动构造函数：

std::vector<A> a;
a.emplace_back(A(1)); 
a.push_back(A(2));

插入对象都需要三步走：建临时对象->移动->销毁临时对象

3. 插入实例化的对象，二者还是一样，调用拷贝构造函数：

std::vector<A> a;
A obj(1);
a.emplace_back(obj); 
a.push_back(obj);

注意：这里调用的是拷贝构造函数：拷贝->销毁临时对象。

将N个元素使用push_back插入到vector中， 求push_back操作的复杂度。参考：1、2

考虑vector每次内存扩充两倍的情况。如果我们插入N个元素， 则会引发lgN次的内存扩充，而每次扩充引起的元素拷贝次数分别为2^0, 2^1, 2^2, …, 2^lgN，把所有的拷贝次数相加得到 2^0 + 2^1 + 2^2 + … + 2^lgN = 2 * 2^lgN - 1 约为 2N次，共拷贝了N次最后一个元素，所以总的操作大概为3N。所以每个push_back操作分摊3次， 是O(1) 的复杂度。

为什么要成倍的扩容而不是一次增加一个固定大小的容量呢？

采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此使用成倍的方式扩容。

为什么是以两倍的方式扩容而不是三倍四倍，或者其他方式呢？

考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2倍的方式扩容，或者以1.5倍的方式扩容。以2倍的方式扩容，下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间。倍数过大容易使申请的新空间比之前已经申请的旧空间还大，导致空间的无法重复利用。

resize和reserve

首先必须弄清楚两个概念：

• capacity：该值在容器初始化时赋值，指的是容器能够容纳的最多的元素的个数，还不能通过下标来访问，因为此时容器中还没有创建任何对象。

• size：指的是此时容器中实际的元素个数，可以通过下标访问0 ~ (size - 1)范围内的对象。

resize和reserve区别主要有以下几点：

1. resize既分配了空间，也创建了对象；reserve表示容器预留空间，但没有创建对象，需要通过 insert() 或 push_back() 等创建对象。

2. resize既修改capacity大小，也修改size大小；reserve只修改capacity大小，不修改size大小。

3. 两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为0）；reserve只带一个参数，表示容器预留空间的大小。

vector和数组的区别

1. 内存中的位置

   C++中数组为内置的数据类型，存放在栈中，其内存的分配和释放完全由系统自动完成；vector存放在堆中，由STL库中程序负责内存的分配和释放，使用方便。

2. 大小能否变化

   数组的大小在初始化后就固定不变，而vector可以通过push_back或pop等操作进行变化。

3. 初始化

   数组不能将数组的内容拷贝给其他数组作为初始值，也不能用数组为其他数组赋值；而vector可以。

4. 执行效率

   数组效率 > vector效率。主要原因是vector的扩容过程要消耗大量的时间。

deque原理

vector是单向开口（尾部）的连续线性空间，deque则是一种双向开口的连续线性空间，虽然vector也可以在头尾进行元素操作，但是其头部操作的效率十分低下（主要是涉及到整体的移动）。deque和vector的最大差异一个是deque可以在常数时间内在头端进行元素操作，二是deque没有容量的概念，它是由分段连续空间组合而成的，可以随时增加一段新的空间并链接起来。

deque虽然也提供随机访问的迭代器，但是其迭代器并不是普通的指针，其复杂程度比vector高很多，因此除非必要，否则一般使用vector而非deque。如果需要对deque排序，可以先将deque中的元素复制到vector中，利用sort对vector排序，再将结果复制回deque。

deque由一段一段的定量连续空间组成，一旦需要增加新的空间，只要配置一段定量连续空间拼接在头部或尾部即可，因此deque的最大任务是如何维护这个整体的连续性。

deque的数据结构如下：

class deque{...
protected:typedef pointer* map_pointer;//指向map指针的指针map_pointer map;			//指向mapsize_type map_size;			//map的大小
public:...iterator begin();itertator end();...
}

deque内部有一个指针指向map，map是一小块连续空间，其中的每个元素称为一个节点node，每个node都是一个指针，指向另一段较大的连续空间，称为缓冲区，这里就是deque中实际存放数据的区域，默认大小为512bytes。

deque的迭代器数据结构如下：

struct __deque_iterator{...T* cur;		//迭代器所指缓冲区当前的元素T* first;	//迭代器所指缓冲区第一个元素T* last;	//迭代器所指缓冲区最后一个元素map_pointer node;	//指向map中的node...
}    

从deque的迭代器数据结构可以看出，为了保持与容器联结，迭代器主要包含上述4个元素。

deque迭代器的“++”、“–”操作是远比vector迭代器繁琐，其主要工作在于缓冲区边界，如何从当前缓冲区跳到另一个缓冲区。当然deque内部在插入元素时，如果map中node数量全部使用完，且node指向的缓冲区也没有多余的空间，这时会配置新的map（2倍于当前+2的数量）来容纳更多的node，也就是可以指向更多的缓冲区。在deque删除元素时，也提供了元素的析构和空闲缓冲区空间的释放等机制。

list原理

相比于vector的连续线型空间，list显得复杂许多，它的好处在于插入或删除都只作用于一个元素空间，因此list对空间的运用是十分精准的，对任何位置元素的插入和删除都是常数时间。list不能保证节点在存储空间中连续存储，也拥有迭代器，迭代器的“++”、“–”操作是指针操作，list提供的迭代器类型是双向迭代器。

list节点的结构见如下源码：

template <class T>
struct __list_node{typedef void* void_pointer;void_pointer prev;void_pointer next;T data;
}

从源码可看出list显然是一个双向链表。list与vector的另一个区别是，list在插入和接合操作之后，都不会造成原迭代器失效，而vector可能因为空间重新配置导致迭代器失效。

此外list也是一个环形链表，因此只要一个指针便能完整遍历整个链表。list中node节点指针始终指向尾端的一个空白节点，因此是一种“前闭后开”的区间结构。

list的空间管理默认采用alloc作为空间配置器，为了方便以节点大小为配置单位，还定义一个list_node_allocator函数一次性配置多个节点空间。

由于list的双向特性，支持在头部和尾部两个方向进行push和pop操作，当然还支持erase，splice，sort，merge，reverse等操作。

vector 和 list 对比

vector：一维数组

动态数组，元素在内存中连续存放，随机访问任何元素都在常数时间内完成，在尾端增删元素性能较好。

特点：元素在内存连续存放，动态数组，在堆中分配内存，元素连续存放，有保留内存，如果减少大小后内存也不会释放。

优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以它的查找效率高其时间复杂度O(1)。

缺点：由于开辟一段连续的空间，所以插入删除会需要对数据进行移动比较麻烦，时间复杂度O(n)，另外当空间不足时还需要进行扩容。

list：双向链表

双向链表，元素在内存不连续存放，在任何位置增删元素都能在常数时间完成，不支持随机访问。

特点：元素在堆中存放，每个元素都是存放在一块内存中，它的内存空间可以是不连续的，通过指针来进行数据的访问。

优点：底层实现是循环双链表，当对大量数据进行插入删除时，其时间复杂度O(1)。

缺点：底层没有连续的空间，只能通过指针来访问，所以查找数据需要遍历其时间复杂度O(n)，没有提供[]操作符的重载。

应用场景

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随机访问，而不在乎插入和删除的效率，使用vector。

list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

删除末尾的元素，指针和迭代器如何变化？删除中间的元素呢？

对于vector而言，删除某个元素以后，该元素后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。而对于list而言，删除某个元素，只有指向被删除元素的那个迭代器失效，其它迭代器不受任何影响。

map和unordered_map

内部实现机理

map底层是红黑树，内部的元素是有序的。map中的元素是按照二叉树搜索树存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map底层是哈希表，内部的元素是无序的。哈希表采用了函数映射将存储位置与记录的关键字关联起来，从而实现快速查找。

优缺点以及使用场景

map

优点：map底层是红黑树，内部的元素是有序的，查找、增删操作都可以在O(lgn)的时间复杂度下完成，因此效率非常的高。

缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红黑性质，使得每一个节点都占用大量的空间。

适用：有顺序要求的问题，用map会更高效一些。

unordered_map

优点：底层是哈希表，查找速度非常的快。

缺点：哈希表的建立比较耗费时间。

适用：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑用unordered_map。

对于unordered_map或者unordered_set容器，其遍历顺序与创建该容器时输入元素的顺序是不一定一致的，遍历是按照哈希表从前往后依次遍历的。

map下标操作 [ ] 和insert的区别

insert

insert 含义是：在 map 中，如果key存在，则插入失败；如果key不存在，就创建这个key－value。实例: map.insert((key, value))。insert接受一个pair参数，并且返回值也是一个pair。

返回值pair中：

第一个元素是一个迭代器，如果数据插入成功，则指向插入关键字的位置，用->解引用可以提取pair类型元素； 若插入失败，迭代器指向已经存在的该元素的位置。

第二个元素是一个bool类型变量，如果关键字已在map中，insert什么也不做，second返回false，插入失败；如果关键字不存在，元素被插入，second返回true。

下标操作 [ ]

利用下标操作的含义是：如果key存在，就更新value；如果key不存在，就创建这个key－value对。实例：map[key] = value。

哈希冲突

对于不同的关键字，可能得到同一个哈希地址，这种现象称之为哈希冲突，也叫哈希碰撞。

如何减少哈希冲突？

一个好的哈希函数可以有效的减少哈希冲突的出现，那什么样的哈希函数才是一个好的哈希函数呢？通常来说，一个好的哈希函数对于关键字集合中的任意一个关键字，经过这个函数映射到地址集合中任何一个集合的概率是相等的。

常用的构造哈希函数的方法有以下几种：

1. 除留取余法：关键字key除以某个不大于哈希表长m的数p，所得余数为哈希地址。即：f(key) = key % p, p ≤ m；

2. 直接定址法：取关键字或关键字的某个线性函数值为哈希地址。即： f(key) = key 或者 f(key) = a * key + b；

3. 数字分析法：假设关键字是以r为基的数（如以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可以选取关键字的若干位数组成哈希表。

如何处理哈希冲突？

虽然我们可以通过选取好的哈希函数来减少哈希冲突，但是哈希冲突终究是避免不了的。那么，碰到哈希冲突应该怎么处理呢？

1. 链地址法：在碰到哈希冲突的时候，将冲突的元素以链表的形式进行存储，也就是哈希地址相同的元素都插入到同一个链表中，元素插入的位置可以是表头（头插法），也可以是表尾（尾插法）。

2. 开放定址法：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。

3. 再哈希法：选取若干个不同的哈希函数，在产生哈希冲突的时候计算另一个哈希函数，直到不再发生冲突为止。

4. 建立公共溢出区：专门维护一个溢出表，当发生哈希冲突时，将值填入溢出表中。

其中比较常用的是链地址法，比如HashMap就是基于链地址法的哈希表结构，所以unordered_map使用开链法解决哈希冲突。

但当链表过长时，哈希表就会退化成一个链表，查找某个元素的时间复杂度又变回了O(n)。因此，当哈希表中的链表过长时就需要我们对其进行优化。二叉搜索树的查询效率是远远高于链表的。因此，当哈希表中的链表过长时，可以把这个链表变成一棵红黑树。红黑树是一个可以自平衡的二叉搜索树，查询的时间复杂度为O(lgn)，通过这样的优化可以提高哈希表的查询效率。

map和set

参考回答

1. set是一种关联式容器，其特性如下：

   （1）以红黑树作为底层容器，所有的元素都会被自动排序

   （2）元素只有key没有value，value就是key

   （3）不允许出现键值重复

   （4）不能通过迭代器来改变set的值，因为set的键值就是关键字，set的迭代器是const的

2. map和set一样是关联式容器，其特性如下：

   （1）map以红黑树作为底层容器，所有元素是通过键进行自动排序的

   （2）所有元素都是键+值存在

   （3）不允许键重复

   （4）map的键是不能修改的，但是其键对应的值是可以修改的

   综上所述，map和set底层实现都是红黑树；map和set的区别在于map的值不作为键，键和值是分开的。

AVL树、红黑树、B+树

二叉搜索树

二叉搜索树的特点是一个节点的左子树的所有节点的值都小于这个节点，右子树的所有节点的值都大于这个节点。但是当每次插入的元素都是二叉搜索树中最大的元素，就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)。

AVL树

为了解决二叉搜索树在极端情况下退化成链表的问题，**平衡二叉搜索树（AVL 树）**在二叉搜索树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过 1，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) 。

不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是十分耗时的，AVL树适合用于插入与删除次数比较少，但查找多的情况。

红黑树

除了平衡二叉搜索树，还有很多自平衡的二叉树，比如红黑树，它也是通过一些约束条件来达到自平衡。

红黑树也是一种二叉搜索树，红黑树每一个结点都会额外记录结点的颜色，红色或者黑色。通过对任何一条从根节点到叶子节点的路径上各个结点颜色的限制，红黑树确保没有一条路径会比其他路径长两倍，因此，红黑树是一种弱平衡树。 对于要求严格的AVL树来说，红黑树为了保持平衡旋转的次数较少，所以对于搜索、插入、删除操作较多的情况下，红黑树的综合能力较好。

红黑树是一种含有红黑结点并能自平衡的二叉搜索树，它必须满足下面性质：

• 性质1：每个结点要么是红色，要么是黑色
• 性质2：根节点是黑色
• 性质3：叶子结点都是黑色
• 性质4：每个红色结点的子结点一定都是黑色
• 性质5：任意一个结点到每个叶子结点的路径包含数量相同的黑色结点。

红黑树的应用：

1、广泛用于C++的STL中；

2、著名的Linux的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间;

3、IO多路复用的epoll的实现采用红黑树组织管理的的的sockfd，支持快速的增删改查;

红黑树与AVL树的区别：

红黑树是一种弱平衡二叉搜索树（红黑树确保没有一条路径比其它路径长出两倍），在相同的节点情况下，AVL树的高度低于红黑树，相对于要求严格的AVL树来说，红黑树的旋转次数少，所以对于插入与删除较多的情况，红黑树的综合能力较好。由于AVL树高度平衡，因此AVL树的查询效率更高。

B+树

自平衡二叉树虽然能保持查询操作的时间复杂度在O(logn)，但是本质上是一个二叉树，每个节点只能有 2 个子节点，那么当节点个数多的时候，树的高度也会相应变高，这样就会增加磁盘的 I/O 次数，从而影响数据查询的效率。

为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。

B+ 树就是对 B 树做了一个升级，MySQL 中索引的数据结构就是采用了 B+ 树。B+ 树与 B 树的差异主要有：

• 叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；
• 所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
• 非叶子节点的索引也会同时存在于子节点中，并且是子节点中所有索引的最大（或最小）值；
• 非叶子节点中有多少个子节点，就有多少个索引；

MySQL 默认的存储引擎 InnoDB 采用 B+ 树作为索引的数据结构，原因有：

• B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比于同时存储索引和数据的 B 树来说，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O 次数会更少。
• B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化；
• B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，只能通过树的遍历来完成，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

容器适配器

标准库提供了三种顺序容器适配器：queue(FIFO队列)、priority_queue(优先级队列)、stack(栈)。

适配器对容器进行包装，使其表现出另外一种行为。例如，stack<int, vector<int>> 实现了栈的功能，但其内部使用顺序容器vector<int>来存储数据 ，相当于是vector<int>表现出了栈的行为。

堆建⽴在完全⼆叉树上，分为⼤根堆、⼩根堆。其在STL中做priority_queue的助⼿，即以任何顺序将元素推⼊容器中，然后取出时⼀定是从优先权最⾼的元素开始取，完全⼆叉树具有这样的性质，适合做priority_queue的底层。

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

stack和queue原理

stack（栈）是一种先进后出的数据结构，只有一个入口和出口，那就是栈顶，除了获取栈顶元素外，没有其他方法可以获取到内部的其他元素。stack这种单向开口的数据结构很容易由双向开口的deque或者list形成，只需要根据stack的性质修改某些接口即可实现，stack的源码如下：

template <class T, class Sequence = deque<T>>
class stack{...
protected:Sequence c;
public:bool empty(){return c.empty();}size_type size() const{return c.size();}reference top() const {return c.back();}const_reference top() const{return c.back();}void push(const value_type& x){c.push_back(x);}void pop(){c.pop_back();}
};

从stack的数据结构可以看出，其所有操作都是围绕Sequence完成，而Sequence默认是deque数据结构。stack修改某种接口来实现栈的操作，成为容器适配器。

stack除了默认使用deque作为其底层容器之外，也可以使用双向开口的list，只需要在初始化stack时，将list作为第二个参数即可。由于stack只能操作顶端的元素，因此其内部元素无法被访问，也不提供迭代器。

queue（队列）是一种先进先出的数据结构，只有一个入口和一个出口，分别位于最底端和最顶端。除了出口元素外，没有其他方法可以获取到内部的其他元素。

类似的，queue这种先进先出的数据结构很容易由双向开口的deque或者list形成，只需要根据queue的性质修改某些接口即可实现，queue的源码如下：

template <class T, class Sequence = deque<T>>
class queue{...
protected:Sequence c;
public:bool empty(){return c.empty();}size_type size() const{return c.size();}reference front() const {return c.front();}const_reference front() const{return c.front();}void push(const value_type& x){c.push_back(x);}void pop(){c.pop_front();}
};

从queue的数据结构可以看出，其所有操作都也都是是围绕Sequence完成，Sequence默认也是deque数据结构。同样，queue也可以使用list作为底层容器，不具有遍历功能，没有迭代器。

heap原理

heap（堆）并不是STL的容器组件，是priority_queue的底层实现机制，因为大根堆总是最大值位于堆的根部，优先级最高。

二叉堆本质是一种完全二叉树，二叉树除了最底层的叶子节点之外，都是填满的，但是叶节点从左到右不会出现空隙。

完全二叉树内没有任何节点漏洞，是非常紧凑的，这样的一个好处是可以使用数组来存储所有的节点，因为当其中某个节点位于i处，其左节点必定位于2i处，右节点位于2i + 1处，父节点位于i / 2（向下取整）处。这种以数组表示二叉树的方式称为隐式表述法。

因此我们可以使用一个数组和一组堆算法来实现最大堆（每个节点的值大于等于其子节点的值）和最小堆（每个节点的值小于等于其子节点的值）。由于数组不能动态的改变空间大小，用vector代替数组是一个不错的选择。

那heap算法有哪些？常见有的插入、弹出、排序和构造算法：

push_heap插入算法

由于完全二叉树的性质，新插入的元素一定是位于树的最底层作为叶子节点，并填补由左至右的第一个空格。事实上，在刚执行插入操作时，新元素位于底层vector的end()处，之后是上溯的过程。

新元素50在插入堆中后，先放在vector的end()存着，之后执行上溯过程，调整其根结点的位置，以便满足大根堆的性质。

pop_heap算法

堆的pop操作实际弹出的是根节点，将其和vector最后一个元素进行替换，然后再为这个被替换的元素找到一个合适的安放位置，使整颗二叉树满足完全二叉树的条件。这个被挤掉的元素首先会与根结点的两个子节点比较，并与较大的子节点更换位置，如此一直往下，直到这个被挤掉的元素大于左右两个子节点，或者下放到叶子节点为止，这个过程称为下溯。

根节点68被pop之后，移到了vector的最底部，将24挤出，24被迫从根节点开始与其子节点进行比较，直到找到合适的位置安身，需要注意的是pop之后元素并没有被移走，如果要将其移走，可以使用pop_back()。

sort算法

因为pop_heap可以将当前heap中的最大值置于底层容器vector的末尾，heap范围减1，那么不断的执行pop_heap直到树为空，即可得到一个递增序列。

make_heap算法

将一段数据转化为heap，一个一个数据插入，调用上面说的两种percolate算法即可。

priority_queue原理

priority_queue（优先级队列）是一个拥有权值观念的queue，它跟queue一样是顶部入口，底部出口，在插入元素时，元素并非按照插入次序排列，它会自动根据权值（通常是元素的实值）排列，权值最高，排在最前面。

默认情况下，priority_queue使用一个大根堆完成，底层容器使用的是一般为vector，堆heap为处理规则来管理底层容器实现。

priority_queue的这种实现机制导致其不被归为容器，而是一种容器配接器。关键的源码如下：

template <class T, class Squence = vector<T>, 
class Compare = less<typename Sequence::value_tyoe>>
class priority_queue{...
protected:Sequence c; 	// 底层容器Compare comp; 	// 元素大小比较标准
public:bool empty() const {return c.empty();}size_type size() const {return c.size();}const_reference top() const {return c.front()}void push(const value_type& x){c.push_heap(x);push_heap(c.begin(), c.end(), comp);}void pop(){pop_heap(c.begin(), c.end(), comp);c.pop_back();}
};

priority_queue的所有元素，进出都有一定的规则，只有queue顶端的元素（权值最高者），才有机会被外界取用，它没有遍历功能，也不提供迭代器。

STL的两级空间配置器

首先明白为什么需要二级空间配置器？

动态开辟内存时，要在堆上申请，但若需要频繁地开辟、释放堆内存，则就会在堆上造成很多外部碎片，浪费了内存空间。随着外部碎片增多，内存分配器在找不到合适内存情况下需要合并空闲块，浪费了时间，大大降低了效率。于是就设置了二级空间配置器，当开辟内存<=128bytes时，即视为开辟小块内存，则调用二级空间配置器。一般默认选择二级空间配置器， 如果分配的内存大于128字节才选择一级空间配置器。

一级空间配置器

一级空间配置器中重要的函数就是allocate、deallocate、reallocate。一级空间配置器是以malloc()，free()，realloc()等C函数执行实际的内存配置 。大致过程是：

1. 使用allocate来分配内存，内部会调用malloc来分配内存，成功则直接返回，失败就调用处理函数；
2. 如果用户自定义了内存分配失败的处理函数就调用，没有的话就返回异常；
3. 如果自定义了处理函数就进行处理，处理完再继续尝试分配内存。

二级空间配置器

会维护16条链表，分别是0-15号链表，最小为8字节，以8字节逐渐递增，最大为128字节。传入一个字节参数，表示需要多大的内存，会自动校对到第几号链表（如需要13bytes空间，我们会给它分配16bytes大小），在找到第n个链表后查看链表是否为空，如果不为空直接从对应的free_list中取出，将已经取出的指针向后移动一位。

如果对应的free_list为空，先看其内存池是不是空，如果内存池不为空：

先检验它剩余空间是否够20个节点大小（即所需内存大小(提升后) * 20），若足够则直接从内存池中拿出20个节点大小的空间，将其中一个分配给用户使用，另外19个当作自由链表中的区块挂在相应的free_list下，这样下次再有相同大小的内存需求时，可直接取出使用。

如果不够20个节点大小，则看它是否能满足1个节点大小，如果够的话则直接拿出一个分配给用户，然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。

如果连一个节点的内存都不能满足的话，则将内存池中剩余的空间挂在相应的free_list中（找到相应的free_list），然后再给内存池申请内存。 二级空间配置器会使用malloc()从堆当中申请内存，（一次所申请的内存大小为 2 * 所需节点内存大小（提升后）* 20 + 一段额外空间），申请40块，一半拿来用，一半放内存池中。

如果malloc()失败了，说明堆上没有足够空间来分配，这时二级空间配置器会从比所需节点空间大的free_list中一一搜索，从比所需节点空间大的free_list中取出一个节点来使用。如果这也没找到，说明比其大的free_list中都没有自由区块了，那就要调用一级适配器了。

释放时调用deallocate()函数，若释放的 n > 128，则调用一级空间配置器，否则就直接将内存块挂在自由链表的合适位置。

STL二级空间配置器虽然解决了外部碎片的问题，提高了效率，但它同时增加了一些缺点：

因为自由链表的管理问题，它会把我们需求的内存块自动提升为8的倍数。若需要1个字节，它会给你8个字节，浪费了7个字节，所以它又引入了内部碎片的问题，若相似情况出现很多次，就会造成很多内部碎片。

二级空间配置器是在堆上申请大块的内存池，然后用自由链表管理。在程序执行过程中，它将申请的内存一块一块都挂在自由链表上，不会还给操作系统，并且它的实现中所有成员全是静态的，所以它申请的所有内存只有在进程结束才会释放内存，还给操作系统，由此带来的问题有：

（1）若不断的开辟小块内存，最后整个堆上的空间都被挂在自由链表上，若想开辟大块内存就会失败；

（2）若自由链表上挂很多内存块没有被使用，当前进程又占着内存不释放，这时别的进程在堆上申请不到空间，也不可以使用当前进程的空闲内存，由此就会引发多种问题。