您的位置: 首页  >  文章  >  STL 模板库 第六日 ： deque

STL 模板库 第六日 ： deque

分类: 文章 • 2025-01-06 22:11:34
STL 模板库 deque
一：什么是deque
所谓的deque是”double ended queue”的缩写，双端队列不论在尾部或头部插入元素，都十分迅速。而在中间插入元素则会比较费时，因为必须移动中间其他的元素。双端队列是一种随机访问的数据类型，提供了在序列两端快速插入和删除操作的功能，它可以在需要的时候改变自身大小，完成了标准的C++数据结构中队列的所有功能。
Vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。deque对象在队列的两端放置元素和删除元素是高效的，而向量vector只是在插入序列的末尾时操作才是高效的。deque和vector的最大差异，一在于deque允许于常数时间内对头端进行元素的插入或移除操作，二在于deque没有所谓的capacity观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque中是不会发生的。也因此，deque没有必要提供所谓的空间预留（reserved）功能。
虽然deque也提供Random Access Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可同日而语，这当然涉及到各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL的sort算法），再复制回deque。
deque是一种优化了的对序列两端元素进行添加和删除操作的基本序列容器。通常由一些独立的区块组成，第一区块朝某方向扩展，最后一个区块朝另一方向扩展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块，而是多个连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。

二：deque的常用方法
（1）申明一个deque
#include<deque>  // 头文件
deque<type> deq;  // 声明一个元素类型为type的双端队列que
deque<type> deq(size);  // 声明一个类型为type、含有size个默认值初始化元素的的双端队列que
deque<type> deq(size, value);  // 声明一个元素类型为type、含有size个value元素的双端队列que
deque<type> deq(mydeque);  // deq是mydeque的一个副本
deque<type> deq(first, last);  // 使用迭代器first、last范围内的元素初始化deq
（2）deque的常用成员函数
    deque<int> deq;
    deq[ ]：用来访问双向队列中单个的元素。
    deq.front()：返回第一个元素的引用。
    deq.back()：返回最后一个元素的引用。
    deq.push_front(x)：把元素x插入到双向队列的头部。
    deq.pop_front()：弹出双向队列的第一个元素。
    deq.push_back(x)：把元素x插入到双向队列的尾部。
    deq.pop_back()：弹出双向队列的最后一个元素。
三：deque的注意点
    支持随机访问，即支持[ ]以及at()，但是性能没有vector好。
    可以在内部进行插入和删除操作，但性能不及list。
    deque两端都能够快速插入和删除元素，而vector只能在尾端进行。
    deque的元素存取和迭代器操作会稍微慢一些，因为deque的内部结构会多一个间接过程。
    deque迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。
    deque可以包含更多的元素，其max_size可能更大，因为不止使用一块内存。
    deque不支持对容量和内存分配时机的控制。
    在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector，因为其内部结构显示不需要复制所有元素。
    deque的内存区块不再被使用时，会被释放，deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实际操作版本定义。
    deque不提供容量操作：capacity()和reverse()，但是vector可以。
四：源码解析
（转 自：http://blog.****.net/chengonghao/article/details/51464598）

Deque采用一块map作为主控，这里所谓map是一小块连续空间，其中每个元素（此处称为节点，node）都是指针，指向另一段连续线性空间，称之为缓冲区。

STL 模板库 第六日 ： deque

deque的实现需要以下几个文件：

1.      globalConstruct.h，构造和析构函数文件，位于cghSTL/allocator/cghAllocator/

2.      cghAlloc.h，空间配置器文件，位于cghSTL/allocator/cghAllocator/

3.      cghDequeIterator.h，迭代器的实现，位于cghSTL/sequence containers/cghDeque/

4.      cghDeque.h，cghDeque的实现，位于cghSTL/sequence containers/cghDeque/

5.      test_cghDeque.cpp，测试代码，位于cghSTL/test/

 

1.构造函数

先看第一个，globalConstruct.h构造函数文件

[cpp] view plain copy
  1. /******************************************************************* 
  2. *  Copyright(c) 2016 Chen Gonghao 
  3. *  All rights reserved. 
  4. * 
  5. *  [email protected] 
  6. * 
  7. *  功能:全局构造和析构的实现代码 
  8. ******************************************************************/  
  9.   
  10.   
  11.   
  12. #include "stdafx.h"  
  13. #include <new.h>  
  14. #include <type_traits>  
  15.   
  16. #ifndef _CGH_GLOBAL_CONSTRUCT_  
  17. #define _CGH_GLOBAL_CONSTRUCT_  
  18.   
  19. namespace CGH  
  20. {  
  21.     #pragma region 统一的构造析构函数  
  22.     template<class T1, class  T2>  
  23.     inline void construct(T1* p, const T2& value)  
  24.     {  
  25.         new (p)T1(value);  
  26.     }  
  27.   
  28.     template<class T>  
  29.     inline void destroy(T* pointer)  
  30.     {  
  31.         pointer->~T();  
  32.     }  
  33.   
  34.     template<class ForwardIterator>  
  35.     inline void destroy(ForwardIterator first, ForwardIterator last)  
  36.     {  
  37.         // 本来在这里要使用特性萃取机（traits编程技巧）判断元素是否为non-trivial  
  38.         // non-trivial的元素可以直接释放内存  
  39.         // trivial的元素要做调用析构函数，然后释放内存  
  40.         for (; first < last; ++first)  
  41.             destroy(&*first);  
  42.     }  
  43.     #pragma endregion   
  44. }  
  45.   
  46. #endif  


