C++ -- 学习系列 std::deque 的原理与使用

一 deque 是什么?

std::deque 是 c++ 一种序列式容器，其与 vector 类似，其底层内存都是连续的，不同的地方在于， vector 是一端开口，在一端放入数据与扩充空间，而 deque 是双端均开口，都可以放入数据与扩充空间。

二原理

deque中存在两种数组：中控数组与缓存数组，在 deque 初始化时，两种数组均会初始化完成。

1. 缓存数组有多个，缓存数组用于存储真正的元素

2.中控数组用于存放缓存数组的地址，方便快速定位到指定缓存数组，进而快速定位元素的位置

其原理图如下：

其迭代器 Iterator 中需要含有四种信息：

1. 当前元素所在缓存数组的首元素地址

2. 当前元素所在缓存数组的尾元素地址

3. 当前元素在缓存数组中的实际地址

4. 当前元素所在缓存数组在中控数组的地址

三使用

1. 容器构造

std::deque<T,Allocator>::deque - cppreference.com

函数	说明
deque( size_type count, const T& value, const Allocator& alloc = Allocator() );	定义 count 个值为 value的元素存储到 deque 中
deque( std::initializer_list<T> init, const Allocator& alloc = Allocator() );	通过 list 定义 deque

#include<iostream>
#include<deque>template<typename T>
void printDeque(std::deque<T>& tmp_deque)
{for(auto iter = tmp_deque.begin(); iter != tmp_deque.end(); iter++){std::cout << *iter <<" ";}std::cout  <<"" << std::endl;
}int main()
{std::deque<int> tmp_deque1(6, 8);printDeque(tmp_deque1);std::deque<int> tmp_deque2;tmp_deque2 = {1, 2 , 3, 4, 5, 6};printDeque(tmp_deque2);return 0;
}

2. 访问元素

https://en.cppreference.com/w/cpp/container/deque

函数	说明
at	返回指定下标元素的引用
operator[]	同上
front	返回容器的首元素引用
back	返回容器的尾元素引用

#include<iostream>
#include<deque>int main()
{std::deque<int> tmp_deque2 = {1, 2 , 3, 4, 5, 6};// Read Elementstd::cout << tmp_deque2.at(1) << std::endl;std::cout << tmp_deque2[2] << std::endl;std::cout << tmp_deque2.front() << std::endl;std::cout << tmp_deque2.back() << std::endl;// Wirte Elementtmp_deque2.at(1) = 888;tmp_deque2[2] = 888;tmp_deque2.front() = 888;tmp_deque2.back() = 888;std::cout << tmp_deque2.at(1) << std::endl;std::cout << tmp_deque2[2] << std::endl;std::cout << tmp_deque2.front() << std::endl;std::cout << tmp_deque2.back() << std::endl;    return 0;
}

3. 容器空间

函数	说明
empty()	返回 deque 是否为空
size()	返回 deque 实际存储元素的个数

#include<deque>
#include<iostream>int  main()
{std::deque<int> tmp_deque2;tmp_deque2 = {1, 2 , 3, 4, 5, 6};std::deque<int> tmp_deque3;std::cout << tmp_deque3.empty() << std::endl;std::cout << tmp_deque3.size() << std::endl;std::cout << tmp_deque2.empty() << std::endl;std::cout << tmp_deque2.size() << std::endl;return 0;
}

4. 容器修改

std::deque - cppreference.com

函数	说明
clear()	清空 deque 的内容
push_back	append 元素到 deque 的尾端
pop_back	将 deque 的尾端元素弹出
push_front	append 元素到 deque 的前端
pop_front	将 deque 的前端元素弹出

