1. deque底层实现原理

1.1 概述

一句话描述：deque的目的是实现一个双端数组，既可以从队列头部插入和删除元素，也可以从队列尾部插入和删除元素。

底层实现：deque的底层实现是一个双向开口的连续线性空间，可以理解为一个动态数组，其内部维护了多个连续的存储空间，并通过一个索引数组（称为map）来管理这些连续的存储空间。

1.2 原理图

1.3 类结构

deque的内部类结构主要由以下几个部分构成：

1. class deque : protected _Deque_base

   这是deque的主体类，它包含了一些基本操作函数如push_back，push_front，pop_back等。deque类继承了_Deque_base类。

   template <class T, class Alloc = alloc>
   class deque {
   public:
       // deque的迭代器
       typedef _Deque_iterator<T, T&, T*>             iterator;
       // 省略其他typedef定义...
   
   protected:
       // deque的数据表示
       typedef pointer*                               map_pointer;
       // 省略其他typedef定义...
       
       // deque的数据成员
       map_pointer _M_map; // 指向map
       size_type _M_map_size; // map大小
       iterator _M_start; // deque开始的位置
       iterator _M_finish; // deque结束的位置
   };
   

2. _Deque_base._Deque_impl

   _Deque_base._Deque_impl是deque的底层实现类，它包含了deque的内部结构和元数据：

   • _M_map：一个指针数组，数组中每一个元素都是一个指向连续存储空间的指针。

   • _M_map_size：记录_M_map的容量，即map中最多可以容纳的指针数量。

   • _M_start：记录map数组中首个连续空间的信息，它是一个迭代器，指向当前deque的首元素。

   • _M_finish：记录map数组中最后一个连续空间的信息，它是一个迭代器，指向当前deque的末元素。

3. _Deque_iterator

   _Deque_iterator是deque的迭代器类，它用于遍历deque中的元素：

   • _M_cur：指向当前正在遍历的元素。

   • _M_first：指向当前连续空间的首地址。

   • _M_last：指向当前连续空间的末尾地址。

   • _M_node：用于指向map数组中存储的指向连续空间的指针。

   template <class T, class Ref, class Ptr, size_t BufSiz>
   struct _Deque_iterator {
       // 一些类型定义，省略...
   
       T* _M_cur; // 指向buffer中的当前元素
       T* _M_first; // 指向buffer的头
       T* _M_last; // 指向buffer的尾
       T** _M_node; // 指向map中的控制中心
       // ...
   };
   

4. _deque_buf_size

   _deque_buf_size函数决定了每个连续空间中能容纳元素的个数，它的设计原则是如果元素的大小较小，则可以存储更多的元素，如果元素的大小较大，则只存储少数几个元素。

   inline size_t _deque_buf_size(size_t __size) {
       return __size < 512 ? size_t(512 / __size) : size_t(1);
   }
   

5. _M_initialize_map

   _M_initialize_map函数用于创建map，并配置缓冲区。一开始，_M_start和_M_finish指向map的中间的位置，这样可以公平地往上或者向下扩展空间。

   void _M_initialize_map(size_t __num_elements) {
       // 计算需要多少个节点（至少需要一个）
       size_t __num_nodes = __num_elements / _S_buffer_size() + 1;
   
       // 一个map管理最少8个，最多是“所需节点数加2”（前后各预留一个，扩充用）
       _M_map_size = max((size_t) InitialMapSize, __num_nodes + 2);
       _M_map = _M_allocate_map(_M_map_size);
   
       // 让nstart和nfinish指向map所拥有之全部节点的最中央区段
       // 保持在中央，可以使头尾两端的扩充能量一样大。每个节点对应一个缓冲区。
       map_pointer __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
       map_pointer __nfinish = __nstart + __num_nodes;
   
       __STL_TRY {
           // 为这些节点配置缓冲区。这些缓冲区对应deque的内容初始空间
           for (map_pointer __cur = __nstart; __cur < __nfinish; ++__cur)
               *__cur = _M_allocate_node();
       }
       __STL_UNWIND(_M_deallocate_map(_M_map, _M_map_size), _M_map = 0);
       // 更新迭代器start, finish
       _M_start._M_set_node(__nstart);
       _M_start._M_cur = _M_start._M_first;
       _M_finish._M_set_node(__nfinish - 1);
       _M_finish._M_cur = _M_finish._M_first + __num_elements % _S_buffer_size();
   }
   

1.4 操作函数

1. push_back

   push_back函数用于在deque的尾部添加元素，它首先会检查当前连续空间是否有足够的空间存储新的元素，如果没有，则需要在map

   中分配一个新的连续空间。同时，还需要检查map空间是否足够，如果不够，则需要重新分配一个更大的map。

   void push_back(const value_type& __t) {
       if (_M_finish._M_cur != _M_finish._M_last - 1) {
           // 最后缓冲区还有两个（含）以上的备用空间
           _Construct(_M_finish._M_cur, __t);
           ++_M_finish._M_cur;
       } else
           // 最后缓冲区只剩一个备用空间
           _M_push_back_aux(__t);
   }
   

