当前位置：首页 > news >正文

【STL源码剖析】从源码看 deque ：拆解双端队列的底层实现与核心逻辑

news 2025/9/4 7:03:49

文章目录

前言
deque 的中控器
deque 的迭代器
成员
关键行为
deque 的数据结构
deque 的构造和内存管理
deque 的接口

本文并不适合STL初学者。对于那些熟练掌握 C++ 模板和 STL 的日常使用，理解内存分配与对象生命周期，并且有扎实的数据结构基础，希望深刻了解STL实现细节，从而得以提升对STL的扩充能力，或是希望藉由观察STL源代码，学习世界一流程序员身手，并藉此彻底了解各种被广泛运用之数据结构和算法的人，本文可能更适合你。

本文的源码主要来自 SGI STL（Silicon Graphics, Inc. 实现的 STL 版本）；
关于源码可以到在线网站查看：源码网站，也可以下载源码压缩包：压缩包

前言

vector是单先开口的，即只有尾部可以直接添加元素，如果想操作头部元素，需要移动后面元素；而deque是双向开口的，就是说可以直接再头尾两端进行元素的增删查改，不影响中间的元素。
请添加图片描述

deque可以在参数级别的时间下，进行头插头删，尾插尾删。实际上deque维护的是一系列分段连续空间，其随时可以增加一段新的空间。也就是说deque扩容的时候不想vector一样，找一块空的位置，拷贝原数据，释放原数据，deque可以直接开辟一段连续的空间来实现扩容，只要对这些分散的分段连续空间管理好就行了。

deque的示意图如下：
请添加图片描述

因为deque维护的空间在整体上并不是连续的，所以deque的迭代器不能像vector一样使用普通的指针作为迭代器，deque的迭代器必须能够满足从一个连续空间跳到另一个连续空间的功能。

本文将围绕4个方面，介绍deque的源码实现

deque 的中控器；
deque 的迭代器；
deque 的构造和内存管理；
deque 的接口。

本文的源码主要来自 SGI STL（Silicon Graphics, Inc. 实现的 STL 版本）；
关于源码可以到在线网站查看：源码网站，也可以下载源码压缩包：压缩包

deque 的中控器

在前言部分我们谈到，vector的扩容需要进行：开空间，拷贝，释放原来空间，这就使得代价相当高，而deque在进行头部扩容的时候只需要再配置一段定量连续空间，将该空间串接带原空间的前面即可，尾部扩容也是同理。

这就意味着deque需要将每一个连续空间维护起来，而deque就是使用一个中控器来进行维护的；
中控器本质上就是一个指针数组，指向每一个连续空间的起始位置。

deque是可以对每个连续空间的大小进行设置的，在deque的第三个模板参数，默认值是0表示每一段空间大小为512字节。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:      typedef T value_type;typedef value_type* pointer;
protected:                      // Internal typedefstypedef pointer* map_pointer;map_pointer map;size_type map_size;          // 存储map的最大容量
};

可以看到在deque中确实维护着一个T*类型的指针数组，该指针数组就是中控器，用来将每一块空空间组织起来。

请添加图片描述

当map的使用完后怎么办，map怎么进行扩容的，map能不能也像deque一样开辟空间，即map扩容时也可以在任意位置开空间，只要将这些位置管理起来就行了？？？

答案是不行的，因为map就是为了管理这些不连续的分段区间的，现在你又要让map也可以实现是任意位置扩容，这就是"鸡生蛋，蛋生鸡"的问题了。

所以map的扩容方式和vector一样都是采用：开心空间，拷贝，释放三步，但是因为map中存放的是每个空间起始位置的指针数量远小于有效数据的大小，所以map的扩容的代价几乎可以忽略。

deque 的迭代器

成员

deque是分段连续空间，所以维护其"整体连续"假象的任务就交给了迭代器来完成。

deque迭代器必须能够知道自己在哪个连续空间/缓冲区中，即在map指向的哪一个空间中；
为了防止迭代器超出该分段连续空间还需要知道该缓冲区的起始和结束位置；
以及当前迭代器指向该缓冲区的哪一个位置。