按照STL的接口规范，正确的顺序是先分配内存然后构造元素。构造函数的实现采用placement new的方式；为了简化起见，我直接调用析构函数来销毁元素，而在考虑效率的情况下一般会先判断元素是否为non-trivial类型。

关于 trivial 和 non-trivial 的含义，参见：stack overflow


2.空间配置器

cghAlloc.h是空间配置器文件，空间配置器负责内存的申请和回收。

[cpp] view plain copy
  1. /******************************************************************* 
  2. *  Copyright(c) 2016 Chen Gonghao 
  3. *  All rights reserved. 
  4. * 
  5. *  [email protected] 
  6. * 
  7. *  功能:cghAllocator空间配置器的实现代码 
  8. ******************************************************************/  
  9.   
  10. #ifndef _CGH_ALLOC_  
  11. #define _CGH_ALLOC_  
  12.   
  13. #include <new>  
  14. #include <cstddef>  
  15. #include <cstdlib>  
  16. #include <climits>  
  17. #include <iostream>  
  18.   
  19.   
  20. namespace CGH  
  21. {  
  22.     #pragma region 内存分配和释放函数、元素的构造和析构函数  
  23.     // 内存分配  
  24.     template<class T>  
  25.     inline T* _allocate(ptrdiff_t size, T*)  
  26.     {  
  27.         set_new_handler(0);  
  28.         T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));  
  29.         if (tmp == 0)  
  30.         {  
  31.             std::cerr << "out of memory" << std::endl;  
  32.             exit(1);  
  33.         }  
  34.         return tmp;  
  35.     }  
  36.   
  37.     // 内存释放  
  38.     template<class T>  
  39.     inline void _deallocate(T* buffer)  
  40.     {  
  41.         ::operator delete(buffer);  
  42.     }  
  43.   
  44.     // 元素构造  
  45.     template<class T1, class  T2>  
  46.     inline void _construct(T1* p, const T2& value)  
  47.     {  
  48.         new(p)T1(value);  
  49.     }  
  50.   
  51.     // 元素析构  
  52.     template<class T>  
  53.     inline void _destroy(T* ptr)  
  54.     {  
  55.         ptr->~T();  
  56.     }  
  57.     #pragma endregion  
  58.   
  59.     #pragma region cghAllocator空间配置器的实现  
  60.     template<class T>  
  61.     class cghAllocator  
  62.     {  
  63.     public:  
  64.         typedef T           value_type;  
  65.         typedef T*          pointer;  
  66.         typedef const T*    const_pointer;  
  67.         typedef T&          reference;  
  68.         typedef const T&    const_reference;  
  69.         typedef size_t      size_type;  
  70.         typedef ptrdiff_t   difference_type;  
  71.   
  72.         template<class U>  
  73.         struct rebind  
  74.         {  
  75.             typedef cghAllocator<U> other;  
  76.         };  
  77.   
  78.         static pointer allocate(size_type n, const void* hint = 0)  
  79.         {  
  80.             return _allocate((difference_type)n, (pointer)0);  
  81.         }  
  82.   
  83.         static void deallocate(pointer p, size_type n)  
  84.         {  
  85.             _deallocate(p);  
  86.         }  
  87.   
  88.         static void deallocate(void* p)  
  89.         {  
  90.             _deallocate(p);  
  91.         }  
  92.   
  93.         void construct(pointer p, const T& value)  
  94.         {  
  95.             _construct(p, value);  
  96.         }  
  97.   
  98.         void destroy(pointer p)  
  99.         {  
  100.             _destroy(p);  
  101.         }  
  102.   
  103.         pointer address(reference x)  
  104.         {  
  105.             return (pointer)&x;  
  106.         }  
  107.   
  108.         const_pointer const_address(const_reference x)  
  109.         {  
  110.             return (const_pointer)&x;  
  111.         }  
  112.   
  113.         size_type max_size() const  
  114.         {  
  115.             return size_type(UINT_MAX / sizeof(T));  
  116.         }  
  117.     };  
  118.     #pragma endregion  
  119.   
  120.     #pragma region 封装STL标准的空间配置器接口  
  121.     template<class T, class Alloc = cghAllocator<T>>  
  122.     class simple_alloc  
  123.     {  
  124.     public:  
  125.         static T* allocate(size_t n)  
  126.         {  
  127.             return 0 == n ? 0 : (T*)Alloc::allocate(n*sizeof(T));  
  128.         }  
  129.   
  130.         static T* allocate(void)  
  131.         {  
  132.             return (T*)Alloc::allocate(sizeof(T));  
  133.         }  
  134.   
  135.         static void deallocate(T* p, size_t n)  
  136.         {  
  137.             if (0 != n)Alloc::deallocate(p, n*sizeof(T));  
  138.         }  
  139.   
  140.         static void deallocate(void* p)  
  141.         {  
  142.             Alloc::deallocate(p);  
  143.         }  
  144.     };  
  145.     #pragma endregion  
  146. }  
  147.   
  148. #endif  


