【C++ STL】deque结构和迭代器

vector是单向开口的连续线性空间；deque是一种双向开口的“连续”空间。

也就是意味着，vector在某一端（尾端）的插入删除效率较高，而deque在两端的开口处插入删除效率都很高！
deque不存在容量的概念。即deque不会发生像vector一样的：“重新开辟空间、拷贝数据、释放原来的空间”的操作。
deque的迭代器实现并不是类似于vector一样使用原生指针。而是必须进行封装。

1. deque的数据结构

deque在逻辑上貌似是连续的空间接口。但是事实并非如此……

deque是由一段一段的定量大小的连续空间构成的。所以实际上如果在deque的头部或者尾部增加新的数据，有必要地为deque继续配置一段连续的空间，连接在deque的头部或者尾部。

那么deque是如何维护一段一段看起来连续的空间呢？那么不得不提到它的特殊的结构：deque的中控器。

例如：我们给出一个连续空间为可容纳8个T类型的元素的空间。

我们的deque就是这些连续空间的管理者一般。这些连续的空间都有一个共同的特征：它们的数据类型一定是一致的且空间一定是连续、容量大小且是一定的……例如，所以我们管理这些连续的内存空间，类似于二维数组方式管理。但是不能直接使用二维数组，因为我们的deque还有扩充机制。但是我们可以利用相同的思想进行管理这些连续空间！

如图：class deque中会提供一个字段，类型一定是T**指向的就是管理连续空间内存块的中控器。每一个元素类型都指向一个连续的空间。deque通过map字段，就可以找到对应的数据位置，从而进行对数据的增删……我们也需要配置一个size来确定中控器的大小。

我们称呼map中的元素都是一个node（节点）。

注：值得一提的是，为了实现双端的插入删除，deque一定需要做的工作是，数据优先插入在中控器的中间数据的位置，将两端先空下来……当中控器的使用率已经满载，deque就会重新配置一个更大的空间来作为中控器，这样就不会发生大量的数据的拷贝，只有指针的拷贝……

2. deque的迭代器

2.1 迭代器的设计

因为deque的看起来的连续空间的数据结构，那么迭代器的设计就需要三思了，我们应该如何准确定位一个数据的迭代器位置呢？

迭代器需要确定自己的所在的连续空间的node。指向当前数据所在的map节点。
迭代器需要确定自己这段空间的起始和结束位置。方便判断自己是否处于缓冲区的边缘，方便进行下一节点的转移。
迭代器需要确定自己的数据指向，即也需要一个指向当前位置的指针。
……

//……
class deque_iterator
{
private://protected:
	T* cur; //指向当前数据的位置地址
	T* first; //指向连续空间的起始位置地址
	T* last; //指向连续空间的结束位置地址 [first, last)
	T** node; //指向当前连续空间在map中的节点位置的起始地址
};

似乎迭代器的设计就应该这样：

注意：

我们接下来需要考虑一个点：既然deque的数据的插入删除是在map的中间开始的，那么如何得到它的起始和结束的迭代器呢？即如何设计：begin()和end()函数呢?

由于deque本来就是数据的管理者，所以它清楚的知道当前的数据已经插入和删除到哪里了……所以，我们可以直接让deque中自行维护两个字段：iterator start和iterator finish。这两个字段就是用来维护deque的起始迭代器和结束迭代器的。每次插入删除，更新这两个迭代器即可……

2.2 迭代器的操作(与vector的随机访问相比较)

了解迭代器的操作：例如++、--、-=……等操作，我们就可以知道deque的迭代器的访问效率究竟如何了……

