概述
vector是单向开口的连续线性空间，而deque则是一种双向开口的连续线性空间。所谓双向开口，是指可以在头尾两端分别做元素的插入和删除操作。
区别
和
vector相比：
deque运行常数时间内对起头端进行元素的插入和移除操作deque没有所谓的容量的概念，因为他是动态得以分段连续空间组合而成，随时可以增加一段新的空间并链接起来
换言之：
像vector那样“因旧空间不足而重新配置一块更大得空间，然后复制元素，再释放旧空间”这样的事情在deque是不会发生的。
中控器
deque是由一段一段的定量连续空间构成。一旦有必要在
deque的前段和尾端增加新空间，便配置一段定量连续空间，串联在整个deque的头端和尾端。
deque的最大任务，就是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。
deque采用一块所谓的map（不是STL的map）作为主控。这里所指的map是一小块连续空间，其中每个元素（结点）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是
deque的存储空间主体。
SGI STL允许我们指定缓冲区的大小，默认值0表示将使用512bytes缓冲区
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
template<class T,class Alloc = alloc,size_t BufSiz = 0> class deque { public: typedef T value_type; typedef value_type* pointer; //... protected: typedef pointer* map_pointer; protected: map_pointer map;//指向map,map里的元素都是指针 size_type map_size; }; |
迭代器
对于
deque的迭代器，它必须能够指出分段连续空间在哪里，其次它也必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃到下一个或上一个缓冲区。为了能够正常跳跃，deque必须随时掌握管控中心map
|
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 |
template<class T,class Ref,class Ptr,size_t BufSiz> struct __deque_iterator { //未基础std::iterator typedef __deque_iterator<T,T&,T*,BufSiz> iterator; typedef __deque_iterator<T,const T&,const T*,BufSiz> const_iterator; static size_t buffer_size() { return __deque_buf_size(BufSiz,sizeof(T)); } //未继承std::iterator，所以必须撰写5个必要的迭代器相应型别 typedef random_access_iterator_tag iterator_category;//1 typedef T value_type;//2 typedef Ptr pointer;//3 typedef Ptr reference;//4 typedef size_t size_type; typedef ptrdeff_t difference_type;//5 typedef T** map_pointer; typedef __deque_iterator self; //保持与容器的连结 T* cur;//此迭代器指向缓冲区的现行元素 T* first;//此迭代器指向缓冲区的头 T* last;//此迭代器指向缓冲区的尾 map_pointer node;//指向管控中心 //... }; |
|
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
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)); } //跳缓冲区 void set_node(map_pointer new_node) { node = new_node; first = *new_node; last = first + difference_type(buffer_size()); } reference operator*() {return *cur;} reference operator->() {return &(operator*());} difference_type operator-(const self& x) const { return difference_type(buffer_size())*(node - x.node - 1) + (cur-first) + (x.last - x.cur); } self& operator++() { ++cur;//切换到下一个元素 if(cur == last)//如果已到达缓冲区的尾端 { set_node(node+1);//就切换到下一个结点的第一个元素 cur = first; } return *this; } self operator++(int) { self temp = *this; ++*this; return temp; } self& operator--() { if(cur == first)//如果已经到缓冲区的头端 { set_node(node-1);//就切换到前一个结点的最后一个元素（的下一个）位置 cur = last; } --cur;//切换到前一个元素 return *this; } self operator--(int) { self temp = *this; --*this; return temp; } self& operator+=(difference_type n) { difference_type offset = n + (cur - last); if(offset > 0 && offset < difference_type(buffer_size())) { //目标位置在同一缓冲区内 cur += n; } else { //目标的位置不在同一缓冲区内 difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()) : -difference_type(-offset - 1) / buffer_size()) - 1; //切换到正确的结点 set_node(node+node_offset); //切换到正确的元素 cur = first + (offset - node_offset*difference_type(buffer_size())); } return *this; } self operator+(difference_type n) { self temp = *this; return temp += n; } self operator-=(difference_type n) { return *this += -n; } self operator-(difference_type n) const { self temp = *this; return temp -= n; } self operator[] (difference_type n) const { return *(*this + n); } bool operator== (const self& x) {return cur == x.cur;} bool operator!= (const self& x) {return !(*this == x);} bool operator< (const self& x) const { return (node == x.node)?(cur<x.cur):(node<x.node); } |
数据结构
|
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 |
template<class T,class Alloc = alloc,size_t BufSiz = 0> class deque { public: typedef T value_type; typedef value_type* pointer; typedef size_t size_type; public: typedef __deque_iterator<T,T&,T*,BufSiz> iterator; protected: //元素的指针的指针 typedef pointer* map_pointer; protected: iterator start;//表现第一个结点 iterator finish;//表现最后一个结点 map_pointer map;//指向map，map是块连续的空间，每个元素都是指针，指向一个结点 size_type map_size;//map内有多少指针 //... public: iterator begin() {return start;} iterator end() {return finish;} reference operator[] (size_type n) { return start[difference_type(n)]; } reference front() {return *start;} reference back() { iterator temp = finish; --temp; return *temp; } size_type size() const {return finish - start;} size_type max_size() const {return size_type(-1);} bool empty() const {return finish == start;} } |
构造与内存管理
|
1 2 3 4 5 6 7 8 |
{ //... protected: //专属空间配置器，么此配置一个元素大小 typedef simple_alloc<value_type,Alloc> data_allocator; //专属空间配置器，每次配置一个指针大小 typedef simple_alloc<pointer,Alloc> map_allocator; } |
|
1 2 3 4 5 |
//构造 deque(int n,const value_type& value):start(),finish(),map(0),map_size(0) { fill_initialize(n,value); } |
|
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
template<class T,class Alloc,size_t BufSize> void deque<T,Alloc,BufSize>::fill_initialize(size_type n, const value_type& value) { create_map_and_nodes(n);//把deque的结构都产生并安排好 map_pointer cur; __STL_TRY { //为每个结点的缓冲区设定初值 for(cur = start.node;cur<finish.node;++cur) uninitialized_fill(*cur,*cur+buffer_size(),value); uninitialized_fill(finish.first,finish.cur,value); } catch(...) { //... } } template<calss T,class Alloc,size_t BufSize> void deque<T,Alloc,BufSize>::create_map_and_nodes(size_type num_elements) { //需要结点数=（元素个数/每个缓冲区可容纳的元素个数）+1 //如果刚好整除，会多分配一个结点 size_type num_nodes = num_elements/buffer_size() + 1; //一个map要管理几个结点，最少8个，最多是所需节点数+2 map_size = max(initial_map_size(),num_nodes + 2); map = map_allocator::allocate(map_size); //令nstart和nfinish指向map所拥有的全部结点的最中央区段 map_pointer nstart = map + (map_size - num_nodes)/2; map_pointer nfinish = nstart + num_nodes - 1; map_pointer cur; __STL_TRY { //为map内的每个现用结点配置缓冲区，所有缓冲区加起来就是deque的可用空间 for(cur = nstart; cur <= nfinish; ++cur) *cur = allocate_node(); } catch(...) { //若非全部成功，就一个不留 //... } start.set_node(nstart); finish.set_node(nfinish); start.cur = start.finish; finish.cur = finish.first + num_elements % buffer_size(); } void push_back(const value_type& t) { if(finish.cur != finish.last - 1) { construct(finish.cur,t); ++finish.cur; } else push_back_aux(t); } template <class T,class Alloc,size_t BufSize> void deque<T,Alloc,BufSize>::push_back_aux(const value_type& t) { value_type t_copy = t; reserve_map_at_front();//符合某种条件则重新换一个map *(start.node-1) = allocate_node();//配置一个新结点 __STL_TRY { start.set_node(start.node-1);//改变start，让其指向新结点 start.cur = start.last - 1;//设定start的状态 constrcut(start.cur,t_copy);//针对标的元素设值 } catch(...) { //...若非全部成功，就一个不留 start.set_node(start.node + 1); start.cur = start.first; deallocate_node(*(start.node - 1)); throw; } } void reserve_map_back(size_type nodes_to_add = 1) { if(nodes_to_add + 1 > map_size - (finish.node - map)) reallocate_map(nodes_to_add,false); } void reserve_map_at_front(size_type nodes_to_add = 1) { if(nodes_to_add > start.node - map) reallocate_map(nodes_to_add,true); } template<class T,class Alloc,size_t BufSize> void deque<T,Alloc,BufSize>::reallocate_map(size_type nodes_to_add, bool add_at_front) { size_type old_num_nodes = finish.node - start.node + 1; size_type new_num_nodes = old_num_nodes + nodes_to_add; map_pointer new_nstart; if(map_size > 2*new_num_nodes) { new_nstart = map+(map_size-new_num_nodes)/2 + (add_to_front ? nodes_to_add : 0); if(new_nstart < start.node) copy(start.node,finish.node+1,new_start); else copy_backward(start.node,finish.node+1,new_nstart+old_num_nodes); } else { size_type new_map_size = map_size + max(map_size,nodes_to_add) + 2; //配置一块空间，准备给新map使用 map_pointer new_map = map_allocator::allocate(new_map_size); new_nstart = new_map + (new_map_size - new_map_nodes)/2 + (add_at_front ? nodes_to_add : 0); //把原map内容拷贝过来 copy(start.node,finish.node+1,new_nstart); //释放原来map map_allocator::deallocate(map,map_size); //设定新map的起始地址与大小 map = new_map; map_size = new_map_size; } } |
操作
pop_back
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
void pop_back() { if(finish.cur != finish.first)//最后缓冲区有一个或更多的元素 { --finish.cur;//调整指针，相当于排除了最后元素 destroy(finish.cur);//将最后元素析构 } else pop_back_aux();//这里将进行缓冲区的释放工作 } template<class T,class Alloc,size_t BufSize> void deque<T,Alloc,BufSize>::pop_back_aux() { deallocate_node(finish.first);//释放最后一个缓冲区 finish.set_node(finish.node - 1);//调整finish的状态，是指向上一个缓冲区 finish.cur = finish.last - 1;//的最后一个元素 destroy(finish.cur);//将该元素析构 } |
pop_front
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
void pop_front() { if(start.cur != start.last - 1) { //第一缓冲区有两个或更多的元素 destroy(start.cur); ++start.cur; } else pop_front_aux();//这里进行缓冲区的释放工作 } template <class T,class Alloc,size_t BufSize> void deque<T,Alloc,BufSize>::pop_front_aux() { destroy(start.cur);//将第一缓冲区的第一个（也是最后一个）元素析构 deallocate_node(start.first);//释放第一缓冲区 start.set_node(start.node + 1);//调整start的状态，使其指向下一个缓冲区的第一个元素 start.cur = start.first; } |
clear
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
template <class T,class Alloc,size_t BufSize> void deque<T,Alloc,BufSize>::clear() { //先针对头尾以外的每一个缓冲区（都是饱满的） for(map_pointer node = start.node+1;node < finish.node; ++node) { //将缓冲区内的所有元素析构 destroy(*node,*node+buffer_size()); //释放缓冲区内存 data_allocator::deallocate(*node,buffer_size()); } if(start.node != finish.node) { destroy(start.cur,start.last);//将头缓冲区的目前所有元素析构 destroy(finish.first,finish.cur);//将尾缓冲区的目前所有元素析构 //释放尾缓冲区，保留头缓冲区 data_allocator::deallocate(finish.first,buffer_size()); } else//只有一个缓冲区 destroy(start.cur,finish.cur);//将此唯一缓冲区所有元素析构 finish = start;//调整状态 } |
erase
|
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 |
iterator erase(inerator pos) { iterator next = pos; ++next; difference_type index = pos - start;//清除点之前的元素个数 if(index < size() >> 1)//如果清除点之前元素比较少 { copy_backward(start,pos,next);//移动清除点之前的元素 pop_front();//移动完毕，最前一个元素冗余，去掉 } else//清除点之后的元素比较少 { copy(next,finish,pos);//移动清除点之后的元素 pop_back();//移动完毕，最后一个元素冗余，去掉 } return start + index; } template<class T,class Alloc,size_t BufSize> deque<T,Alloc,BufSize>::iterator deque<T,Alloc,BufSize>::erase( iterator first,iterator last) { if(first == last && last == first) { clear();//如果要清除的区间就是整个deque，调用clear就行 return finish; } else { difference_type n = last - first;//清除区间的长度 difference_type elems_before = first - start;//清除区间前方的元素个数 if(elems_before < (size() - n)/2) { //如果前方的元素比较少，向后移动前方元素 copy_backward(start,first,last); iterator new_start = start + n;//标记deque的新起点 destroy(start,new_start); //将冗余的缓冲区释放 for(map_pointer cur = start.node; cur < new_start.node; ++cur) data_allocator::deallocate(*cur,buffer_size()); start = new_start; } else { copy(last,finish,first);//向前移动后方元素 iterator new_finish = finish - n;//标记deque的新尾点 destroy(new_finish,finish);//移动完毕，将冗余的元素析构 //将冗余的缓冲区释放 for(map_pointer cur = new_finish.node; cur <= finish.node； ++cur) data_allocator::deallocate(*cur,buffer_size()); finish = new_finish;//设定deque的新尾点 } return start + elems_before; } } |
insert
|
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 |
iterator insert(iterator position,const value_type& x) { if(position.cur == start.cur)//插入最前端，push_front去做 { push_front(x); return start; } else if(position.cur == finish.cur)//插入最尾端，push_back去做 { push_back(x); iterator temp = finish; --temp; return temp; } else return insert_aux(position,x); } template <class T,class Alloc,size_t BufSize> deque<T,Alloc,BufSize>::insert_aux(iterator pos, const value_type& x) { difference_type index = pos - start;//插入点之前的元素个数 value_type x_copy = x; if(index < size()/2)//如果插入点之前的元素个数比较少 {//在最前端加入与第一元素同值的元素 push_front(front()); iterator front1 = start;//标识记号，然后元素移动 ++front1; iterator front2 = front1; ++front2; pos = start+index; iterator pos1 = pos; ++pos1; copy(front2,pos1,front1);//元素移动 } else { push_back(back());//插入点之后的元素个数比较少，在最尾端加入与最后元素同值得元素 iterator back1 = finish;//标识记号，然后元素移动 --back1; iterator back2 = back1; --back2; pos = start + index; copy_backward(pos,back2,back1);//元素移动 } *pos = x_copy;//在插入点设定新值 return pos; } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 51CTO：Linux C++网络编程五08/20
- ♥ 51CTO：C++语言高级课程一08/07
- ♥ STL_内存处理工具05/02
- ♥ Boost 程序库完全开发指南：工具与字符串08/22
- ♥ Effective C++_第四篇07/02
- ♥ C++17_第二篇12/22