5双向队列（deque）
程序员文章站
2024-02-11 23:24:22
...
1、deque概述
deque是一种双向开口的连续线性空间，而vector是单向开口的连续线性空间，deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入或移除操作，二在于deque没有容量（capacity）观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新空间并链接起来。deque的迭代器也是Random Access Iterator，但不是普通指针，其复杂度和vector不可以道里计。
2、deque迭代器
deque是由一段一段的定量连续空间构成，一旦有必要在deque的前端或者尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque最大的任务便是将这些分段的定量连续空间维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置空间、复制、释放旧空间”的轮回，代价便是复杂的迭代器架构。
deque采用一块map（不是STL的map容器）作为主控，这里的map是一小块连续空间，其中每个元素就是一个节点node也是一个指针，指向另一段较大的连续线性空间称为缓冲区，才是deque实际存储空间主体，map其实是一个T**，也就是说它是一个指针，所指之物又是一个指针，指向型别是T的一块空间。
deque是分段连续空间，维持其整体连续假象的任务，落在了迭代器的operator++和operator--两个运算子身上。deque的迭代器主要有四个成员变量，node为此迭代器指向的管控中心也就是位于map的地址，cur为此迭代器所指缓冲区中的当前元素地址，first为此迭代器所指缓冲区的头地址，last为此迭代器所指缓冲区的尾地址，其中last所指空间不用，这样缓冲区空间就满足左闭右开的法则[first,last)。
deque维护着两个首尾迭代器start和finish，分别指向第一个缓冲区的第一个元素和最后一个缓冲区的最后一个元素的下一个位置，start的node指向map的第一个空间first指向node所指缓冲区的第一个位置last指向node所指缓冲区的最后一个位置其cur指向node所指缓冲区的第一个元素，这样就使得start的cur所指元素是整个deque的第一个元素；finish的node指向map的最后一个空间first指向node所指缓冲区的第一个位置last指向node所指缓冲区的最后一个位置其cur指向node所指缓冲区的最后一个元素的后一个位置，这样就使得finish的cur所指元素是整个deque的最后一个元素后一个位置，这样start和finish的cur就形成了整个deque的区间[start.cur,finish.cur)。
deque数据结构的核心思想是：通过用node大范围表示，具体小范围用cur表示相当于偏移量，deque迭代器只要有node和cur就可以精准定位到deque每一个元素位置。
deque之所以能将分段连续空间看起来像是一个整体就是因为operator+=设计的好：将当前迭代器node所指cur前移n个位置，offset是迭代器中cur最终指向的位置相对于当前迭代器的first的位置距离，node_offset是迭代器node最终位置相对于当前位置node的距离，通过计算得到offset和node_offset，那么迭代器最终位置node=node+node_offset,cur=first + (offset - node_offset * difference_type(buffer_size()))
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
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;
}template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_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)); }
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
template <class T, class Ref, class Ptr>
struct __deque_iterator {
typedef __deque_iterator<T, T&, T*> iterator;
typedef __deque_iterator<T, const T&, const T*> const_iterator;
static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }
#endif
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer;
typedef __deque_iterator self;
T* cur;
T* first;
T* last;
map_pointer node;
__deque_iterator(T* x, map_pointer y)
: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
__deque_iterator() : cur(0), first(0), last(0), node(0) {}
__deque_iterator(const iterator& x)
: cur(x.cur), first(x.first), last(x.last), node(x.node) {}
reference operator*() const { return *cur; }
pointer operator->() const { 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 tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
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) const {
self tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n) { return *this += -n; }
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n;
}
reference operator[](difference_type n) const { return *(*this + n); }
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
};3、deque数据结构
deque维护着两个首尾迭代器start和finish，分别指向第一个缓冲区的第一个元素和最后一个缓冲区的最后一个元素的下一个位置，start的node指向map的第一个空间first指向node所指缓冲区的第一个位置last指向node所指缓冲区的最后一个位置其cur指向node所指缓冲区的第一个元素，这样就使得start的cur所指元素是整个deque的第一个元素；finish的node指向map的最后一个空间first指向node所指缓冲区的第一个位置last指向node所指缓冲区的最后一个位置其cur指向node所指缓冲区的最后一个元素的后一个位置，这样就使得finish的cur所指元素是整个deque的最后一个元素后一个位置，这样start和finish的cur就形成了整个deque的区间[start.cur,finish.cur)。
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: // Basic types
typedef T 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;
public: // Iterators
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T&, BufSiz> const_iterator;
typedef __deque_iterator<T, T&, T*> iterator;
typedef __deque_iterator<T, const T&, const T*> const_iterator;
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
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;
protected: // Internal typedefs
typedef pointer* map_pointer;
typedef simple_alloc<value_type, Alloc> data_allocator;
typedef simple_alloc<pointer, Alloc> map_allocator;
static size_type buffer_size() {
return __deque_buf_size(BufSiz, sizeof(value_type));
}
static size_type initial_map_size() { return 8; }
protected: // Data members
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
public: // Basic accessors
iterator begin() { return start; }
iterator end() { return finish; }
const_iterator begin() const { return start; }
const_iterator end() const { return finish; }
reverse_iterator rbegin() { return reverse_iterator(finish); }
reverse_iterator rend() { return reverse_iterator(start); }
const_reverse_iterator rbegin() const {
return const_reverse_iterator(finish);
}
const_reverse_iterator rend() const {
return const_reverse_iterator(start);
}
reference operator[](size_type n) { return start[difference_type(n)]; }
const_reference operator[](size_type n) const {
return start[difference_type(n)];
}
reference front() { return *start; }
reference back() {
iterator tmp = finish;
--tmp;
return *tmp;
}
const_reference front() const { return *start; }
const_reference back() const {
const_iterator tmp = finish;
--tmp;
return *tmp;
}
size_type size() const { return finish - start;; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }
}4、deque构造与内存管理
初始的map分配的空间大小为map_size = max(initial_map_size(), num_nodes + 2)，也就是最小为8，最大为所需节点数num_nodes加2。缓冲区大小如果指定就为n否则就是512/sizeof(T)，比如int的缓冲区大小就是128。并且在分配空间的时候，尽量让节点处于map的中间，因为deque的两头都有可能插入数据，最终还要初始化start和finish迭代器，设置它们的node、first、last、cur。
当向deque的两端push元素时，首先检查当前两端的缓冲区是否还余有空间，如果有直接构造对象元素不需要配置空间，否则则需要对两端外节点node所指空间重新配置缓冲区大小，另外一个问题什么时候map需要重新整治？当两端外节点node数小于2时就需要整治，这个时候需要判断是否是map还有足够空间（map_size>2*num_nodes），因为数据分布不均导致数据过于倾向一头，如果是这样只要将数据重新移动至map*即可，而不需要重新配置map空间；否则map需要扩充空间，也就是重换一个map，配置更大的空间、拷贝原来的数据至新map*、释放原来的空间，新配置的map空间大小至少是原来的2倍加2大小。
当向deque的两端pop元素时，首先检查当前两端的缓冲区是否还余有元素，如果有直接析构对象元素不需要释放缓冲区空间，否则则需要对两端外节点node所指空间析构对象元素同时释放缓冲区空间大小。
void push_back(const value_type& t) {
if (finish.cur != finish.last - 1) {
construct(finish.cur, t);
++finish.cur;
}
else
push_back_aux(t);
}
void push_front(const value_type& t) {
if (start.cur != start.first) {
construct(start.cur - 1, t);
--start.cur;
}
else
push_front_aux(t);
}
void pop_back() {
if (finish.cur != finish.first) {
--finish.cur;
destroy(finish.cur);
}
else
pop_back_aux();
}
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>::push_back_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_back();
*(finish.node + 1) = allocate_node();
__STL_TRY {
construct(finish.cur, t_copy);
finish.set_node(finish.node + 1);
finish.cur = finish.first;
}
__STL_UNWIND(deallocate_node(*(finish.node + 1)));
}
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_front();
*(start.node - 1) = allocate_node();
__STL_TRY {
start.set_node(start.node - 1);
start.cur = start.last - 1;
construct(start.cur, t_copy);
}
catch(...) {
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
}
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.cur = finish.last - 1;
destroy(finish.cur);
}
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.cur = start.first;
}
void reserve_map_at_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_at_front ? nodes_to_add : 0);
if (new_nstart < start.node)
copy(start.node, finish.node + 1, new_nstart);
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_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
copy(start.node, finish.node + 1, new_nstart);
map_allocator::deallocate(map, map_size);
map = new_map;
map_size = new_map_size;
}
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
}5、deque元素操作
（1）pop_back
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.cur = finish.last - 1;
destroy(finish.cur);
}（2）pop_front
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.cur = start.first;
}（3）clear
clear用来清除整个deque，deque的最初状态保有一个缓冲区，所以clear完成之后回复初始状态，也一样要保留一个缓冲区，此时start和finish指向同一个缓冲区，但这个缓冲区中所有元素都析构掉。
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;
}（4）erase
iterator erase(iterator 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 == start && last == finish) {
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;
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;
destroy(new_finish, finish);
for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
finish = new_finish;
}
return start + elems_before;
}
}（5）insert
iterator insert(iterator position, const value_type& x) {
if (position.cur == start.cur) {
push_front(x);
return start;
}
else if (position.cur == finish.cur) {
push_back(x);
iterator tmp = finish;
--tmp;
return tmp;
}
else {
return insert_aux(position, x);
}
}
template <class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator
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;
}
上一篇： STL（七）deque双端队列容器