classcghAllocator是空间配置器类的定义，主要的四个函数的意义如下：allocate函数分配内存，deallocate函数释放内存，construct构造元素，destroy析构元素。这四个函数最终都是通过调用_allocate、_deallocate、_construct、_destroy这四个内联函数实现功能。

我们自己写的空间配置器必须封装一层STL的标准接口，

[cpp] view plain copy
  1. template<classT, class Alloc = cghAllocator<T>>  
  2. class simple_alloc  


         构造与析构函数、空间配置器是最最基本，最最底层的部件，把底层搭建好之后我们就可以着手设计deque了。


3.deque的迭代器

         我们首先设计deque的迭代器，我把迭代器的内部结构分解为一下几个部分

1.      一堆typedef、成员变量的声明。最重要的成员变量是node，它是衔接管控中心和迭代器的枢纽；

2.      迭代器管控中心和cghDeque管控中心的衔接，只有一个函数：set_node，初始化迭代器的成员变量，更重要的是与deque的管控中心连接；

3.      确定每个缓冲区的大小：只有一个函数buffer_size()；

4.      迭代器基本操作：deque的迭代器要保证random access；

STL 模板库 第六日 ： deque

迭代器代码的注释已经写得十分详细了，有疑问的地方我都给出了说明，童鞋们可以参考迭代器的内部结构来总体把握迭代器的框架，通过注释来理解迭代器的工作原理。

cghDequeIterator.h（迭代器）代码如下：