inline size_t __deque_buf_size(size_t n, size_t sz)
{return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iteratorstatic size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef T** map_pointer;typedef __deque_iterator self;T* cur;                // 当前迭代器所指向的位置T* first;              // 该分段空间的起始位置T* last;               // 该分段空间的结束位置map_pointer node;      // 在哪一个分段中};

其中决定缓冲区的大小的函数buffer_size()，默认BufSiz是0，也就是说默认deque的缓冲区大小为512字节，如果类型为_int64的话，也就是一个缓冲区可以存放8个数据。

下图是中控器，缓冲区和迭代器的关系：

请添加图片描述

在deque中有两个默认的迭代器指向deque的起始和结束位置：start,finish.

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:      
protected:                      // Data membersiterator start;iterator finish;map_pointer map;size_type map_size;
};

请添加图片描述

关键行为

迭代器不论是++ / --都有可能越界，所以迭代器必须满足在不同的缓冲区之间移动，库中使用void set_node(map_point new_node)来是进行缓冲区间的移动。

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {void set_node(map_pointer new_node) {node = new_node;                                  // 修改迭代器指向的缓冲区first = *new_node;                                // 修改迭代器缓冲区起始位置和结束位置指向last = first + difference_type(buffer_size());}
};

有了set_node迭代器在进行++和–操作的时候，只需要多一步判断看是否越界即可，如果越界就调用set_node。

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {self& operator++() {++cur;if (cur == last) {            // 越界了,跳到下一个缓冲区的起始位置set_node(node + 1);cur = first;}return *this; }self operator++(int)  {         // 直接调用前置++的实现self tmp = *this;   ++*this;return tmp;}self& operator--() {            // 越界了,跳到前一个缓冲区的末尾if (cur == first) {set_node(node - 1);cur = last;}--cur;                        // [start , last)是左闭右开的,所以让cur指向有效位置return *this;}self operator--(int) {self tmp = *this;--*this;return tmp;}};

迭代器的* , ->直接对T* cur; 操作即可：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {reference operator*() const { return *cur; }
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
};

对于迭代器的==,!=就是直接比较cur的地址是否一样，如果要比较两个迭代器的大小，就需要相比较所处的缓冲区，再比较再同一个缓冲区的先后：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {bool operator==(const self& x) const { return cur == x.cur; }bool operator!=(const self& x) const { return !(*this == x); }bool operator<(const self& x) const {return (node == x.node) ? (cur < x.cur) : (node < x.node);}
};

deque迭代器还要满足迭代器能够先减，即计算两个迭代器之间的元素个数，deque因为每个缓冲区的空间并不是连续的，所以在迭代器相减的时候要考虑中间相差的缓冲区个数：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {difference_type operator-(const self& x) const {return difference_type(buffer_size()) * (node - x.node - 1) +(cur - first) + (x.last - x.cur);}
};

difference_type就是int。

迭代器不仅要满足++，还要能够+=，在deque中如果要进行+= ，就需要先看迭代器是否会跳出当前缓冲区，如果会跳出当前缓冲区，会跳到哪一个缓冲区中：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {self& operator+=(difference_type n) {difference_type offset = n + (cur - first); // 跳跃之后对于当前缓冲区起始位置的偏移量if (offset >= 0 && offset < difference_type(buffer_size()))  // 没有跳出cur += n;else {                                                       // 跳出去了difference_type node_offset =offset > 0 ? offset / difference_type(buffer_size()): -difference_type((-offset - 1) / buffer_size()) - 1;set_node(node + node_offset);cur = first + (offset - node_offset * difference_type(buffer_size()));}return *this;}
};

其中node_offset专门用来计算目标缓冲区相对于当前缓冲区的偏移量。

      difference_type node_offset =offset > 0 ? offset / difference_type(buffer_size()): -difference_type((-offset - 1) / buffer_size()) - 1;

如果是向前移动偏移量就直接是offset / difference_type(buffer_size())；
如果是先后偏移，就不能直接使用 - offset / buffer_size())，因为这样计算的结果是向上取整的，如果结果是-0.5会取0，而我们希望的是向下取整。

有了+=的重载，后面的+，-，-=的重载都可以直接复用+=：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {self operator+(difference_type n) const {self tmp = *this;return tmp += n;}self& operator-=(difference_type n) { return *this += -n; }self operator-(difference_type n) const {self tmp = *this;return tmp -= n;}
};

有了operator +，那么deque的索引也就可以直接进行复用了：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {reference operator[](difference_type n) const { return *(*this + n); }
};

deque 的数据结构

根据上面已有的知识，我们知道deque内部成员变量一定有：中控器map，有效数据的起始位置start，有效数据的结束位置finish：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // Basic typestypedef T value_type;typedef value_type* pointer;typedef value_type& reference;typedef size_t size_type;typedef ptrdiff_t difference_type;
public:                         // Iterators
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUGtypedef __deque_iterator<T, T&, T*, BufSiz>              iterator;typedef __deque_iterator<T, const T&, const T&, BufSiz>  const_iterator;
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */protected:                      // Data memberstypedef pointer* map_pointer;iterator start;iterator finish;map_pointer map;size_type map_size;
}；

通过这些成员变量以及迭代器的接口，一些deque简单的接口就可以直接实现了：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // Basic accessorsiterator begin() { return start; }iterator end() { return finish; }reference operator[](size_type n) { return start[difference_type(n)]; }reference front() { return *start; }reference back() {iterator tmp = finish;--tmp;return *tmp;}size_type size() const { return finish - start;; }size_type max_size() const { return size_type(-1); }bool empty() const { return finish == start; }
}；

deque 的构造和内存管理

deque不仅要对缓冲区进行扩容，可能还需要对map进行扩容，所以deque提供了两个专属的空间配置器：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
protected:                      // Internal typedefstypedef T value_type;typedef value_type* pointer;typedef simple_alloc<value_type, Alloc> data_allocator;  // 为缓冲区进行扩容typedef simple_alloc<pointer, Alloc> map_allocator;      // 为map进行扩容
}；

先看一下deque提供的一个用n个value进行初始化：deque(int n , value_type& value) :

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:deque(long n, const value_type& value): start(), finish(), map(0), map_size(0){fill_initialize(n, value);     // 实现见下}
}；template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_type n,const value_type& value) {create_map_and_nodes(n);      // 为map和缓冲区开辟空间,详细代码见下map_pointer cur;__STL_TRY {for (cur = start.node; cur < finish.node; ++cur)      // 将每个缓冲区进行初始化,除了最后一个uninitialized_fill(*cur, *cur + buffer_size(), value);uninitialized_fill(finish.first, finish.cur, value);  // 最后一个单独进行初始化,因为最后一个可能没满}
#       ifdef __STL_USE_EXCEPTIONScatch(...) {for (map_pointer n = start.node; n < cur; ++n)destroy(*n, *n + buffer_size());destroy_map_and_nodes();throw;}
#       endif /* __STL_USE_EXCEPTIONS */
}template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {size_type num_nodes = num_elements / buffer_size() + 1;  // map的大小map_size = max(initial_map_size(), num_nodes + 2);       // 如果num<8 默认至少开8个,如果大于8,默认会在map的左右两边多开一个map = map_allocator::allocate(map_size);map_pointer nstart = map + (map_size - num_nodes) / 2;   // deque的map在使用的时候不是从头先后使用的,优先使用中间的,从中间向两边扩map_pointer nfinish = nstart + num_nodes - 1;map_pointer cur;__STL_TRY {for (cur = nstart; cur <= nfinish; ++cur)       // 开辟缓冲区*cur = allocate_node();}
#     ifdef  __STL_USE_EXCEPTIONS catch(...) {for (map_pointer n = nstart; n < cur; ++n)deallocate_node(*n);map_allocator::deallocate(map, map_size);throw;}
#     endif /* __STL_USE_EXCEPTIONS */start.set_node(nstart);finish.set_node(nfinish);start.cur = start.first;finish.cur = finish.first + num_elements % buffer_size();  // 设置结束位置
}

