deque是一种双向开口的连续线性空间。可以在头尾两端分别做元素的插入和删除操作。deque允许于常数时间内对头端进行元素的插入或移除操作。vector从技术上也可以在头尾两端进行操作，但是由于内存的布局，在头部操作效率极差。
deque在逻辑上看来是整块连续空间，实际上是由一段一段的定量连续空间构成的。所以deque需要设计复杂的数据结构和迭代器来模拟整体连续的假象。
中控器
deque采用一小块连续空间(称作map，不是STL的map)，其中每个元素都是指针，每个指针指向一段连续线性空间，称为缓冲区。怎样扩容呢？当map使用率满载，可以找一块更大的空间作为map，把之前map中的指针移到新map中，并且在新map中的空白元素放入新申请连续线性空间的地址。
template<class T, class Alloc = alloc, size_t BufSiz = 0> //BUfSiz = 0,表示将使用512bytes缓冲区
class deque{
public:
typedef T value_type;
typedef value_type* pointer;
protected:
typedef pointer* map_pointer;
map_pointer map;
size_type map_szie; //map中可以存储的元素大小
};
迭代器
deque的迭代器承担了很大的作用，通过重载++和–来遍历获得deque的元素，其中必然会遇到跨连续空间的情况。
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));
}
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)); } //
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; //指向map的某个元素(该元素指向一段连续空间)
void set_node(map_pointer new_node){ //初始化node
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
reference operator*() const { return *cur; }
pointer operator->() const { return &(operator*()); }
difference_type operator-(const self& x) const { //返回两个迭代器cur的距离
return difference_type(buffer_size() * (node - x.node - 1) + (cur - first) + (x.last - x.cur)) ;
}
self& operator++(){
++cur;
if(cur == last){ //[first, last)依然是前闭后开
set_mode(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;
}
//实现随机存取，迭代器可以直接跳跃n个距离
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()));
}
}
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n) const { return tmp += -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);
}
};
中控器，迭代器和缓冲区的关系
deque中的头迭代器和尾迭代器
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;
typedef __deque_iterator<T, T&, T*, BufSiz> iterator; //定义迭代器型别
protected:
typedef pointer* map_pointer; //定义中控器型别
map_pointer map; //定义中控器
size_type map_size; //map内的元素个数
iterator start; //定义头迭代器
iterator finish; //定义尾迭代器
typedef simple_alloc<value_type, Alloc> data_allocator; //配置map中每个元素指针对应的连续空间中的元素
typedef simple_alloc<pointer, Alloc> map_allocator; //配置map
void create_map_and_nodes(size_type num_elements){
size_type num_nodes = num_elements / buffer_size() + 1;
map_size = max(initial_map_size(), num_nodes + 2); //map管理的节点数，最少8个，最多是所需节点数加2
map = map_allocator::allocate(map_size);
//把头迭代器和尾迭代器的指向位于map的最中央区段，可使头尾两端的扩充能量一样大
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;
__STL_TRY{
for(cur nstart; cur <= nfinish; ++cur){
*cur = allocate_node();
}
}
catch(...){
}
start.set_node(nstart);
finish.set_node(nfinish);
start.cur = start.first;
finish.cur = finish.first + num_element % buffer_size(); //cur要多加一个，前闭后开
}
void fill_initialize(size_type n, const value_type &value){
create_map_and_nodes(n);
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(...) {
}
}
public:
deque(int n, const value_type &value):start(), finish(), map(0), map_size(0) {
fill_initialize(n, value); //初始化deque
}
iterator begin() { return start; }
iterator end() { return finish; }
reference front() { return *(start); }
reference back() {
iterator tmp = finish;
--tmp; //前闭后开，所以要减一
return *tmp;
}
reference operator[](size_type n){
return start[difference_type(n)];
}
void 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) { //map的size大于二倍已使用的空间，那么可以根据需要将头迭代器前移或后移
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 = map + (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);
}
void reserve_map_at_back(size_type nodes_to_add = 1){
if(node_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(node_to_add > start.node - map){ //如果头迭代器前剩下的元素小于要添加的元素，那么就重新分配
reallocate_map(nodes_to_add, true);
}
}
void 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));
}
void 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; //deque的start初始状态是cur=last,在第一个push_front操作时，就会进入该函数，申请一个新的连续内存空间，cur的值也就发生改变，且前闭后开。cur是与第一个元素对应的
construct(start.cur, t_copy);
}catch(...){
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
}
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 push_back(const value_type& t){
if(finish.cur != finish.last - 1){
construct(finish.cur, t);
++finish.cur; //前闭后开
}else{ //只剩下一个元素空间
push_back_aux(t);
}
}
void pop_back_aux(){
deallocate_node(finish.first);
finish.set_node(finish.node - 1);
finish.cur = finish.last - 1; //依然满足前闭后开的原则，与push_back最后一个元素的规则有关
destory(finish.cur);
}
void pop_back(){
if(finish.cur != finish.first){
--finish.cur;
destory(finish.cur);
}else{
pop_back_aux();
}
}
void pop_front_aux(){
destory(start.cur);
deallocate_node(start.first);
start.set_node(start.node + 1);
start.cur = start.first;
}
void pop_front(){
if(start.cur != start.last - 1){
destory(start.cur);
++start.cur;
}else{
pop_front_aux();
}
}
void clear(){
for(map_pointer node = start.node + 1; node < finish.node; ++node){
destory(*node, *node + buffer_size());
data_allocate::deallocate(*node, buffer_size());
}
if(start.node != finish.node){
destory(start.cur, start.last);
destory(finish.cur, finish.last);
data_allocator::deallocate(finish.first, buffer_size);
}else{
destory(start.cur, finish.last);
}
finish = start;
}
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;
}
iterator 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;
destory(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;
destory(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;
}
}
iterator 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;
}
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);
}
}
size_type size() const { return finish - start; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }
};
deallocate_node：释放map中某个元素的整个空间
|| ？
data_allocator::deallocate：释放map中某个元素空间中的元素部分空间 ？