2. pop_back

   pop_back函数用于删除deque的尾部元素，如果删除后当前连续空间没有数据了，则需要释放该连续空间，并且更新map和_M_finish。

   void pop_back() {
       if (_M_finish._M_cur != _M_finish._M_first) {
           // 最后缓冲区有多于一个元素
           --_M_finish._M_cur;
           _Destroy(_M_finish._M_cur);
       } else
           // 最后缓冲区仅剩一个元素
           _M_pop_back_aux();
   }
   

2. 什么时候使用vector、list、deque

2.1 vector

• 使用场景：如果需要高效地快速访问（随机存取），并且不在乎插入和删除的效率，使用vector。vector在内存中是连续的，所以可以利用缓存，访问效率高。而插入和删除需要移动大量元素，所以效率较低。

• 例子：一个典型的应用场景是，如果你有一个学生列表，并且需要频繁地按照索引查询学生信息，但是很少需要添加或删除学生，那么这种情况下使用vector是最合适的。

#include <vector>

struct Student {
    int id;
    std::string name;
};

std::vector<Student> students;

// 查询学生信息
Student getStudent(int index) {
    return students[index];
}

2.2 list

• 使用场景：如果需要大量的插入和删除，而且不关心快速访问（随机存取），使用list。list的插入和删除只需要改变几个指针，所以效率很高。但是由于数据不连续，无法直接通过索引访问，所以访问效率低。

• 例子：一个典型的应用场景是，如果你正在实现一个任务队列，并且需要频繁地添加和删除任务，但是不需要按照索引查询任务，那么这种情况下使用list是最合适的。

#include <list>

struct Task {
    int id;
    std::string description;
};

std::list<Task> tasks;

// 添加任务
void addTask(const Task& task) {
    tasks.push_back(task);
}

// 删除任务
void deleteTask(std::list<Task>::iterator it) {
    tasks.erase(it);
}

2.3 deque

• 使用场景：如果需要快速访问（随机存取），并且关心两端数据插入和删除，使用deque。deque既可以快速地访问元素，又可以在两端高效地插入和删除元素。

• 例子：一个典型的应用场景是，如果你正在实现一个双端任务队列，并且需要频繁地从两端添加和删除任务，同时也需要按照索引查询任务，那么这种情况下使用deque是最合适的。

#include <deque>

struct Task {
    int id;
    std::string description;
};

std::deque<Task> tasks;

// 添加任务到队列头部
void addTaskToFront(const Task& task) {
    tasks.push_front(task);
}

// 添加任务到队列尾部
void addTaskToBack(const Task& task) {
    tasks.push_back(task);
}

// 查询任务


Task getTask(int index) {
    return tasks[index];
}

3. priority_queue的底层实现原理

3.1 一句话概括：用堆来实现优先级队列

优先队列的一种常见实现方式是使用堆，这是因为堆具有“大致有序”的特性，这使得堆非常适合用来实现优先队列。堆数据结构可以快速地找出最大值（最大堆）或最小值（最小堆）。

3.2 堆结构

堆是一种特殊的完全二叉树，它具有以下特性：

1. 完全二叉树

   堆总是一棵完全二叉树，这意味着树的每一层都有左侧子节点，并且只有最后一层可以没有右侧子节点。此外，最后一层的节点必须从左到右填充。这些特性使得堆可以用数组来存储，数组中每个索引表示的节点和其父节点、子节点之间的关系可以用以下公式表示：

   • 给定一个索引 i（0-indexed）
     • 其父节点的索引为 (i - 1) / 2
     • 左子节点的索引为 2 * i + 1
     • 右子节点的索引为 2 * i + 2
   • 代码实现：

   int parent(int i) { return (i - 1) / 2; }
   int left_child(int i) { return 2 * i + 1; }
   int right_child(int i) { return 2 * i + 2; }
   

2. 最大堆、最小堆

   最大堆和最小堆是两种常见的堆结构。

   • 在最大堆中，每个节点的值都大于或等于其子节点的值。因此，最大的元素存储在根节点（即堆顶）。
   • 在最小堆中，每个节点的值都小于或等于其子节点的值。因此，最小的元素存储在根节点（即堆顶）。

   注意，这里的“大于”和“小于”关系只限于父子节点之间，而与兄弟节点之间无关。