[cpp] view plain copy
  1. /******************************************************************* 
  2. *  Copyright(c) 2016 Chen Gonghao 
  3. *  All rights reserved. 
  4. * 
  5. *  [email protected] 
  6. * 
  7. *  功能:cghDeque的迭代器的实现代码 
  8. ******************************************************************/  
  9.   
  10. #ifndef _CGH_DEQUE_ITERATOR_  
  11. #define _CGH_DEQUE_ITERATOR_  
  12.   
  13. #include <memory>  
  14. namespace CGH{  
  15.   
  16.     template<class T, class Ref, class Ptr, size_t BufSiz>  
  17.     struct __deque_iterator{  
  18.   
  19.         #pragma region typedef和成员变量的定义  
  20.   
  21.         typedef T           value_type;  
  22.         typedef Ptr         pointer;  
  23.         typedef Ref         reference;  
  24.         typedef size_t      size_type;  
  25.         typedef ptrdiff_t   difference_type; // ptrdiff_t的使用要#include <memory>  
  26.         typedef T**         map_pointer; // 迭代器所属缓冲区，该缓冲区由cghDeque的管控中心管理  
  27.         typedef __deque_iterator self;  
  28.         typedef __deque_iterator<T, T&, T*, BufSiz>       iterator;  
  29.   
  30.         T* cur; // 当前位置  
  31.         T* first; // 缓冲区头部  
  32.         T* last; // 缓冲区尾部  
  33.         map_pointer node; // 迭代器所属缓冲区，该缓冲区由cghDeque的管控中心管理  
  34.   
  35.         #pragma endregion  
  36.   
  37.         #pragma region 迭代器管控中心和cghDeque管控中心的衔接  
  38.   
  39.         /* 
  40.             输入参数：new_node，cghDeque传过来的缓冲区位置（管控中心的某个节点） 
  41.         */  
  42.         void set_node(map_pointer new_node)  
  43.         {  
  44.             node = new_node; // 连接cghDeque管控中心的某个节点和迭代器缓冲区  
  45.             first = *new_node; // 缓冲区头部  
  46.             last = first + difference_type(buffer_size()); // 缓冲区尾部  
  47.         }  
  48.   
  49.         #pragma endregion  
  50.   
  51.         #pragma region 确定每个缓冲区的大小  
  52.   
  53.         /* 
  54.             缓冲区默认大小为512字节 
  55.             1.如果BufSiz不为0，传回BufSiz，表示buffer_size由用户自定义 
  56.             2.如果BufSiz，表示buffer_size使用默认值，那么如果元素大小（sizeof(T)）小于512字节，传回size_t(512 / sizeof(T) 
  57.               如果元素大小（sizeof(T)）大于512字节，传回1 
  58.         */  
  59.   
  60.         size_t buffer_size()  
  61.         {  
  62.             return BufSiz != 0 ? BufSiz : (sizeof(T) < 512 ? size_t(512 / sizeof(T)) : size_t(1));  
  63.         }  
  64.         #pragma endregion  
  65.           
  66.         #pragma region 迭代器基本操作  
  67.   
  68.             #pragma region 解除引用  
  69.   
  70.         reference operator*() const{ return *cur; }  
  71.         pointer operator->()const{ return &(operator*()); }  
  72.   
  73.         #pragma endregion  
  74.   
  75.             #pragma region 迭代器的单步移动  
  76.   
  77.         self& operator++()  
  78.         {  
  79.             ++cur; // 切换至下一个元素  
  80.             // 如果到所在缓冲区的尾端，注意缓冲区是前闭后开的空间，last是缓冲区结束的哨兵，到达last就该切换缓冲区了  
  81.             if (cur == last)   
  82.             {  
  83.                 set_node(node + 1); // 就切换至管控中心的下一个节点（也即缓冲区）  
  84.                 cur = first; // 下一个缓冲区的第一个元素  
  85.             }  
  86.             return *this;  
  87.         }  
  88.   
  89.         self& operator++(int)  
  90.         {  
  91.             self tmp = *this;  
  92.             ++*this;  
  93.             return tmp;  
  94.         }  
  95.   
  96.         self& operator--()  
  97.         {  
  98.             if (cur == first) // 如果到达所在缓冲区的头部  
  99.             {  
  100.                 set_node(node - 1); // 就切换至管控中心的前一个节点（也即缓冲区）  
  101.                 cur = last; // 下一个缓冲区的最后一个元素  
  102.             }  
  103.             // 注意缓冲区是前闭后开的空间，last是缓冲区结束的哨兵，本身没有意义，last的前一个元素才有正确的值域  
  104.             --cur;  
  105.             return *this;  
  106.         }  
  107.   
  108.         self& operator--(int)  
  109.         {  
  110.             self tmp = *this;  
  111.             --*this;  
  112.             return tmp;  
  113.         }  
  114.   
  115.         #pragma endregion  
  116.   
  117.             #pragma region 迭代器的随机移动  
  118.   
  119.         /* 
  120.             实现随机存取（random access） 
  121.         */  
  122.         self& operator+=(difference_type n)  
  123.         {  
  124.             difference_type offset = n + (cur - first); // 偏移  
  125.             // 1.offset >= 0：向后偏移  
  126.             // 2.offset < difference_type(buffer_size())：偏移小于缓冲区长度  
  127.             if (offset >= 0 && offset < difference_type(buffer_size()))  
  128.             {  
  129.                 cur += n;  
  130.             }  
  131.             else  
  132.             {  
  133.                 difference_type node_offset = offset > 0  
  134.                     ? offset / difference_type(buffer_size()) // 向后偏移：确定管控中心的偏移的节点（偏移多少个缓冲区）  
  135.                     : -difference_type((-offset - 1) / buffer_size()) - 1; // 向前偏移：确定管控中心的偏移的节点（偏移多少个缓冲区）  
  136.                 set_node(node + node_offset); // 从管控中心中选择新的节点，切换缓冲区  
  137.                 cur = first + (offset - node_offset*difference_type(buffer_size()));  
  138.             }  
  139.             return *this;  
  140.         }  
  141.   
  142.         /* 
  143.             实现随机存取（random access） 
  144.         */  
  145.         self operator+(difference_type n) const  
  146.         {  
  147.             self tmp = *this;  
  148.             return tmp += n;  
  149.         }  
  150.   
  151.         self& operator-=(difference_type n)const{ return *this += -n; }  
  152.   
  153.         self operator-(difference_type n)const  
  154.         {  
  155.             self tmp = *this;  
  156.             return tnp -= n;  
  157.         }  
  158.   
  159.         difference_type operator-(const self& x)  
  160.         {  
  161.             return difference_type(buffer_size())*(node - x.node - 1) + (cur - first) + (x.last - x.cur);  
  162.         }  
  163.   
  164.         reference operator[](difference_type n)const{ return *(*this + n); }  
  165.   
  166.         #pragma endregion  
  167.   
  168.             #pragma region 迭代器的相互比较  
  169.   
  170.         bool operator==(const self& x)const{ return cur == x.cur; }  
  171.   
  172.         bool operator!=(const self& x)const{ return cur != x.cur; }  
  173.   
  174.         bool operator<(const self& x)const  
  175.         {  
  176.             return (node == x.node) ? (cur < x.cur) : (node < x.node);  
  177.         }  
  178.   
  179.         #pragma endregion  
  180.   
  181.         #pragma endregion  
  182.     };  
  183. }  
  184.   
  185. #endif  

4.deque

重头戏来啦：deque的实现。

Deque的内部结构我用region分为了以下几类：

1.      一堆typedef、成员变量的定义，最重要的成员变量是map（管控中心），是deque实现头尾插删，动态扩容的灵魂；

2.      辅助函数：buffer_size()，确定每个缓冲区的大小；

3.      初始化：deque的构造函数，以及构造函数引出的一大堆东西~~

4.      查询操作：返回deque的大小、头部、尾部等等；

5.      添加和删除：前插、后插、清空

 STL 模板库 第六日 ： deque

deque代码的注释已经写得十分详细了，有疑问的地方我都给出了说明，童鞋们可以参考deque的内部结构来总体把握deque的框架，通过注释来理解deque的工作原理。

cghDeque.h：