#include<deque>
#include<iostream>template<typename T>
void printDeque(std::deque<T>& tmp_deque)
{for(auto iter = tmp_deque.begin(); iter != tmp_deque.end(); iter++){std::cout << *iter <<" ";}std::cout  <<"" << std::endl;
}int main(0
{std::deque<int> tmp_deque2;tmp_deque2 = {1, 2 , 3, 4, 5, 6};printDeque(tmp_deque2);tmp_deque2.push_back(22);tmp_deque2.push_front(33);std::cout << tmp_deque2.front() << std::endl;std::cout << tmp_deque2.back() << std::endl;printDeque(tmp_deque2);tmp_deque2.pop_back();tmp_deque2.pop_front();std::cout << tmp_deque2.front() << std::endl;std::cout << tmp_deque2.back() << std::endl;printDeque(tmp_deque2);tmp_deque2.clear();std::cout << tmp_deque2.empty() << std::endl;return 0;
}

四简单实现

1. 参照原理做了简单的实现，实现了几个简单的函数接口：

// my_deque.h#ifndef MY_DEQUE_H
#define MY_DEQUE_H#include<vector>
#include<iostream>// 迭代器, T 为 my_deque 的元素类型, buffserSize 为每个缓存区的大小
template<typename T, int bufferSize>
struct my_deque_iterator
{T* M_start; // 当前buffer 的起始位置T* M_finish; // 当前buffer 的结尾位置T* M_curr; // 当前元素的位置T** M_map_node; // 当前 buffer 对应的中控数组的位置my_deque_iterator(T* start = nullptr, T* finish = nullptr, T* curr = nullptr, T** map_node = nullptr):M_start(start), M_finish(finish), M_curr(curr),M_map_node(map_node){}my_deque_iterator(const my_deque_iterator& other):M_start(other.M_start), M_finish(other.M_finish), M_curr(other.M_curr),M_map_node(other.M_map_node){}my_deque_iterator(my_deque_iterator& other):M_start(other.M_start), M_finish(other.M_finish), M_curr(other.M_curr),M_map_node(other.M_map_node){}my_deque_iterator& operator++(){if(M_curr == M_finish){M_map_node += 1;set_M_Node(M_map_node);}else{M_curr++;}return *this;}my_deque_iterator& operator++(int){operator++();return *this;}my_deque_iterator& operator--(){if(M_curr == M_start){M_map_node -= 1;set_M_Node(M_map_node, bufferSize - 1);}else{M_curr--;}return *this;}my_deque_iterator& operator--(int){operator--();return *this;}T&  operator*(){return *(this->M_curr);}my_deque_iterator& operator+=(int offset){if(offset >=0 && M_curr + offset <= M_finish || offset < 0 && M_curr + offset >= M_start){M_curr += offset;}else{int diff =  offset >= 0 ? M_finish - M_curr + 1 : M_curr - M_start + 1;int offsetNode = offset >= 0 ? (offset - diff) / bufferSize + 1: ((offset + diff) / bufferSize - 1);int offsetBuff = offset >= 0 ? (offset - diff) % bufferSize :(diff + offset) % bufferSize;M_map_node += offsetNode;if(offset >= 0){set_M_Node(M_map_node, offsetBuff);}else{set_M_Node(M_map_node, bufferSize - 1 - offsetBuff);}}return *this;}my_deque_iterator& operator-=(int offset){this->operator+=(-offset);return *this;}my_deque_iterator operator+(int offset){my_deque_iterator tmp = *this;tmp += offset;return tmp;}my_deque_iterator& operator-(int offset){this->operator-=(offset);return *this;}void set_M_Node(T** map_node, int offset = 0){M_start = M_map_node[0];M_curr = M_start + offset;M_finish = M_start + bufferSize - 1;}bool operator==(my_deque_iterator& other){return this->M_curr == other.M_curr;}bool operator!=(my_deque_iterator& other){return this->M_curr != other.M_curr;}bool operator==(my_deque_iterator&& other){return this->M_curr == other.M_curr;}bool operator!=(my_deque_iterator&& other){return this->M_curr != other.M_curr;}my_deque_iterator& operator=(my_deque_iterator& other){this->M_start = other.M_start;this->M_curr = other.M_curr;this->M_finish = other.M_finish;this->M_map_node = other.M_map_node;return *this;}my_deque_iterator& operator=(my_deque_iterator&& other){this->M_start = other.M_start;this->M_curr = other.M_curr;this->M_finish = other.M_finish;this->M_map_node = other.M_map_node;return *this;}};template<typename T, int bufferSize>
class my_deque
{
public:typedef my_deque_iterator<T, bufferSize> Iterator;public:my_deque(int map_size = 9):M_map_size(map_size){M_map = new T*[M_map_size];for(int i = 0; i < M_map_size; i++){M_map[i] = new T[bufferSize];for(int j = 0; j < bufferSize; j++){M_map[i][j] = 0;}}}~my_deque(){for(int i = 0; i < M_map_size; i++){delete [] M_map[i];}delete [] M_map;}void push_front(T& val){// 元素存储到了起始位置if(M_start.M_curr == &M_map[0][0]){reAlloc(M_map_size * 2);}if(M_start.M_curr == nullptr){M_map[M_map_size/2][0] = val;M_start = Iterator(&M_map[M_map_size/2][0], &M_map[M_map_size/2][0] + bufferSize - 1, &M_map[M_map_size/2][0], &M_map[M_map_size/2]);M_finish = M_start;}else{M_start--;*M_start.M_curr = val;}}void push_front(T&& val){push_front(val);}void push_back(T& val){// 元素存储到了结尾位置if(M_finish.M_curr == &M_map[M_map_size-1][bufferSize-1]){reAlloc(M_map_size * 2);}if(M_finish.M_curr == nullptr){M_map[M_map_size/2][0] = val;M_finish = Iterator(&M_map[M_map_size/2][0],&M_map[M_map_size/2][0] + bufferSize - 1, &M_map[M_map_size/2][0], &M_map[M_map_size/2]);M_start = M_finish;}else{M_finish++;*M_finish.M_curr = val;}}void push_back(T&& val){push_back(val);}T pop_front(){T tmp = *M_start.M_curr;M_start++;return tmp;}T pop_back(){T tmp = *M_finish.M_curr;M_finish--;return tmp;}Iterator begin(){return M_start;}Iterator end(){return M_finish + 1;}int size(){return bufferSize *(M_finish.M_map_node - M_start.M_map_node - 1) +(M_start.M_finish - M_start.M_curr + 1) + (M_finish.M_curr - M_finish.M_start + 1);}T& front(){return *M_start.M_curr;}T& back(){return *M_finish.M_curr;}void print(){for(int i = 0; i < M_map_size; i++){for(int j = 0; j < bufferSize; j++){std::cout << M_map[i][j] <<" ";}std::cout << "" << std::endl;}}private:void reAlloc(int map_size){T** tmp = new T*[map_size];int ori_mid = M_map_size / 2;int new_mid = map_size / 2;tmp[new_mid] = M_map[ori_mid];// mid to leftint new_index = new_mid - 1;for(int i = ori_mid - 1; i >= 0; i--){M_map[new_index--] = tmp[i];}while (new_index >= 0) {M_map[new_index--] = new T[bufferSize];}// mid to rightnew_index = new_mid + 1;for(int i = ori_mid + 1; i < M_map_size; i++){M_map[new_index++] = tmp[i];}while (new_index < map_size) {M_map[new_index++] = new T[bufferSize];}M_map_size = map_size;T** tmp1 = M_map;M_map = tmp;tmp = tmp1;delete tmp;}private:int  M_map_size; // 中控 数组 的长度T**  M_map = nullptr;  // 中控数组Iterator   M_start; // 起始元素Iterator   M_finish; // 结尾元素
};#endif // MY_DEQUE_H// main.cpp
#include<iostream>
#include<my_deque.h>void testMyDeque()
{my_deque<int, 3> tmp_deque;tmp_deque.push_back(1);
//    std::cout << " --------- " << std::endl;
//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_back(2);//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_back(3);
//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_back(4);
//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_back(5);
//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_front(2);
//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_front(3);
//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_front(4);
//    tmp_deque.print();
//    std::cout << " --------- " << std::endl;tmp_deque.push_front(5);
//    tmp_deque.print();for(my_deque<int, 3>::Iterator iter = tmp_deque.begin(); iter != tmp_deque.end(); iter++){std::cout << *iter << " ";}std::cout << " --------- " << std::endl;auto iter = tmp_deque.begin();std::cout << *iter <<std::endl;//std::cout << *(iter-3) <<std::endl;
//    std::cout << (iter).M_start <<std::endl;
//    std::cout << (iter).M_curr <<std::endl;
//    std::cout << (iter).M_finish <<std::endl;
//    std::cout << (iter).M_map_node <<std::endl;std::cout << " --------- " << std::endl;std::cout << *(iter+3) <<std::endl;
//    std::cout << (iter+3).M_start <<std::endl;
//    std::cout << (iter+3).M_curr <<std::endl;
//    std::cout << (iter+3).M_finish <<std::endl;
//    std::cout << (iter+3).M_map_node <<std::endl;std::cout << " --------- " << std::endl;auto iter2 = iter + 3;std::cout << *(iter2-3) <<std::endl;
//    std::cout << (iter2-3).M_start <<std::endl;
//    std::cout << (iter2-3).M_curr <<std::endl;
//    std::cout << (iter2-3).M_finish <<std::endl;
//    std::cout << (iter2-3).M_map_node <<std::endl;std::cout << " --------- " << std::endl;std::cout << *(iter+5) <<std::endl;
//    std::cout << (iter+5).M_start <<std::endl;
//    std::cout << (iter+5).M_curr <<std::endl;
//    std::cout << (iter+5).M_finish <<std::endl;
//    std::cout << (iter+5).M_map_node <<std::endl;std::cout << "size: " << tmp_deque.size() << std::endl;std::cout << "pop_back: " << tmp_deque.pop_back() << std::endl;std::cout << "size: " << tmp_deque.size() << std::endl;std::cout << "pop_front: " << tmp_deque.pop_front() << std::endl;std::cout << "size: " << tmp_deque.size() << std::endl;std::cout << "empty: " << tmp_deque.empty() << std::endl;
}int main()
{testMyDeque();return 0;
}

输出：