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_backappend 元素到 deque 的尾端
pop_back将 deque 的尾端元素弹出
push_frontappend 元素到 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;
}

输出:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/145301.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

3D孪生场景搭建:模型区域摆放

前面介绍完了NSDT场景编辑器的线性绘制和阵列绘制&#xff0c;本章将讲述下编辑器的另一种绘制方式&#xff1a;区域绘制。 1、区域绘制功能简介 在场景中绘制资产时&#xff0c;除使用上述两个的方式外&#xff0c;NSDT 编辑器还支持使用区域绘制的方式进行绘制。先选取需要…

GEO生信数据挖掘(一)数据集下载和初步观察

检索到目标数据集后&#xff0c;开始数据挖掘&#xff0c;本文以阿尔兹海默症数据集GSE1297为例 目录 GEOquery 简介 安装并加载GEOquery包 getGEO函数获取数据&#xff08;联网下载&#xff09; 更换下载数据源 对数据集进行初步观察处理 GEOquery 简介 GEOquery是一个…

聊聊并发编程——并发容器和阻塞队列

目录 一.ConcurrentHashMap 1.为什么要使用ConcurrentHashMap&#xff1f; 2.ConcurrentHashMap的类图 3.ConcurrentHashMap的结构图 二.阻塞队列 Java中的7个阻塞队列 ArrayBlockingQueue&#xff1a;一个由数组结构组成的有界阻塞队列。 LinkedBlockingQueue&#xf…

用go实现http服务端和请求端

一、概述 本文旨在学习记录下如何用go实现建立一个http服务器&#xff0c;同时构造一个专用格式的http客户端。 二、代码实现 2.1 构造http服务端 1、http服务处理流程 基于HTTP构建的服务标准模型包括两个端&#xff0c;客户端(Client)和服务端(Server)。HTTP 请求从客户端…

PHP8的静态变量和方法-PHP8知识详解

我们在上一课程讲到了public、private、protected这3个关键字&#xff0c;今天我们来讲解static关键字&#xff0c;明天再讲解final关键字。 如果不想通过创建对象来调用变量或方法&#xff0c;则可以将该变量或方法创建为静态变量或方法&#xff0c;也就是在变量或方法的前面…

【PyTorch实战演练】使用Cifar10数据集训练LeNet5网络并实现图像分类(附代码)

文章目录 0. 前言1. Cifar10数据集1.1 Cifar10数据集下载1.2 Cifar10数据集解析 2. LeNet5网络2.1 LeNet5的网络结构2.2 基于PyTorch的LeNet5网络编码 3. LeNet5网络训练及输出验证3.1 LeNet5网络训练3.2 LeNet5网络验证 4. 完整代码4.1 训练代码4.1 验证代码 0. 前言 按照国际…

C语言文件操作与管理

一、为什么使用文件 在我们前面练习使用结构体时&#xff0c;写通讯录的程序&#xff0c;当通讯录运行起来的时候&#xff0c;可以给通讯录中增加、删除数据&#xff0c;此时数据是存放在内存中&#xff0c;当程序退出的时候&#xff0c;通讯录中的数据自然就不存在了&#xff…

Java 基于 SpringBoot 的在线学习平台

1 简介 基于SpringBoot的Java学习平台&#xff0c;通过这个系统能够满足学习信息的管理及学生和教师的学习管理功能。系统的主要功能包括首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;教师管理&#xff0c;课程信息管理&#xff0c;类型管理&#xff0c;作业信息…

大数据Doris(一):Doris概述篇

文章目录 Doris概述篇 一、前言 二、Doris简介

队列的各个函数的实现

1.第一个结构是存放链表的数据&#xff0c;第二个结构体是存放头节点和尾节点的以方便找到尾节点&#xff0c;存放头节点的是phead&#xff0c;尾节点的是ptail typedef struct QueueNode {struct QueueNode* next;//单链表QDataType data;//放数据 }QNode;typedef struct Queu…

并查集LRUCache