[cpp] view plain copy
  1. /******************************************************************* 
  2. *  Copyright(c) 2016 Chen Gonghao 
  3. *  All rights reserved. 
  4. * 
  5. *  [email protected] 
  6. * 
  7. *  功能:cghDeque的实现代码 
  8. ******************************************************************/  
  9.   
  10. #ifndef _CGH_DEQUE_  
  11. #define _CGH_DEQUE_  
  12.   
  13. #include "cghAlloc.h"  
  14. #include "globalConstruct.h"  
  15. #include "cghDequeIterator.h"  
  16. #include <algorithm>  
  17.   
  18. namespace CGH{  
  19.     template<class T, class Alloc = cghAllocator<T>, size_t BufSiz = 0>  
  20.     class cghDeque{  
  21.   
  22.         #pragma region typedef和成员变量的定义  
  23.     public:  
  24.         typedef T               value_type;  
  25.         typedef value_type*     pointer;  
  26.         typedef value_type&     reference;  
  27.         typedef size_t          size_type;  
  28.         typedef ptrdiff_t   difference_type;  
  29.         typedef typename __deque_iterator<T, T&, T*, BufSiz>::iterator iterator; // 迭代器，#include "cghDequeIterator.h"  
  30.   
  31.     protected:  
  32.         typedef pointer* map_pointer;  
  33.     protected:  
  34.         iterator start;  
  35.         iterator finish;  
  36.         map_pointer map; // 管控中心  
  37.         size_type map_size;  
  38.   
  39.         #pragma endregion  
  40.   
  41.         #pragma region 辅助函数  
  42.   
  43.     protected:  
  44.         /* 
  45.             管控中心（map）每个节点指向的缓冲区大小 
  46.             缓冲区默认大小为512字节 
  47.             1.如果BufSiz不为0，传回BufSiz，表示buffer_size由用户自定义 
  48.             2.如果BufSiz，表示buffer_size使用默认值，那么如果元素大小（sizeof(T)）小于512字节，传回size_t(512 / sizeof(T) 
  49.             如果元素大小（sizeof(T)）大于512字节，传回1 
  50.         */  
  51.         size_t buffer_size()  
  52.         {  
  53.             return BufSiz != 0 ? BufSiz : (sizeof(T) < 512 ? size_t(512 / sizeof(T)) : size_t(1));  
  54.         }  
  55.   
  56.         #pragma endregion  
  57.                   
  58.         #pragma region cghDeque的初始化  
  59.   
  60.     protected:  
  61.         typedef simple_alloc<value_type, Alloc>       data_allocator; // cghDeque节点的空间配置器  
  62.         typedef simple_alloc<pointer, Alloc>      map_allocator; // cghDeque管控中心（map）的空间配置器  
  63.     public:  
  64.         /* 
  65.             构造函数 
  66.         */  
  67.         cghDeque(int n, const value_type& value) :start(), finish(), map(0), map_size(0)  
  68.         {  
  69.             fill_initialize(n, value);  
  70.         }  
  71.         /* 
  72.             默认构造函数 
  73.         */  
  74.         cghDeque() :start(), finish(), map(0), map_size(0) { fill_initialize(0, 0); }  
  75.     protected:  
  76.   
  77.         /* 
  78.         各种初始化 
  79.         */  
  80.         void fill_initialize(size_type n, const value_type& value)  
  81.         {  
  82.             create_map_and_nodes(n);  
  83.             map_pointer cur;  
  84.             for (cur = start.node; cur < finish.node; ++cur)  
  85.             {  
  86.                 std::uninitialized_fill(*cur, *cur + buffer_size(), value);  
  87.             }  
  88.             std::uninitialized_fill(finish.first, finish.cur, value);  
  89.         }  
  90.   
  91.         /* 
  92.         初始化管控中心（map）、管控中心每个节点管理的缓冲区大小 
  93.         */  
  94.         void create_map_and_nodes(size_type num_elements)  
  95.         {  
  96.             // 需要初始化的节点数 = （元素个数 / 每个缓冲区可容纳的元素个数） +　１  
  97.             size_type num_nodes = num_elements / buffer_size() + 1;  
  98.             // 一个管控中心（map）要管理几个节点，最少8个，最多是“所需节点数 + 2”  
  99.             map_size = std::max(initial_map_size(), num_nodes + 2); // std::max 需要 #include <algorithm>  
  100.             // 配置出一个具有“map_size个节点”的管控中心（map）  
  101.             map = map_allocator::allocate(map_size);  
  102.             // 令nstart和nfinish指向管控中心（map）所有节点的中间  
  103.             // 保持在中间，可使头尾两端扩充能量一样大  
  104.             map_pointer nstart = map + (map_size - num_nodes) / 2;  
  105.             map_pointer nfinish = nstart + num_nodes - 1;  
  106.   
  107.             // 为管控中心（map）的每个现用节点配置缓冲区，所有缓冲区加起来就是cghDeque的可用空间  
  108.             map_pointer cur;  
  109.             for (cur = nstart; cur <= nfinish; ++cur)  
  110.             {  
  111.                 *cur = allocate_node(); // 配置缓冲区  
  112.             }  
  113.             start.set_node(nstart); // 衔接start迭代器  
  114.             finish.set_node(nfinish); // 衔接finish迭代器  
  115.             start.cur = start.first; // 确定start迭代器的游标  
  116.             finish.cur = finish.first + num_elements % buffer_size(); // 确定finish迭代器的游标  
  117.         }  
  118.   
  119.         /* 
  120.         管控中心（map）最小节点数 
  121.         */  
  122.         size_type initial_map_size(){ return (size_type)8; }  
  123.   
  124.         /* 
  125.         配置管控中心（map）每个节点的缓冲区大小 
  126.         */  
  127.         pointer allocate_node()  
  128.         {  
  129.             return data_allocator::allocate(buffer_size() / sizeof(T));  
  130.         }  
  131.   
  132.         /* 
  133.         释放管控中心（map）节点的缓冲区 
  134.         */  
  135.         void deallocate_node(void* node)  
  136.         {  
  137.             data_allocator::deallocate(node);  
  138.         }  
  139.   
  140.         #pragma endregion  
  141.   
  142.         #pragma region cghDeque的查询操作  
  143.   
  144.     public:  
  145.         iterator begin(){ return start; } // 获得cghDeque的头部  
  146.   
  147.         iterator end(){ return finish; } // 获得cghDeque的尾部  
  148.   
  149.         reference operator[](size_type n){ return start[difference_type(n)]; } // 获得cghDeque第n个元素  
  150.   
  151.         reference front(){ return *start; } // 获得cghDeque的头部的值  
  152.   
  153.         /* 
  154.             因为缓冲区是前闭后开的区间，获得cghDeque的尾部时需要finish回退一个步长 
  155.         */  
  156.         reference back()  
  157.         {  
  158.             iterator tmp = finish;  
  159.             --tmp;  
  160.             return *tmp;  
  161.         }  
  162.   
  163.         /* 
  164.             获得cghDeque的长度 
  165.         */  
  166.         size_type size()  
  167.         {  
  168.             return finish - start;  
  169.         }  
  170.   
  171.         size_type max_size() const{ return finish - start; } // 获得cghDeque的最大程长度  
  172.   
  173.         bool empty()const{ return finish == start; } // cghDeque是否为空  
  174.   
  175.         #pragma endregion  
  176.   
  177.         #pragma region cghDeque元素的添加和删除操作  
  178.   
  179.     public:  
  180.   
  181.         /* 
  182.             在cghDeque尾部插入元素 
  183.         */  
  184.         void push_back(const value_type& t)  
  185.         {  
  186.             // 缓冲区是前闭后开的区间，finish迭代器的last元素做哨兵  
  187.             // 如果到达finish.last，说明缓冲区尾部已满，调用push_back_aux，来到管控中心（map）的下一个节点，也就是下一个缓冲区  
  188.             if (finish.cur != finish.last - 1)  
  189.             {  
  190.                 construct(finish.cur, t);  
  191.                 ++finish.cur;  
  192.             }  
  193.             else  
  194.             {  
  195.                 push_back_aux(t);  
  196.             }  
  197.         }  
  198.           
  199.         /* 
  200.             在cghDeque头部插入元素 
  201.         */  
  202.         void push_front(const value_type& t)  
  203.         {  
  204.             // 如果没有到达缓冲区头部，说明缓冲区前半部分有剩余，直接插入  
  205.             // 如果到达start.first，说明缓冲区头部已满，调用push_front_aux，来到管控中心（map）的上一个节点，也就是上一个缓冲区  
  206.             if (start.cur != start.first)  
  207.             {  
  208.                 construct(start.cur - 1, t);  
  209.                 --start.cur;  
  210.             }  
  211.             else  
  212.             {  
  213.                 push_front_aux(t);  
  214.             }  
  215.         }  
  216.   
  217.         /* 
  218.             从cghDeque尾部弹出元素 
  219.         */  
  220.         void pop_back()  
  221.         {  
  222.             // 如果没有到达finish迭代器的头部，直接destroy  
  223.             if (finish.cur != finish.first)  
  224.             {  
  225.                 --finish.cur;  
  226.                 destroy(finish.cur);  
  227.             }  
  228.             else  
  229.             {  
  230.                 pop_back_aux(); // 如果到达finish的头部，说明我们要销毁的元素跨了缓冲区，我们要到上一个缓冲区去删除元素  
  231.             }  
  232.         }  
  233.   
  234.         /* 
  235.             从cghDeque头部弹出元素 
  236.         */  
  237.         void pop_front()  
  238.         {  
  239.             // 如果没有到达start迭代器的尾，直接destroy  
  240.             if (start.cur != start.last - 1)  
  241.             {  
  242.                 destroy(start.cur);  
  243.                 ++start.cur;  
  244.             }  
  245.             else  
  246.             {  
  247.                 pop_front_aux(); // 如果到达start的尾，说明我们要销毁的元素跨了缓冲区，我们要到下一个缓冲区去删除元素  
  248.             }  
  249.         }  
  250.   
  251.         /* 
  252.             清除cghDeque的所有元素 
  253.         */  
  254.         void clear()  
  255.         {  
  256.             // [start.node + 1, finish.node)是满员的，所以先清除[start.node + 1, finish.node)这段缓冲区的元素  
  257.             for (map_pointer node = start.node + 1; node < finish.node; ++node)  
  258.             {  
  259.                 destroy(*node, *node + buffer_size());  
  260.                 data_allocator::deallocate(*node, buffer_size());  
  261.             }  
  262.             // 如果start.node != finish.node，说明start迭代器和finish迭代器跨了管控中心的节点，要分别清除  
  263.             if (start.node != finish.node)  
  264.             {  
  265.                 destroy(start.cur, start.last);  
  266.                 destroy(finish.first, finish.last);  
  267.                 data_allocator::deallocate(finish.first, buffer_size());  
  268.             }  
  269.             else // 如果start.node == finish.node，说明start迭代器和finish迭代器在管控中心同一个节点中  
  270.             {  
  271.                 destroy(start.cur, finish.cur);  
  272.             }  
  273.             finish = start; // 不要忘了！  
  274.         }  
  275.     protected:  
  276.   
  277.         /* 
  278.             缓冲区溢出时的后插 
  279.         */  
  280.         void push_back_aux(const value_type& t)  
  281.         {  
  282.             value_type t_copy = t;  
  283.             *(finish.node + 1) = allocate_node(); // 给管控中心（map）的下一个节点（也就是下一个缓冲区）分配内存  
  284.             construct(finish.cur, t_copy); // 构造元素  
  285.             finish.set_node(finish.node + 1); // 重置finish迭代器，指向下一个缓冲区  
  286.             finish.cur = finish.first; // 重置finish迭代器的游标  
  287.         }  
  288.   
  289.         /* 
  290.             缓冲区溢出时的前插 
  291.         */  
  292.         void push_front_aux(const value_type& t)  
  293.         {  
  294.             value_type t_copy = t;  
  295.             *(start.node - 1) = allocate_node(); // 给管控中心（map）的上一个节点（也就是上一个缓冲区）分配内存  
  296.             start.set_node(start.node - 1); // 重置start迭代器，指向上一个缓冲区  
  297.             start.cur = start.last - 1; // 重置start迭代器的游标  
  298.             construct(start.cur, t_copy); // 构造元素  
  299.         }  
  300.   
  301.         /* 
  302.             缓冲区溢出时的后删 
  303.         */  
  304.         void pop_back_aux()  
  305.         {  
  306.             deallocate_node(finish.first); // 释放内存  
  307.             finish.set_node(finish.node - 1); // 上一个缓冲区  
  308.             finish.cur = finish.last - 1; // 重置元素，注意缓冲区是前闭后开  
  309.             destroy(finish.cur); // 析构上一个缓冲区的最后一个元素  
  310.         }  
  311.   
  312.         /* 
  313.             缓冲区溢出时的前删 
  314.         */  
  315.         void pop_front_aux()  
  316.         {  
  317.             destroy(start.cur); // 析构元素  
  318.             deallocate_node(start.first); // 释放内存  
  319.             start.set_node(start.node + 1); // 下一个缓冲区  
  320.             start.cur = start.first; // 重置游标  
  321.         }  
  322.   
  323.         #pragma endregion  
  324.     };  
  325. }  
  326. #endif  



 5.测试

