《STL源码剖析》笔记：deque

概述

vector是单向开口的连续空间，deque则是双向开口的连续空间，可以在头尾两端分别做元素的插入和删除。

deque与vector最大的差异在于：

• deque允许在常数时间内对起头端进行元素的插入或者移除。
• deque没有容量的概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。亦既是在vector中那样"因为旧空间不足而重新分配空间，然后复制元素，再释放旧空间"这样的事情在deque中不会发生，因此没有必要保留reserve等容量相关。

deque由2部分组成：

• 缓冲区：一段连续的内存空间。
• map：指向缓冲区的指针数组。

deque.png

template <typename T>
class Deque {
    ......
    private:
        T **_map;                      // 动态数组
        iterator _begin;
        iterator _end;
        size_t _mapSize = 1;          // map的数量
        size_t _pageSize = 3;         // 缓冲区的大小
}

迭代器

deque是分段的连续空间，维持其"整体连续"假象的任务，就落在了迭代器身上。为此迭代器必须能够做到：

• 能够指向缓冲区的元素
• 能够判断自己是否已处于缓冲区的边缘。当自己处于缓冲区的边缘时，能够跳跃至上一个缓冲区或者下一个缓冲区，需要知道自己在map中哪个位置。
  所以，在其中应该要保留一个指向容器（其中有map）的指针，一个所处map为重的索引， 指向元素的指针。

class DequeIterator {
    private:
        Deque<T> *_containerPtr;      // 保存对容器的连接，重点是能访问到map。
        T *_cur;                      // 指向缓冲区的元素
        size_t _mapIndex;             // map数组的索引，向前跳跃或者向后跳跃
};

迭代器.png

DequeIterator &operator++();

_cur = isPageTail() ? _containerPtr->_map[++_mapIndex] : ++_cur;    // 判断是否是缓冲区末尾
return *this;

DequeIterator &operator--()

_cur = isPageHead() ? _containerPtr->_map[--_mapIndex] + (getPageSize()-1) : --_cur;  // 判断是否是缓冲区头部
return *this;

添加元素

void push_back(const T &value)

• 如果没有空间容纳新元素
  • 申请新的map
  • 拷贝原deque的缓冲区中的元素
  • 构造元素

if (isLastPageTail())    // 是否是Deque缓冲区的最后一个位置
    reallocateMapForTail();    
dataAlloc::construct(_end._cur, value);
++_end;

void push_front(const T& value)

if (isFirstPageHead())
    reallocateMapForHead();
--_begin;
dataAlloc::construct(_begin._cur, value);

删除元素

void Deque<T>::pop_back()

if (empty())
    throw std::out_of_range("pop_back() on empty Deque");
--_end;
dataAlloc::destroy(_end._cur);

void pop_front()

if (empty())
    throw std::out_of_range("pop_front() on empty Deque");
dataAlloc::destroy(_begin._cur);
++_begin;