在使用map的时候并不是直接从前往后进行使用的，而是从中间位置开始，这样可以保证在进行头插的时候可以直接添加缓冲区，不需要对map进行扩容。

让我们看看deque在push_back()时是如何处理的，如果容器不够会怎么样：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // push_* and pop_*void push_back(const value_type& t) {if (finish.cur != finish.last - 1) {  // 空间够,直接进行插入construct(finish.cur, t);++finish.cur;}elsepush_back_aux(t);                   // 空间不够}
};

deque是如何对待缓冲区用完的情况：

// Called only if finish.cur == finish.last - 1.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {value_type t_copy = t;reserve_map_at_back();                      // 判断map是否需要扩容*(finish.node + 1) = allocate_node();       // 开辟新的缓冲区__STL_TRY {construct(finish.cur, t_copy);            // 调用构造函数进行初始化finish.set_node(finish.node + 1);         // 调整finish迭代器状态finish.cur = finish.first;}__STL_UNWIND(deallocate_node(*(finish.node + 1)));
}

deque如何检查以及对map进行扩容的：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
protected:void reserve_map_at_back (size_type nodes_to_add = 1) {if (nodes_to_add + 1 > map_size - (finish.node - map))reallocate_map(nodes_to_add, false);}
};template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,bool add_at_front) {size_type old_num_nodes = finish.node - start.node + 1;  // 之前的map节点使用数量size_type new_num_nodes = old_num_nodes + nodes_to_add;  // 需要节点个数map_pointer new_nstart;if (map_size > 2 * new_num_nodes) {  // map空间够new_nstart = map + (map_size - new_num_nodes) / 2  // 调整map使用的起始位置,因为map可能正在进行头插的时候空间不够的,所以如果是头插,在前面要留够头插的空间+ (add_at_front ? nodes_to_add : 0);if (new_nstart < start.node)        // 根据new_satrt和start二点位置判断对原数据如何拷贝,是从或往前还是从前往后              copy(start.node, finish.node + 1, new_nstart);elsecopy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);}else {// map空间不够}start.set_node(new_nstart);                         // 调整start和finish迭代器finish.set_node(new_nstart + old_num_nodes - 1);
}

