STL—deque使用及源码剖析

本文主要是介绍STL—deque使用及源码剖析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 <deque>
#include <algorithm>
#include <iostream>
using namespace std;void main() {//初始化deque<int> d;deque<int> d2(5);	//5个结点的dequedeque<int> d3(5, 1);//5个结点元素为1的dequedeque<int> d4(d3);	//用d3初始化d4deque<int> 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);	//在首部插入元素5d.insert(d.begin(), 3, 0);	//在首部插入3个0d.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 T, class Alloc =alloc, size_t BufSiz = 0>
class deque {
public:typedef T value_type;typedef _deque_iterator<T, T &, T *, BufSiz> iterator;
protected:typedef pointer *map_pointer;   // T**
protected:iterator start;iterator finish;map_pointer map;		// 控制中心,数组中每个元素指向一个buffersize_type map_size;
public:iterator begin() { return start; }iterator end() { return finish; }size_type size() const { return finish - start; }// ...
};

控制中心

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

迭代器

template<class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {// 定义5个关联类型typedef random_access_iterator_tag	iterator_category; 	// 关联类型1typedef T 							value_type;       	// 关联类型2typedef ptrdiff_t 					difference_type;	// 关联类型3typedef Ptr 						pointer;			// 关联类型4typedef Ref 						reference;			// 关联类型5typedef 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<class T, class Ref, class Ptr, size_t BufSiz>
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_nodenode = 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_frontpush_front(x);return start;} else if (position.cur == finish.cur) {	// 若插入位置是容器尾部,则直接push_backpush_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) {    	  		// 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;
}

这篇关于STL—deque使用及源码剖析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---