双端队列(double-ended queue)
deque是一种双向开口的连续线性空间,允许在队列的两端进行操作(插入和删除)。
deque和vector的区别:
deque与vector非常相似。它也采用动态数组管理元素,提供随机存取,有着和vector几乎一样的接口。不同的是deque的动态数组头尾都开放,因此能在头尾两端进行快速安插和删除。
1)deque是动态地以分段连续空间组合而成,随时可以增加一端新的空间并链接起来。迭代器需要在不同区块间跳转,(迭代器属于random access iterator(随机存取迭代器)),所以它非一般指针,这会影响运算层面。而vector必须使用一块连续内存,所以不像vector那样“因旧空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间”。deque的max_size()可能更大。
2)元素的存取和迭代器的动作比vector稍慢。因此,尽可能选择使用vector而非deque。这里,对deque进行排序操作,如果为了提高效率,可将deque先完整复制到一个vector,然后对vector排序,再复制回vector。
3)不支持对容量和内存重新分配时机的控制。不过deque的内存重分配优于vector,因为其内部结构显示,deque不必在内存重分配时复制所有元素。
deque的中控器
在底层,deque按“页”(page)或“块”(chunk)来分配存储器,每页包含固定数目的元素,(定量连续空间)一旦有必要在deque的前端或尾端增加新空间,便配置一段定量连续空间,串接在整个deque的头端或尾端。deque的最大任务就是在这些分段的定量连续空间上,维护其整体连续的假像,并提供随机存取的接口。
例如,一个10M字节的vector使用的是一整块10M字节的内存,而deque可以使用一串更小的内存块,比如10块1M的内存。所以不能将deque的地址(如&deque[0])传递给传统的C API,因为deque内部所使用的内存不一定会连续。
中央控制
deque采用一块所谓的map(区别于STL的map容器)作为主控。这里的map是一小段连续空间,其中每个元素都是指针(node),指向另一端(较大的)连续线性空间,即缓冲区。默认值为0表示将使用512bytes的缓冲区。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
//stl_deque.h inline size_t __deque_buf_size(size_t __size) { return __size < 512 ? size_t(512 / __size) : size_t(1); } template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class deque : protected _Deque_base<_Tp, _Alloc> { __STL_CLASS_REQUIRES(_Tp, _Assignable); typedef _Deque_base<_Tp, _Alloc> _Base; public: // Basic types typedef _Tp value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef typename _Base::allocator_type allocator_type; allocator_type get_allocator() const { return _Base::get_allocator(); } //偏特化 public: // Iterators typedef typename _Base::iterator iterator; typedef typename _Base::const_iterator const_iterator; #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION typedef reverse_iterator<const_iterator> const_reverse_iterator; typedef reverse_iterator<iterator> reverse_iterator; #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ typedef reverse_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator; typedef reverse_iterator<iterator, value_type, reference, difference_type> reverse_iterator; #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ protected: // Internal typedefs //元素的指针的指针 typedef pointer* _Map_pointer; static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); } protected: #ifdef __STL_USE_NAMESPACES ... #endif /* __STL_USE_NAMESPACES */ public: // Basic accessors iterator begin() { return _M_start; } iterator end() { return _M_finish; } const_iterator begin() const { return _M_start; } const_iterator end() const { return _M_finish; } reverse_iterator rbegin() { return reverse_iterator(_M_finish); } reverse_iterator rend() { return reverse_iterator(_M_start); } const_reverse_iterator rbegin() const { return const_reverse_iterator(_M_finish); } const_reverse_iterator rend() const { return const_reverse_iterator(_M_start); } reference operator[](size_type __n) { return _M_start[difference_type(__n)]; } const_reference operator[](size_type __n) const { return _M_start[difference_type(__n)]; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//concept_checks.h #define __STL_TYPEDEF_REQUIREMENT(__REQUIREMENT) \ template \ struct __##__REQUIREMENT##__typedef_requirement_violation { \ typedef typename Type::__REQUIREMENT __REQUIREMENT; \ } __STL_TYPEDEF_REQUIREMENT(value_type); __STL_TYPEDEF_REQUIREMENT(difference_type); __STL_TYPEDEF_REQUIREMENT(size_type); __STL_TYPEDEF_REQUIREMENT(reference); __STL_TYPEDEF_REQUIREMENT(const_reference); __STL_TYPEDEF_REQUIREMENT(pointer); __STL_TYPEDEF_REQUIREMENT(const_pointer); |