上面if条件如果成立，说明map空间足够，只不过可能因为一直在尾插导致map数组后面空间用完了，但是前面还有很多空间没有使用，体现出头重脚轻的状况，此时就不需要再进行扩容了，只需要调整一下map使用的起始位置就行了。

如果map空间确实不够了：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
protected:void reserve_map_at_back (size_type nodes_to_add = 1) {if (nodes_to_add + 1 > map_size - (finish.node - map))reallocate_map(nodes_to_add, false);}
};template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,bool add_at_front) {size_type old_num_nodes = finish.node - start.node + 1;size_type new_num_nodes = old_num_nodes + nodes_to_add;map_pointer new_nstart;if (map_size > 2 * new_num_nodes) {// 空间够}else {size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;  // 需要的空间大小,map扩容至少二倍扩所以取max ,并且在首尾要预留空间所以+2map_pointer new_map = map_allocator::allocate(new_map_size);  // 开辟新的mapnew_nstart = new_map + (new_map_size - new_num_nodes) / 2     // 找map中间位置+ (add_at_front ? nodes_to_add : 0);copy(start.node, finish.node + 1, new_nstart);                // 拷贝原数据map_allocator::deallocate(map, map_size);                     // 销毁原mapmap = new_map;map_size = new_map_size;}start.set_node(new_nstart);finish.set_node(new_nstart + old_num_nodes - 1);
}

头插道理也是一样的：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:void push_front(const value_type& t) {if (start.cur != start.first) {construct(start.cur - 1, t);--start.cur;}elsepush_front_aux(t);}
};// Called only if start.cur == start.first.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {value_type t_copy = t;reserve_map_at_front();*(start.node - 1) = allocate_node();__STL_TRY {start.set_node(start.node - 1);start.cur = start.last - 1;construct(start.cur, t_copy);}
#     ifdef __STL_USE_EXCEPTIONScatch(...) {start.set_node(start.node + 1);start.cur = start.first;deallocate_node(*(start.node - 1));throw;}
#     endif /* __STL_USE_EXCEPTIONS */
}

deque 的接口

deque的接口很多，此处只间接几个最常用的。

deque的pop接口：

先以pop_back()为例：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:void pop_back() {if (finish.cur != finish.first) {  // 不是当前缓冲区的起始位置--finish.cur;                    // 直接让finish--,将删除位置对象进行析构destroy(finish.cur);}else                               // 是缓冲区的起始位置pop_back_aux();}
};

如果调用pop_back()的时候，删除的是缓冲区的第一个元素，那就需要跳到上一个缓冲区的末尾。

// Called only if finish.cur == finish.first.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>:: pop_back_aux() {deallocate_node(finish.first);            // 释放最后一个缓冲区finish.set_node(finish.node - 1);         // 跳到上一个缓冲区中finish.cur = finish.last - 1;             // 调整finish的位置destroy(finish.cur);                      // 析构删除位置对象
}

