一 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;
}
输出: