410-C++之STL模板库（9-11）

9、STL中的deque的实现

deque则是一种双向开口的连续线性空间。

deque由一段一段的定量连续空间组成，一旦需要增加新的空间，只要配置一段定量连续空间拼接在头部或尾部即可，因此deque的最大任务是如何维护这个整体的连续性

deque的数据结构如下：

class deque
{
    ...
protected:
    typedef pointer* map_pointer;//指向map指针的指针
    map_pointer map;//指向map
    size_type map_size;//map的大小
public:
    ...
    iterator begin();
    itertator end();
    ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

deque内部有一个指针指向map，map是一小块连续空间，其中的每个元素称为一个节点，node，每个node都是一个指针，指向另一段较大的连续空间，称为缓冲区，这里就是deque中实际存放数据的区域，默认大小512bytes。整体结构如上图所示。

deque的迭代器数据结构如下：

deque虽然也提供随机访问的迭代器，但是其迭代器并不是普通的指针，其复杂程度比vector高很多。

struct __deque_iterator
{
    ...
    T* cur;//迭代器所指缓冲区当前的元素
    T* first;//迭代器所指缓冲区第一个元素
    T* last;//迭代器所指缓冲区最后一个元素
    map_pointer node;//指向map中的node
    ...
}
1
2
3
4
5
6
7
8
9

从deque的迭代器数据结构可以看出，为了保持与容器联结，迭代器主要包含上述4个元素。

deque迭代器的“++”、“–”操作是远比vector迭代器繁琐，其主要工作在于：

• 缓冲区边界，如何从当前缓冲区跳到另一个缓冲区；
• 当然deque内部在插入元素时，如果map中node数量全部使用完，且node指向的缓冲区也没有多余的空间，这时会配置新的map（2倍于当前+2的数量）来容纳更多的node，也就是可以指向更多的缓冲区；
• 在deque删除元素时，也提供了元素的析构和空闲缓冲区空间的释放等机制。

---

deque： 双端队列容器。

底层数据结构： 动态开辟的二维数组，一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组，从新的第一维数组的下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加。

第一维空间大小是MAP_SIZE=2，第二维和元素类型有关。

如果T是int类型，则第二维空间大小是4096/4=1024个。

• 双端队列，两个端可以做队头，或者队尾。
• 相当于2个方向都有2个角色。
• first和last处于中间的位置（512）：为了让两头都预留足够的空间，每一头都可以插入的。

随着元素的增加，相应的指针fisrt和last向两端移动！

如果还想从右向左入，这个第二维已经没有空间了！

需要进行另外一个二维的开辟。

随着我们空间又添加满了：

此时deque就需要扩容了，它扩容的是第一维，是按照2倍进行扩容的。

• 然后第二维也要挪过来了。是放在第一维的中间的位置。
• 因为是双端队列，任何一端都有可能进行元素的插入。给上下都预留空间。方便元素的添加！

然后deque又需要扩容。第一维扩容到原来的2倍。第二维挪过来，放在第一维的中间位置。

10、STL中stack实现

stack（栈） 是一种先进后出（First In Last Out）的数据结构，只有一个入口和出口，那就是栈顶，除了获取栈顶元素外，没有其他方法可以获取到内部的其他元素，其结构图如下：

stack这种单向开口的数据结构很容易由双向开口的deque和list形成，只需要根据stack的性质对应移除某些接口即可实现，stack的源码如下：

template <class T, class Sequence = deque<T> >
class stack
{
	...
protected:
    Sequence c;
public:
    bool empty(){return c.empty();}
    size_type size() const{return c.size();}
    reference top() const {return c.back();}
    const_reference top() const{return c.back();}
    void push(const value_type& x){c.push_back(x);}
    void pop(){c.pop_back();}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

从stack的数据结构可以看出，其所有操作都是围绕Sequence完成，而Sequence默认是deque数据结构。

stack这种“修改某种接口，形成另一种风貌”的行为，成为adapter(配接器)。常将其归类为container adapter（容器适配器）而非container。

stack除了默认使用deque作为其底层容器之外，也可以使用双向开口的list，只需要在初始化stack时，将list作为第二个参数即可。

由于stack只能操作顶端的元素，因此其内部元素无法被访问，也不提供迭代器。

11、STL中queue的实现

queue（队列）是一种先进先出（First In First Out）的数据结构，只有一个入口和一个出口，分别位于最底端和最顶端，出口元素外，没有其他方法可以获取到内部的其他元素，其结构图如下：

类似的，queue这种“先进先出”的数据结构很容易由双向开口的deque和list形成，只需要根据queue的性质对应移除某些接口即可实现，queue的源码如下：

template <class T, class Sequence = deque<T> >
class queue
{
	...
protected:
    Sequence c;
public:
    bool empty(){return c.empty();}
    size_type size() const{return c.size();}
    reference front() const {return c.front();}
    const_reference front() const{return c.front();}
    void push(const value_type& x){c.push_back(x);}
    void pop(){c.pop_front();}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

从queue的数据结构可以看出，其所有操作都也都是是围绕Sequence完成，Sequence默认也是deque数据结构。queue也是一类container adapter（容器适配器）。

同样，queue也可以使用list作为底层容器，不具有遍历功能，没有迭代器。