【STL源码剖析】deque 的使用

别院深深夏席清，石榴开遍透帘明。

树阴满地日当午，梦觉流莺时一声。

目录

deque 的结构

deque 的迭代器剖析

deque 的使用

编辑

deque 的初始化

deque 的容量操作

deque 的访问操作

在 pos 位置插入另一个向量的 [forst，last] 间的数据编辑

删除 [first，last] 之间的元素

assign的用法

deque 的优缺点

契子✨

deque （ double-ended queue ，双端队列）是有下标顺序容器，它允许在其首尾两段快速插入及删除。另外，在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。

deque 是一块连续的空间（至少逻辑看来如此），连续空间我们可能会想到 array（数组）或者vector。array 无法成长，vector 虽然可以成长但是只有尾端成长，而且扩容（成长）只是假象，实际上是：<1>另寻更大的空间、<2>将原资料拷贝过去、<3>释放原空间。这样的话 vector 成长所带来的代价是相当高的。

deque 的想象结构：就是相同的连续空间拼接而成

而 deque 巧妙的避开了 vector 的缺点，deque 的结构有一段一段的定量空间组成。一旦有必要在 deque 的前端或者尾端增加新空间，便配置一定量的连续空间，串在整个 deque 的头端或者尾端。deque 便是在这些分段的定量连续空间上，维序其连续的假象，并提供随机存取的界面。简单来讲就是 vector、list 的结合体，大小相同的连续空间串在一起。这样就避开了 vector 的【重新配置、拷贝、释放】的轮回。不过呢？有舍就有得，代价是迭代器的框架很复杂。

现在我们已经对 deque 有了一定的了解 ~ 接下来我们看看它的结构

deque 的结构

和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。为了管理这些连续空间，deque 容器用数组 map （注意，不是 STL 的 map）存储着各个连续空间的首地址。也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间。我们称 map 数组为中控区，存储的空间位置为缓冲区。

这个时候我们的老铁可能就会问，要是中控区的空间满了怎么办，我们知道 deque 是一块连续空间拼接而成的，一般情况下空间是足够的，并不会频繁扩容。如果 map 不够用了，我们这边需要找一块更大的空间来做我们的中控器 map，这个时候 map 就会有更多的节点空间来存储我们的缓冲区。

我们再来细致的了解一下中控器、缓冲区、迭代器之间的相互关系：

简单来讲我们的迭代器就是一块 4 个空间的节点，cur 指向缓冲区的数据元素，first 指向缓冲区的首地址，last 指向缓冲区的末地址，而 node 则指向在中控区的节点，那如果我们要访问 deque 内的数据该怎么办呢？

举个栗子 ~ 我想访问 12 位置的元素

首先我们先来分析一下：

这是一个空间大小为 8 的数组 Buff（通常用 Buff 来表示缓冲区的空间）

我们要找到是第几个 Buff 数组存放了 12 位置：i = pos/N（设 pos 是访问位置，N 是 Buff 空间的大小）所以 i = 12/8，即第二个 Buff 数组存放了该访问元素

然后我们要找到该元素在 Buff 空间的第几号位置：j = pos%N，j = 12%8，即该元素在 Buff 空间的第 4 号位置（Buff 空间从 0 开始）

deque 的迭代器剖析

deque 容器底层将序列中的元素分别存储到了不同段的连续空间中，因此要想实现迭代器的功能，必须先解决如下 2 个问题：

迭代器在遍历 deque 容器时，必须能够确认各个连续空间在 map 数组中的位置

迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中

为了控制 deque 的迭代功能，deque 专门设置了以下的结构：

template <class T ,...,size_t BufSiz>
struct __deque_iterator 
{ 
	// ...
    typedef T** map_pointer;
private:
	T* cur; 
	T* first; 
	T* last; 
	map_pointer node;
};

cur	指向迭代器当前在缓冲区遍历的元素
first	指向缓冲区的首节点
last	指向缓冲区的末节点
node	指向中控区的节点

借助这 4 个指针，deque 迭代器对各种运算符进行了重载、封装：

template <class T,..., size_t BufSiz>
struct __deque_iterator
{
    //...
    typedef __deque_iterator self;
    typedef T** map_pointer;
    typedef ptrdiff_t difference_type;
public:

    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));
    }

    static size_t buffer_size()
    {
        return __deque_buf_size(0, sizeof(T)); 
    }

    void set_node(map_pointer new_node)
    {
        //记录新的空间在 map 中的位置
        node = new_node;
        first = *new_node; 
        //更新 last 指针，difference_type(buffer_size())表示每段连续空间的长度
        last = first + difference_type(buffer_size());
    }

    T* operator*() const 
    {
        return *cur;
    }

    T* operator->() const
    {
        return &(operator *()); 
    }

    self& operator++() 
    {
        ++cur;
        if (cur == last) 
        {
            //如果 cur 位于连续空间边缘，则先将迭代器跳跃到下一个连续空间中
            set_node(node + 1);
            cur = first;
        }
        return *this;
    }

    self& operator--()
    {
        if (cur == first) 
        {
            //如果 cur 位于连续空间边缘，则先将迭代器跳跃到前一个连续空间中
            set_node(node - 1);
            cur == last;
        }
        --cur;
        return *this;
    }
    T* operator[](difference_type n) const 
    { 
        return *(*this + n);
    }

    bool operator==(const self& x) const 
    { 
        return cur == x.cur;
    }

    bool operator!=(const self& x) const 
    { 
        return !(*this == x); 
    }