最后是测试环节，测试的主要内容已在注释中说明

test_cghDeque.cpp：

[cpp] view plain copy
  1. /******************************************************************* 
  2. *  Copyright(c) 2016 Chen Gonghao 
  3. *  All rights reserved. 
  4. * 
  5. *  [email protected] 
  6. * 
  7. *  文件名称:cghDeque容器的测试代码 
  8. ******************************************************************/  
  9.   
  10. #include "stdafx.h"  
  11. #include "cghVector.h"  
  12. #include "cghDeque.h"  
  13. using namespace::std;  
  14.   
  15. int _tmain(int argc, _TCHAR* argv[])  
  16. {  
  17.     using namespace::CGH;  
  18.   
  19.   
  20.   
  21.     /***************************************************************************************/  
  22.     /***************************************************************************************/  
  23.     std::cout << "************************初始化、前插、后插测试************************" << endl;  
  24.     std::cout << endl;  
  25.     cghDeque<int> test(1, 1); // 初始化  
  26.     test.push_back(2); // 后插  
  27.     test.push_back(3); // 后插  
  28.     test.push_back(4); // 后插  
  29.     test.push_front(0); // 前插  
  30.     test.push_front(-1); // 前插  
  31.   
  32.     std::cout << "当前元素：";  
  33.     for (cghDeque<int>::iterator iter = test.begin(); iter != test.end(); ++iter){  
  34.         std::cout << *iter << ",";  
  35.     }  
  36.     std::cout << endl;  
  37.     std::cout << endl;  
  38.     std::cout << "长度：" << test.size() << endl;  
  39.     std::cout << endl;  
  40.   
  41.   
  42.   
  43.   
  44.     /***************************************************************************************/  
  45.     /***************************************************************************************/  
  46.     std::cout << "************************前删、后删测试************************" << endl;  
  47.     std::cout << endl;  
  48.     test.pop_front(); // 前删  
  49.     test.pop_back(); // 后删  
  50.     std::cout << "当前元素：";  
  51.     for (cghDeque<int>::iterator iter = test.begin(); iter != test.end(); ++iter){  
  52.         std::cout << *iter << ",";  
  53.     }  
  54.     std::cout << endl;  
  55.     std::cout << endl;  
  56.     std::cout << "长度：" << test.size() << endl;  
  57.     std::cout << endl;  
  58.   
  59.   
  60.   
  61.   
  62.     /***************************************************************************************/  
  63.     /***************************************************************************************/  
  64.     std::cout << "************************清空测试************************" << endl;  
  65.     std::cout << endl;  
  66.     test.clear(); // 前删  
  67.     std::cout << "当前元素：";  
  68.     for (cghDeque<int>::iterator iter = test.begin(); iter != test.end(); ++iter){  
  69.         std::cout << *iter << ",";  
  70.     }  
  71.     std::cout << endl;  
  72.     std::cout << endl;  
  73.     std::cout << "长度：" << test.size() << endl;  
  74.     std::cout << endl;  
  75.   
  76.   
  77.   
  78.   
  79.     /***************************************************************************************/  
  80.     /***************************************************************************************/  
  81.     std::cout << "************************跨主控节点后插测试************************" << endl;  
  82.     std::cout << endl;  
  83.     std::cout << "缓冲区默认大小为512字节，一个int占4字节，512 / 4 = 128" << endl << endl;  
  84.     std::cout << "当插入的元素量 > 128 时就会跨主控节点" << endl;  
  85.     std::cout << endl;  
  86.     test.clear(); // 前删  
  87.     for (int i = 0; i < 150; i++){  
  88.         test.push_back(i);  
  89.     }  
  90.     std::cout << "当前元素：";  
  91.     for (cghDeque<int>::iterator iter = test.begin(); iter != test.end(); ++iter){  
  92.         std::cout << *iter << ",";  
  93.     }  
  94.     std::cout << endl;  
  95.     std::cout << endl;  
  96.     std::cout << "长度：" << test.size() << endl;  
  97.     std::cout << endl;  
  98.   
  99.   
  100.   
  101.   
  102.     /***************************************************************************************/  
  103.     /***************************************************************************************/  
  104.     std::cout << "************************跨主控节点前插测试************************" << endl;  
  105.     std::cout << endl;  
  106.     std::cout << "缓冲区默认大小为512字节，一个int占4字节，512 / 4 = 128" << endl << endl;  
  107.     std::cout << "当插入的元素量 > 128 时就会跨主控节点" << endl;  
  108.     std::cout << endl;  
  109.     test.clear(); // 前删  
  110.     for (int i = 0; i < 150; i++){  
  111.         test.push_front(i);  
  112.     }  
  113.     std::cout << "当前元素：";  
  114.     for (cghDeque<int>::iterator iter = test.begin(); iter != test.end(); ++iter){  
  115.         std::cout << *iter << ",";  
  116.     }  
  117.     std::cout << endl;  
  118.     std::cout << endl;  
  119.     std::cout << "长度：" << test.size() << endl;  
  120.     std::cout << endl;  
  121.   
  122.     std::cout << "************************测试结束************************" << endl;  
  123.     std::cout << endl;  
  124.     system("pause");  
  125.     return 0;  
  126. }  


