本文主要是介绍STL—deque使用及源码剖析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- deque概述
- deque的使用
- deque源码剖析
- 控制中心
- 迭代器
- insert方法
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使用及源码剖析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