假设每一个配置的空间是8个元素大小。实际上deque的默认空间数是512byte（SGI STL）
了解deque的operator+=(size_t n) 操作：（接口有封装，我们假设是这样的）
1. 我们需要确定当前迭代器 +n之后在当前空间起始位置的偏移量offset = (cur - last) + n
2. 判断offset是否在当前连续空间：
  
  例如：if(offset >= 0 && offset 。
  - 是。cur += n;返回迭代器即可。
  - 否。
    - 求出offset在map中节点的偏移量offset_node = offset > 0 ? offset / (last - first) : (offset + 1) / (last - first) - 1;
    - 更新node：node += offset_node;
      更新first：*node;
      更新last：first + size;（size为连续空间的大小）
      更新cur：cur = first + (offset - (offset_node * size));
3. 返回当前位置的迭代器即可。

似乎接口就是这样设计：

#include   // for ptrdiff_t

template class T>
struct __deque_iterator {
    // 类型定义（SGI STL标准）
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef __deque_iteratorT> self;

    // 公开成员（SGI中为保护成员，此处暴露以便理解）
    pointer cur;    // 当前元素指针
    pointer first;  // 当前缓冲区起始指针
    pointer last;   // 当前缓冲区结束指针（最后一个元素的下一位）
    pointer* node;  // 指向中控数组（map）的当前节点

    // SGI STL中缓冲区大小计算（根据元素大小动态调整）
    static size_type buffer_size() {
        return 512 / sizeof(T);  // 保证每个缓冲区至少16字节（若T>32字节则为1个元素）
    }

    // 切换到指定的中控节点（SGI中的核心操作，此处简化为公开函数）
    void set_node(pointer* new_node) {
        node = new_node;
        first = *new_node;
        last = first + buffer_size();  // 缓冲区结束位置 = 起始 + 容量
    }

    // 核心：operator+=实现
    self& operator+=(difference_type n) {
        difference_type offset = n + (cur - first);  // 计算相对于当前缓冲区起始的总偏移

        if (offset >= 0 && offset  difference_type(buffer_size())) {
            // 情况1：移动后仍在当前缓冲区
            cur += n;
        } else {
            // 情况2：需要跨缓冲区移动
            // 计算需要移动的节点数（中控数组的索引偏移）
            difference_type node_offset;
            if (offset  0) {
                // 向前移动（n为负数）
                node_offset = (offset + 1) / buffer_size() - 1;
            } else {
                // 向后移动（n为正数）
                node_offset = offset / buffer_size();
            }
            // 切换到目标节点
            set_node(node + node_offset);
            // 计算在新缓冲区中的位置
            cur = first + (offset - node_offset * buffer_size());
        }
        return *this;
    }
};

所以实际上的deque支持的operator[]底层一定会调用迭代器的operator[]最后一定会调用operator+=操作符！所以我们从这样的角度来看。deque的随机访问数据的能力真的会很强吗？不说很差，但是一定不如vector！！

2.3 deque的随机插入(与list的随机插入比较)

实际上，小编就不用在这里与list的随机插入删除来进行进行比较的了，效率一定是不如list。list在常数级别的时间复杂度内完成，而deque一定会发生的就是对数据的移动……

3. 小结

3.1 vector、deque 和 list 容器优势对比分析

特性	vector	deque	list
随机访问	最优（O(1)，连续内存直接寻址）	优秀（O(1)，通过中控数组间接寻址）	最差（O(n)，需遍历链表）
头部操作	最差（O(n)，需整体移动元素）	最优（O(1)，直接操作首缓冲区）	优秀（O(1)，仅修改指针）
尾部操作	最优（O(1)，预留空间足够时）	优秀（O(1)，尾缓冲区未满时）	优秀（O(1)，仅修改指针）
中间插入/删除	最差（O(n)，需移动后续元素）	较差（O(n)，需移动当前缓冲区元素）	最优（O(1)，仅修改相邻指针）
内存利用率	较好（连续内存，局部性好）	中等（缓冲区可能有碎片）	较差（每个元素需额外存储指针）
迭代器稳定性	插入/删除中间元素时失效	插入/删除中间元素时当前缓冲区迭代器失效	插入/删除不影响其他迭代器（仅被删元素迭代器失效）
扩容效率	可能触发整体拷贝（代价高）	无需整体拷贝（新增缓冲区即可）	无扩容问题（动态分配单个元素）

3.2 劣势对比

容器	主要劣势
vector	1. 头部/中间插入/删除效率低（O(n)） 2. 扩容时可能拷贝整个数组（代价高） 3. 预留空间可能造成内存浪费
deque	1. 中间插入/删除效率低（O(n)） 2. 内存局部性不如 vector（跨缓冲区访问缓存不友好） 3. 迭代器实现复杂（需跟踪缓冲区边界）
list	1. 无随机访问能力（访问第 k 个元素需 O(n)） 2. 内存开销大（每个元素额外存储两个指针） 3. 遍历效率低（缓存不友好）

3.3 适用场景

vector：适合频繁随机访问、尾部增删，且元素数量变化相对可预测的场景（如存储动态数组、实现栈等）。
deque：适合频繁在头部和尾部操作，且需要随机访问的场景（如实现队列、双端队列等）。
list：适合频繁在任意位置插入/删除，且对随机访问需求低的场景（如实现链表、需要频繁拆分/合并的结构等）。

4. 总结

优先用 vector：需要高效随机访问，且操作集中在尾部。
优先用 deque：需要高效的头尾操作，且需要随机访问。
优先用 list：需要频繁在中间插入/删除，且不依赖随机访问。

实际开发中，vector 因简单高效是最常用的选择，deque 适合特定的双端操作场景，list 则在频繁修改中间元素时更有优势。

文章来源于互联网:【C++ STL】deque结构和迭代器