private:
    T* cur;
    T* first;
    T* last;
    map_pointer node;
};

关于我们 typedef 的 ptrdiff_t 具体是什么：不同机器下，他都有对应的类是为了适应不同平台下定义的

我们的迭代器就已经大致完成了 ~

这样就可以借助 start 和 finish，以及 deque 迭代器中重载的诸多运算符，就可以实现 deque 容器提供的大部分成员函数：

template <class T, size_t BufSiz = 0>
class deque 
{
    typedef __deque_iterator<T, ..., BufSiz> iterator;
    typedef pointer* map_pointer;
public: 
    iterator begin()
    { 
        return start; 
    }
    
    iterator end()
    { 
        return finish;
    }

    T* operator[](size_type n) 
    {
        return start[difference_type(n)];
    }

    T* front() 
    {
        return *start;
    }

    T* back() 
    {
        iterator tmp = finish;
        --tmp;
        return *tmp;
    }

    size_t size() const 
    { 
        return finish - start;
    }

    bool empty() const 
    { 
        return finish == start; 
    }
protected:
    iterator start; 
    iterator finish; 
    map_pointer map; 
    size_t map_size;
};

对了以上的代码都是伪代码，不能使用的哦 ~ 只是为了更好了解 deque 的结构

需要源码的老铁可以点击文章顶部的资源管理

接下来我们聊一聊使用：

deque 的使用

在讲使用之前，我们可以先来参考一下文档 deque 文档

deque 的初始化

deque<int> a;        // 定义一个int类型的双端队列a
deque<int> a(10);    // 定义一个int类型的双端队列a，并设置初始大小为10
deque<int> a(10, 1); // 定义一个int类型的双端队列a，并设置初始大小为10且初始值都为1
deque<int> b(a);     // 定义并用双端队列a初始化双端队列b
deque<int> b(a.begin(), a.begin()+3); // 将双端队列a中从第0个到第2个(共3个)作为双端队列b的初始值
deque<int> b=a;      // 定义一个int类型的双端队列b，并将双端队列a赋值给b

我们之前学过 vector、list 所以应该很容易理解以上的意义：

无参构造、链式构造、拷贝构造、迭代器区间构造、赋值构造

这里就不一一讲解了

注意：除此之外，deque 还可以直接使用数组来初始化

	int a[] = { 1,2,3,4,5 };
	deque<int> str(a, a+5);

我们简单来测试一下 ~

void deque_test()
{
	int a[] = { 1,2,3,4,5 };
	deque<int> str(a, a + 5);
	while (!str.empty())
	{
		cout << str.front() << " ";
		str.pop_front();
	}
}

deque 的容量操作

size() 计算容器大小

max_size() 计算容器最大容量（不经常用的接口函数）

resize() 预留容器的空间大小

empey() 判断容器是否为空

deque 的访问操作

<1> 支持下标 [ ] 访问：越界报错

<2> 支持 at 访问：越界抛异常

<3> front：访问第一个元素

<4> back：访问最后一个元素

代码测试：
void deque_test()
{
	deque<int> str = { 1,2,3,4,5 };
	cout << str.front() << endl;
	cout << str.back() << endl;
}

老铁们 ~ 我想开摆了（挑重点讲）：

在 pos 位置插入另一个向量的 [forst，last] 间的数据

注意：插入元素不一定要同一个容器，但是要同一种类型

代码测试：

void deque_test()
{
	deque<int> str = { 1,2,3,4,5 };
	vector<int> arr = { 7,8,9,10,11 };
	str.insert(str.begin()+2, arr.begin(), arr.end());
	while (!str.empty())
	{
		cout << str.front() << " ";
		str.pop_front();
	}
}

删除 [first，last] 之间的元素

代码测试：

void deque_test()
{
	deque<int> str = { 1,2,3,4,5 };
	str.erase(str.begin(), str.begin()+3);
	while (!str.empty())
	{
		cout << str.front() << " ";
		str.pop_front();
	}
}

assign的用法

assign 简单来讲就是初始化，而且不仅支持迭代器区间初始化还支持用 n 个 val 初始化

代码测试

void deque_test()
{
	deque<int> str;
	str.assign(5, 0);
	deque<int> arr;
	arr.assign(str.begin(), str.end());
	while (!arr.empty())
	{
		cout << arr.front() << " ";
		arr.pop_front();
	}
}

deque 的优缺点

我们先来看看 vector、list 的特点：

deque 的优势：

<1> 与 vector 比较：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的

<2> 与 list 比较：其底层是连续空间，空间利用率比较高，不需要存储额外字段

deque的缺点：

deque 不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而排序场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list。deque 的应用并不多，不适合大量的头部和中间插入删除，也不适合大量的随机访问。而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。