本文共 6477 字，大约阅读时间需要 21 分钟。

deque概述

deque容器为一个给定类型的元素进行线性处理，像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素。但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。 deque容器可以在双端插入和删除,其底层是分段连续的,对于使用者来说造成了一种连续的假象。

deque的使用

deque类常用的函数有：

(1) 构造函数

deque():创建一个空deque

deque(int nSize):创建一个deque,元素个数为nSize

deque(int nSize,const T& t):创建一个deque,元素个数为nSize,且值均为t

deque(const deque &):复制构造函数

(2) 增加函数

void push_front(const T& x):双端队列头部增加一个元素X

void push_back(const T& x):双端队列尾部增加一个元素x

iterator insert(iterator it,const T& x):双端队列中某一元素前增加一个元素x

void insert(iterator it,int n,const T& x):双端队列中某一元素前增加n个相同的元素x

void insert(iterator it,const_iterator first,const_iteratorlast):双端队列中某一元素前插入另一个相同类型向量的[forst,last)间的数据

(3) 删除函数

Iterator erase(iterator it):删除双端队列中的某一个元素

Iterator erase(iterator first,iterator last):删除双端队列中[first,last）中的元素

void pop_front():删除双端队列中最前一个元素

void pop_back():删除双端队列中最后一个元素

void clear():清空双端队列中最后一个元素

(4) 遍历函数

reference at(int pos):返回pos位置元素的引用

reference front():返回首元素的引用

reference back():返回尾元素的引用

iterator begin():返回向量头指针，指向第一个元素

iterator end():返回指向向量中最后一个元素下一个元素的指针（不包含在向量中）

reverse_iterator rbegin():反向迭代器，指向最后一个元素

reverse_iterator rend():反向迭代器，指向第一个元素的前一个元素

(5) 判断函数

bool empty() const:向量是否为空，若true,则向量中无元素

(6) 大小函数

Int size() const:返回向量中元素的个数

int max_size() const:返回最大可允许的双端对了元素数量值

(7) 其他函数

void swap(deque&):交换两个同类型向量的数据

void assign(int n,const T& x):向量中第n个元素的值设置为x

#include 
   
    #include 
    
     #include 
     
      using namespace std;void main() {   	//初始化	deque
      
        d;	deque
       
         d2(5);	//5个结点的deque	deque
        
          d3(5, 1);//5个结点元素为1的deque deque
         
           d4(d3); //用d3初始化d4 deque
          
            d5(d4.begin(), d4.end()); //算法操作 reverse(d5.begin(), d5.end()); //翻转 sort(d5.begin(), d5.end()); //排序 //遍历操作 for (auto i : d) { cout << i << endl; } for (auto i = d.begin(); i != d.end(); i++) { cout << *i << endl; } //成员函数 d.assign(d5.begin(), d5.end()); d.assign(5, 6); d.back(); d.front(); d.empty(); d.erase(d.begin()++); //删除第2个结点 d.insert(d.begin(), 5); //在首部插入元素5 d.insert(d.begin(), 3, 0); //在首部插入3个0 d.max_size(); d.pop_back(); d.pop_front(); d.push_back(5); d.push_front(5); d.swap(d2); d.resize(2); //修改为2个结点大小}
          
         
        
       
      
     
    
   

deque源码剖析

deque内部是分段连续的，对使用者表现为连续

template
   
    class deque {   public:    typedef T value_type;    typedef _deque_iterator
    
      iterator;protected:    typedef pointer *map_pointer;   // T**protected:    iterator start;    iterator finish;    map_pointer map;		// 控制中心,数组中每个元素指向一个buffer    size_type map_size;public:    iterator begin() {    return start; }    iterator end() {    return finish; }    size_type size() const {    return finish - start; }    // ...};
    
   

控制中心

deque::map的类型为二重指针T**，称为控制中心，其中每个元素指向一个buffer

迭代器

template
   
    struct __deque_iterator {       // 定义5个关联类型    typedef random_access_iterator_tag	iterator_category; 	// 关联类型1    typedef T 							value_type;       	// 关联类型2    typedef ptrdiff_t 					difference_type;	// 关联类型3    typedef Ptr 						pointer;			// 关联类型4    typedef Ref 						reference;			// 关联类型5    typedef size_t size_type;    typedef T **map_pointer;    typedef __deque_iterator self;    // 迭代器核心字段:4个指针    T *cur;     		// 指向当前元素    T *first;   		// 指向当前buffer的开始    T *last;    		// 指向当前buffer的末尾    map_pointer node;   // 指向控制中心    // ...};
   

迭代器deque::iterator的核心字段是4个指针:cur指向当前元素、first和last分别指向当前buffer的开始和末尾、node指向控制中心

迭代器deque::iterator模拟空间的连续性：

template
   
    struct __deque_iterator {       // 迭代器核心字段:4个指针    T *cur;            	// 指向当前元素    T *first;        	// 指向当前buffer的开始    T *last;            // 指向当前buffer的末尾    map_pointer node;   // 指向控制中心    // ...        difference_type operator-(const self &x) const {           return             difference_type(buffer_size()) * (node - x.node - 1) +	// 两根迭代器间的长度               (cur - first) +      								// 当前迭代器到当前buffer末尾的长度               (x.last - x.cur);    								// 迭代器x到其buffer首部的长度    }    self &operator++() {           ++cur;				// 切换至下一元素        if (cur == last) {    	// 若到达buffer末尾,则跳转至下一buffer的起点            set_node(node + 1);            cur = first;         }        return *this;    }    void set_node(map_pointer new_node) {    	// 设置当前元素所在的buffer为new_node        node = new_node;        first = *new_node;        last = first + difference_type(buffer_size());    }    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()))	            // 若目标位置在同一buffer内,则直接跳转            cur += n;        else {   			// 若目标位置不在同一buffer内,则先切换buffer,再在buffer内寻址            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); }};
   

insert方法

deque::insert方法先判断插入元素在容器的前半部分还是后半部分,再将数据往比较短的那一半推

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 tmp = finish;        --tmp;        return tmp;    } else {           return insert_aux(position, x);    }}template
   
    typename deque
    
     ::iterator deque
     
      ::insert_aux(iterator pos, const value_type &x) {       difference_type index = pos - start;    // 插入点前的元素数    value_type x_copy = x;    if (index < size() / 2) {       	  		// 1. 如果插入点前的元素数较少,则将前半部分元素向前推        push_front(front());        		// 1.1. 在容器首部创建元素        // ...        copy(front2, pos1, front1); 		// 1.2. 将前半部分元素左移    } else {                           		// 2. 如果插入点后的元素数较少,则将后半部分元素向后推        push_back(back());          		// 2.1. 在容器末尾创建元素        copy_backward(pos, back2, back1); 	// 2.2. 将后半部分元素右移    }    *pos = x_copy;		// 3. 在插入位置上放入元素    return pos;}
     
    
   

转载地址：http://scjnz.baihongyu.com/