3. 增加节点和删除节点

   在堆中增加和删除节点的过程需要保持堆的特性。当添加节点时，节点首先被添加到数组的末尾，然后通过一种称为"上浮"的过程调整到正确的位置。当删除节点时（通常是删除根节点），最后一个元素被移动到堆顶，然后通过一种称为"下沉"的过程调整到正确的位置。

   void push_heap(vector<int>& heap, int value) {
       heap.push_back(value);  // 将新元素放到数组的末尾
       int i = heap.size() - 1;
       while (i > 0 && heap[parent(i)] < heap[i]) {
           // 如果新添加的元素大于其父节点，则交换它们
           swap(heap[i], heap[parent(i)]);
           i = parent(i);  // 将索引移动到父节点
       }
   }
   
   void pop_heap(vector<int>& heap) {
       heap[0] = heap.back();  // 将最后一个元素移动到堆顶
       heap.pop_back();  // 删除最后一个元素
   
       // 下沉过程
       int i = 0;
       while (true) {
           int left = left_child(i);
           int right = right_child(i);
           int largest = i;
   
           if (left < heap.size() && heap[left] > heap[largest]) {
               largest = left;
           }
           if (right < heap.size() && heap[right] > heap[largest]) {
               largest = right;
           }
   
           if (i != largest) {
               swap(heap[i], heap[largest]);
               i = largest;
           } else {
               break;
           }
       }
   }
   

3.3 底层容器

priority_queue通常用vector作为底层容器，但也可以使用deque。选择哪种容器主要取决于以下因素：

• 提供front操作，用于访问队首元素（即堆顶元素）。
• 提供push_back操作，用于在队尾添加元素。
• 提供pop_back操作，用于删除队尾元素。

3.4 STL对堆结构提供的接口

STL为堆提供了一些接口，如下：

• make_heap(first, last, comp)：根据比较函数comp，把区间[first, last)的元素构建成一个堆。
• push_heap(first, last, comp)：把区间[first, last)中最后一个元素插入到前面的堆中，形成新的堆。

#include <algorithm>
#include <vector>
#include <functional>

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

std::make_heap(v.begin(), v.end(), std::greater<>());  // 创建一个小根堆
v.push_back(8);  // 添加一个元素到数组末尾
std::push_heap(v.begin(), v.end(), std::greater<>());  // 将新元素添加到堆中

3.5 支持的接口

priority_queue支持的接口主要有以下几种：

• empty()：检查队列是否为空。
• size()：返回队列中元素的个数。
• top()：返回队首元素（即堆顶元素）。
• push(elem)：向队尾添加元素，然后重新调整堆。
• pop()：删除队首元素（即堆顶元素），然后重新调整堆。

#include <queue>

std::priority_queue<int> pq;  // 默认为最大堆
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top() << std::endl;  // 输出：4
pq.pop();
std::cout << pq.top() << std::endl;  // 输出：3

4. multiset的底层实现原理

4.1 一句话描述

multiset 是一个基于红黑树实现的集合，它允许存储重复的键值，且元素始终按照排序顺序进行组织。

4.2 红黑树

红黑树是一种自平衡的二叉搜索树，它通过颜色和特定的属性来确保平衡，从而使得在最坏情况下，基本的操作（如插入、删除和查找）的时间复杂度仍为 $O(\log n)$。

中序遍历红黑树可以得到一个有序序列，这是由红黑树作为二叉搜索树的性质决定的。它通过对节点的键值进行比较来维持树的有序性。

4.3 STL 中红黑树的实现

在 STL 中，红黑树的实现模板是 _Rb_tree，其主要结构如下：

template<typename _Key, typename _Val, typename _KeyOfValue, typename _Compare, typename _Alloc = allocator<_Val> >
struct _Rb_tree { /* ... */ };

其中：

• _Key 是键值的类型。
• _Val 是节点数据的类型，通常是键值和实值的组合。
• _KeyOfValue 是一个函数或者函数对象，用于从 _Val 类型中提取 _Key 类型的值。
• _Compare 是一个函数或者函数对象，用于比较键值。
• _Alloc 是内存分配器。

每个 _Rb_tree 节点是 _Rb_tree_node 结构，其中包含一个 _M_storage 成员，用于存储实际的值。

struct _Rb_tree_node : public _Rb_tree_node_base
{
  typedef _Rb_tree_node* _Link_type;
  _Val _M_storage;
};

原理图：

红黑树提供了两个重要的接口：

• _M_insert_unique：插入数据的时候，保证键值唯一。
• _M_insert_equal：插入数据的时候，允许键值重复。

4.4 multiset 的实现

multiset 是在红黑树 _Rb_tree 的基础上实现的，其定义如下：

template<typename _Key, typename _Compare = less<_Key>, typename _Alloc = allocator<_Key> >
class multiset
{
  typedef _Rb_tree<key_type, value_type, _Identity<value_type>, key_compare, _Key_alloc_type> _Rep_type;
  _Rep_type _M_t;  // Red-black tree representing multiset.
  // ...
};

其中，value_type 存储的就是 key，key 是不允许被修改的，所以 multiset 中的元素是不可修改的（常常称为"immutable"

）。

在插入元素时，multiset 会调用 _M_insert_equal 方法，这使得 multiset 可以存储具有相同键值的元素。