pop_front()也是同理：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:void pop_front() {if (start.cur != start.last - 1) {destroy(start.cur);++start.cur;}else pop_front_aux();}
};template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_front_aux() {destroy(start.cur);deallocate_node(start.first);start.set_node(start.node + 1);start.cur = start.first;
}

在deque中还提供了一个clear()用来将所有数据进行清除，清除的时候并不会将所有缓冲区都删除，还会保留一个，以备后面使用。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::clear() {for (map_pointer node = start.node + 1; node < finish.node; ++node) {  // (start, finish)中的所有缓冲区都销毁destroy(*node, *node + buffer_size());data_allocator::deallocate(*node, buffer_size());}if (start.node != finish.node) {       // satrt和finish是两个不同的缓冲区destroy(start.cur, start.last);      // 将start缓冲区中的元素都删除destroy(finish.first, finish.cur);   // 将finish缓冲区中的元素都删除data_allocator::deallocate(finish.first, buffer_size());  // 将finish缓冲区删除,只保留一个缓冲区即start}else                                // start和finish是同样一个destroy(start.cur, finish.cur);finish = start;}
};

以上就是clear()的源码，还是很简单的；

下面看一下删除指定位置元素：iterator erase(iterator pos),对于指定位置删除，需要将该位置前的数据整体向后移动，或将该位置后的数据整体向前移动，至于选择哪一个移动取决于前面和后面数据的个数。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // Eraseiterator erase(iterator pos) {iterator next = pos;++next;difference_type index = pos - start;   // pos前的元素个数if (index < (size() >> 1)) {           // 前面元素少, 将前面元素整体向后面移动copy_backward(start, pos, next);pop_front();                         // 去除头部冗余数据}else {                                 // 后面元素少, 间后面元素整体向前移动copy(next, finish, pos);pop_back();                          // 去除尾部冗余数据}return start + index;}
};

erase还可以删除一个指定区间：iterator erase(iterator first , iterator last)

template <class T, class Alloc, size_t BufSize>
deque<T, Alloc, BufSize>::iterator 
deque<T, Alloc, BufSize>::erase(iterator first, iterator last) {if (first == start && last == finish) {   // 删除整个deque, 直接调用clear()clear();return finish;}else {difference_type n = last - first;       // 计算删除元素个数difference_type elems_before = first - start;  // 删除元素前面的个数if (elems_before < (size() - n) / 2) {         // 前面元素少,移动前面的元素copy_backward(start, first, last);iterator new_start = start + n;destroy(start, new_start);for (map_pointer cur = start.node; cur < new_start.node; ++cur) data_allocator::deallocate(*cur, buffer_size());  // 销毁头部多出来的冗余数据start = new_start;}else {copy(last, finish, first);iterator new_finish = finish - n;destroy(new_finish, finish);for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)data_allocator::deallocate(*cur, buffer_size());finish = new_finish;}return start + elems_before;}
}

以上都是处理删除是越界的问题，下面看一下insert如何处理insert的越界问题：

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // Insertiterator insert(iterator position, const value_type& x) {if (position.cur == start.cur) {               // 头插 push_front(x);return start;}else if (position.cur == finish.cur) {         // 尾插 push_back(x);iterator tmp = finish;--tmp;return tmp;}else {return insert_aux(position, x);              // 指定位置插入} }
};

指定位置插入：

template <class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {difference_type index = pos - start;         // 前面元素个数value_type x_copy = x;if (index < size() / 2) {                    // 前面元素少push_front(front());                       // 头插一个元素,只是用来开一个空间,后面会被覆盖iterator front1 = start;++front1;iterator front2 = front1;++front2;pos = start + index;iterator pos1 = pos;++pos1;copy(front2, pos1, front1);                // 用[front2 , pos1)覆盖到front1后面}else {                                       // 后面元素少push_back(back());                         // 头插一个元素iterator back1 = finish;--back1;iterator back2 = back1;--back2;pos = start + index;copy_backward(pos, back2, back1);         // 用[pos , back2)覆盖到back1前面}*pos = x_copy;                              // 插入元素return pos;
}