测试结果图：

STL 模板库 第六日 ： deque



6.扩展讨论

在STL简单stack的实现（传送门：点击打开链接）中，我们为什么选择deque作为stack的底层结构，而不是vector？

我们从以下三个方面来分析：

1.      vector和deque的空间使用效率；

2.      vector和deque的迭代器访问元素效率；

3.      stack的应用场景；

STL 模板库 第六日 ： deque

通过上表对比，我们可以得出如下结论：

1.             vector是真正意义上的连续空间，而deque底层不连续，只是用户看来连续罢了，vector容量溢出时要做三步：1.分配新空间；2.数据移动；释还旧空间。Vector在空间使用上的效率远低于deque；

2.             vector底层使用连续空间，故可以采用普通指针作为迭代器，访问元素的效率高；deque在底层不连续，迭代器设计较复杂，在随机访问元素时效率低。


Stack应用场景包括：函数调用时传递参数、保存现场，局部变量分配和使用。


注意，我们只能访问栈顶元素，迭代器一次只移动一个步长，没有随机访问元素的情况，这意味着采用普通指针和deque专属迭代器来获得栈顶元素的效率相差不大。

得出结论一：vector和deque的迭代器在访问stack元素时打个平手。


但是，程序运行过程中stack会不断的变大缩小，对空间的伸缩性要求很高。deque可以自由组合分段空间，而vector显得有些死板，空间不够就搬家。

得出结论二：deque在空间上使用更灵活，更符合stack的应用场景。


综合结论一、二，我们可以得出最终结论：deque更适合作为stack的底层结构。

相关推荐