文章目录 并查集1.概念2. 实现 LRUCache1. 概念2. 实现使用标准库实现自主实现 并查集 1.概念 并查集是一个类似于森林的数据结构&#xff0c;并、查、集指的是多个不相干的集合直接的合并和查找&#xff0c;并查集使用于N个集合。适用于将多个元素分成多个集合&#xff0c;在…

脉冲法和方向盘转角法计算车辆位置不同应用工况

1. 脉冲法计算车辆位置 在定义下的世界坐标系中&#xff0c;车辆运动分为右转后退、右转前进、左转后退、左转前进、直线前进、直线后退和静止七种工况&#xff0c;因此需要推倒出一组包含脉冲、车辆运动方向和车辆结构尺寸参数的综合方程式进行车辆轨迹的实时迭代计算。由于直…

Linux:nginx---web文件服务器

我这里使用的是centos7系统 nginx源码包安装 Linux&#xff1a;nginx基础搭建&#xff08;源码包&#xff09;_鲍海超-GNUBHCkalitarro的博客-CSDN博客https://blog.csdn.net/w14768855/article/details/131445878?ops_request_misc%257B%2522request%255Fid%2522%253A%25221…

【AntDesign】封装全局异常处理-全局拦截器

[toc] 场景 本文前端用的是阿里的Ant-Design框架&#xff0c;其他框架也有全局拦截器&#xff0c;思路是相同&#xff0c;具体实现自行百度下吧 因为每次都需要调接口&#xff0c;都需要单独处理异常情况&#xff08;code !0&#xff09;&#xff0c;因此前端需要对后端返回的…

每日一博 - 闲聊 Java 中的中断

文章目录 概述常见的中断问题中断一个处于运行状态的线程中断一个正在 sleep 的线程中断一个由于获取 ReentrantLock 锁而被阻塞的线程 如何正确地使用线程的中断标识JDK 的线程池 ThreadPoolExecutor 内部是如何运用中断实现功能的小结 概述 在 Java 中&#xff0c;中断是一种…

应用在手机触摸屏中的电容式触摸芯片

触控屏&#xff08;Touch panel&#xff09;又称为触控面板&#xff0c;是个可接收触头等输入讯号的感应式液晶显示装置&#xff0c;当接触了屏幕上的图形按钮时&#xff0c;屏幕上的触觉反馈系统可根据预先编程的程式驱动各种连结装置&#xff0c;可用以取代机械式的按钮面板&…

ElementUI实现登录注册啊,axios全局配置,CORS跨域

一&#xff0c;项目搭建 认识ElementUI ElementUI是一个基于Vue.js 2.0的桌面端组件库&#xff0c;它提供了一套丰富的UI组件&#xff0c;包括表格、表单、弹框、按钮、菜单等常用组件&#xff0c;具备易用、美观、高效、灵活等优势&#xff0c;能够极大的提高Web应用的开发效…

Lua函数

--函数--无参无返回值 function F1()print("F1函数") end F1() print("*****************")--有参 function F2(a)print("F2函数"..a) end F2(2) --如果传入参数和函数数量不一致 --不会报错只是补空 F2(1,2) print("*****************&quo…

【夏虫语冰】测试服务器端口是否打开(命令行、Python)

文章目录 1、简介2、命令行2.1 telnet2.1.1 工具简介2.1.2 工具配置2.1.3 工具使用 2.2 curl2.2.1 工具简介2.2.1 工具下载2.2.1 工具使用 2.3 wget2.3.1 工具简介2.3.2 工具下载2.3.2 工具使用 2.4 nc2.4.1 工具简介2.4.2 工具安装2.4.3 工具使用 2.5 ssh2.5.1 工具简介2.5.2 …

数据链路层 MTU 对 IP 协议的影响

在介绍主要内容之前&#xff0c;我们先来了解一下数据链路层中的"以太网" 。 “以太网”不是一种具体的网络&#xff0c;而是一种技术标准&#xff1b;既包含了数据链路层的内容&#xff0c;也包含了一些物理层的内容。 下面我们再来了解一下以太网数据帧&#xff…