C++迈向精通：STL的Deque复现

2024-06-10 00:04
文章标签 c++ 精通 复现 stl deque 迈向

本文主要是介绍C++迈向精通：STL的Deque复现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++迈向精通：STL的Deque复现

最近忙着写一个其他的小玩意，好久没更新博客了，手痒更新一下：
本期来讲一讲C++中的STL中的deque的底层实现原理。

deque的地位

STL中的deque的地位很高
主要原因是由于泛型思想和对于其他容器的影响，
因为queue以及stack都是基于deque实现的。

实现deque需要思考的几点

这次我没有向上篇博客一样提前查看 deque 的源码，但是基本的实现方式我已经猜的七七八八了。

主要是下面亮点：

  • 数据的存储方式
  • 支持的基本操作

存储方式

双端队列，底层实现应当是一个双向链表，节点中应该有两个指针，指向相同类型的节点。
还有一个指针指向需要存储的数据区域。

支持的基本操作

  • 两头元素的压入与弹出
  • 队列清空
  • 迭代器的遍历访问和随机访问（这个似乎不需要实现，但是当时我给写出来了）

实现过程

程序的设计方法是从具体到抽象的，因此我们可以先来尝试将支持的操作写出来：

int main() {my::deque<int> dq; // 定义了一个双端队列_PrintLine_("input");  // 这个是一个宏，用于打印一个标题，测试时便于观察std::cout << "dq.init..." << std::endl;// 压入1到10的元素for (int i = 0; i < 10; ++i) {dq.push_back(i);}std::cout << "dq.init done." << std::endl;// 测试大小_PrintLine_("size");std::cout << "dq.size() = " << dq.size() << std::endl;// 队列的弹出测试_PrintLine_("pop and front");std::cout << "dq.pop..." << std::endl;for (int i = 0; i < 10; ++i) {std::cout << dq.front() << std::endl;dq.pop_front();}std::cout << "dq.pop done" << std::endl;// 再次压入_PrintLine_("init again");for (int i = 0; i < 10; ++i) {dq.push_back(i);}// 队列的判空测试和清空测试_PrintLine_("clear and empty");std::cout << "dq.clear() ..." << std::endl;dq.clear();std::cout << "dq.clear() done" << std::endl;if (dq.empty()) {std::cout << "dq is empty." << std::endl;} else {std::cout << "dq isn't empty." << std::endl;}std::cout << "init again..." << std::endl;for (int i = 0; i < 10; ++i) {dq.push_back(i);}if (dq.empty()) {std::cout << "dq is empty." << std::endl;} else {std::cout << "dq isn't empty." << std::endl;}_PrintLine_("auto text");// 迭代器测试for (auto x : dq) {std::cout << x << std::endl;}return 0;
}

下面是上面程序的那个标题输出宏的代码：

#define _PrintLine_(str) \for (int i = 0; i < 20; ++i) { \std::cout << '='; \} \std::cout << #str; \for (int i = 0; i < 20; ++i) { \std::cout << '='; \} \std::cout << std::endl;

接下来才是正题：
首先来实现底层的数据结构，双向链表的节点：

节点中有三个元素：

  • 指向上一个节点的指针
  • 指向下一个节点的指针
  • 指向数据区的指针

关于这个指向数据区域的指针，其实也可以写成静态成员，但是这样的话，数据就会被存放在栈区，我一个强迫症还是觉得栈区的空间太小，而且我个人比较喜欢对堆区进行操作（虽然有讨厌的内存泄漏问题），因此将其改成指针，实际上我猜测STL源码中的 deque 的数据应该是存放在栈区中的。

class _deque_node {typedef _deque_node _node;
public:_deque_node() : _data(new T()), _prev(nullptr), _next(nullptr) {}_deque_node(T &data) : _data(new T(data)), _prev(nullptr), _next(nullptr) {}_deque_node(T &&data) : _data(new T()), _prev(nullptr), _next(nullptr) {*_data = data;}~_deque_node() {delete _data;_prev = nullptr;_next = nullptr;}T *_data;_node *_prev;_node *_next;
};

为了方便，我没有将节点中的成员变量设置为私有权限。
另外，这个右值引用的有参构造应该是用不到的，可以删除，只不过我喜欢在写构造函数的时候喜欢写全一点。

具体实现方法不做详细解释，上面的代码相信有基础语法基础的人应该都能看懂。（毕竟我写的那么规范！）

迭代器先放在一边，我们先来写主要的内容，双端队列。

双端队列的成员应该有三个：

  • 指向头节点的指针
  • 指向尾节点的指针
  • 长度
  size_t _size;_node *_head; // 虚拟头节点 _node *_tail;

为什么要设置一个虚拟头节点呢？这是因为如果没有设置虚拟头节点，那么在定义这个容器时，两个指针就都会指向空地址，这样的话在插入之前就需要进行一次特殊判断了，对于大量数据的插入会降低速度。

构造函数：

  deque() : _head(new _node()), _tail(_head), _size(0) {}

接下来就是对应方法的实现：

首先是最简单的 size 和 判空 方法:

  size_t size() const {return _size;}bool empty() const {return _size == 0;}

然后是，两端的压入方法：

  void push_front(T &data) {_node *new_node = new _node(data);new_node->_next = this->_head->_next;this->_head->_next->_prev = new_node;this->_head->_next = new_node;new_node->_prev = this->_head;_size += 1;}void push_back(T &data) {_node *new_node = new _node(data);this->_tail->_next = new_node;new_node->_prev = this->_tail;this->_tail = new_node;_size += 1;}

然后是两端的弹出方法：

  void pop_front() {if (empty()) return ;if (this->_size == 1) {delete this->_tail;this->_tail = this->_head;} else {_node *old_node = this->_head->_next;this->_head->_next = old_node->_next;old_node->_next->_prev = this->_head;delete old_node;}_size -= 1;}void pop_back() {if (empty()) return ;_node *old_node = this->_tail;this->_tail = old_node->_prev;this->_tail->_next = nullptr;delete old_node;_size -= 1;}

不要忘了从头插入的时候跳过第一个虚拟头节点

然后是 clear 方法：

  void clear() {_node *cur = this->_head->_next;_node *old = this->_head;while(!empty()) {pop_back();}

还有一个查看头尾节点的方法：

  _node &front() {return *_head->_next;}_node &back() {return *_tail;}

到了这里，我们需要输出他们返回头尾节点的值，因此我们需要重载一下输出运算符号：
一定是在类外呦：

template <typename T>
std::ostream &operator<<(std::ostream &out, _deque_node<T> &node) {out << *node._data;return out;
}

到这里我们的双端队列实现的就差不多了。此时，我们一开始写的代码应该只剩下最后的一个 for auto 遍历方法还在报错，这个是因为我们没有实现迭代器的一系列的方法，如果你不明白 for auto 的原理的话，需要参考其他的博客或者资料了，如果你感性的话，可以私信我，我会出一篇博客专门来写auto for的。

迭代器的实现：

迭代器的表现形式更像是指针，因此成员可以是一个指针。
我直接将整个代码放在这里，具体细节会在注释中提及


template <typename T>
class _deque_node_iterator {
typedef _deque_node<T> * iterator;
public:// 构造函数_deque_node_iterator() : _ptr(nullptr) {}// 用于类为迭代器的节点赋值，通常是iter = dq.begin()_deque_node_iterator(iterator ptr) : _ptr(ptr) {}// 用于类外迭代器的相互赋值操作_deque_node_iterator(_deque_node_iterator &ptr) : _ptr(ptr) {}// 下面的所有运算符的重载都是用于 auto for// 原理并不难。bool operator==(const _deque_node_iterator &obj) const {return _ptr == obj._ptr;}bool operator!=(const _deque_node_iterator &obj) const {return !this->operator==(obj);}iterator &operator++() {_ptr = _ptr->_next;return _ptr;}iterator operator++(int) {new iterator(_ptr);_ptr = _ptr->_next;return _ptr;}iterator &operator--() {_ptr = _ptr->_prev;return _ptr;}iterator operator--(int) {new iterator(_ptr);_ptr = _ptr->_prev;return _ptr;}T &operator*() {return *_ptr->_data;}
private:iterator _ptr;
};

实现之后，还差最后一步，那就是在我们的 deque 类中添加两个成员方法：

  • begin()
  • end()

众所周知迭代器是左闭右开的，因此我们返回虚拟头节点的下一个节点和尾节点的下一个节点：

  iterator begin() const {return this->_head->_next;}iterator end() const {return this->_tail->_next;}

完整代码

/*************************************************************************> File Name: deque.cpp> Author:Royi> Mail:royi990001@gmail.com> Created Time: Fri 07 Jun 2024 01:25:31 PM HKT> Describe:************************************************************************/#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <ctype.h>
#include <cmath>
#include <string>
#include <sstream>
#include <functional>#define _PrintLine_(str) \for (int i = 0; i < 20; ++i) { \std::cout << '='; \} \std::cout << #str; \for (int i = 0; i < 20; ++i) { \std::cout << '='; \} \std::cout << std::endl;namespace my {template <typename T>
class _deque_node {typedef _deque_node _node;
public:_deque_node() : _data(new T()), _prev(nullptr), _next(nullptr) {}_deque_node(T &data) : _data(new T(data)), _prev(nullptr), _next(nullptr) {}_deque_node(T &&data) : _data(new T()), _prev(nullptr), _next(nullptr) {*_data = data;}~_deque_node() {delete _data;_prev = nullptr;_next = nullptr;}T *_data;_node *_prev;_node *_next;
};template <typename T>
std::ostream &operator<<(std::ostream &out, _deque_node<T> &node) {out << *node._data;return out;
}template <typename T>
class _deque_node_iterator {
typedef _deque_node<T> * iterator;
public:_deque_node_iterator() : _ptr(nullptr) {}_deque_node_iterator(iterator ptr) : _ptr(ptr) {}_deque_node_iterator(_deque_node_iterator &ptr) : _ptr(ptr) {}bool operator==(const _deque_node_iterator &obj) const {return _ptr == obj._ptr;}bool operator!=(const _deque_node_iterator &obj) const {return !this->operator==(obj);}iterator &operator++() {_ptr = _ptr->_next;return _ptr;}iterator operator++(int) {new iterator(_ptr);_ptr = _ptr->_next;return _ptr;}iterator &operator--() {_ptr = _ptr->_prev;return _ptr;}iterator operator--(int) {new iterator(_ptr);_ptr = _ptr->_prev;return _ptr;}T &operator*() {return *_ptr->_data;}private:iterator _ptr;
};template <typename T>
class deque {
typedef _deque_node<T> _node;
typedef _deque_node_iterator<T> iterator;
public:deque() : _head(new _node()), _tail(_head), _size(0) {}size_t size() const {return _size;}bool empty() const {return _size == 0;}_node &front() {return *_head->_next;}_node &back() {return *_tail;}void push_front(T &data) {_node *new_node = new _node(data);new_node->_next = this->_head->_next;this->_head->_next->_prev = new_node;this->_head->_next = new_node;new_node->_prev = this->_head;_size += 1;}void push_back(T &data) {_node *new_node = new _node(data);this->_tail->_next = new_node;new_node->_prev = this->_tail;this->_tail = new_node;_size += 1;}void pop_front() {if (empty()) return ;if (this->_size == 1) {delete this->_tail;this->_tail = this->_head;} else {_node *old_node = this->_head->_next;this->_head->_next = old_node->_next;old_node->_next->_prev = this->_head;delete old_node;}_size -= 1;}void pop_back() {if (empty()) return ;_node *old_node = this->_tail;this->_tail = old_node->_prev;this->_tail->_next = nullptr;delete old_node;_size -= 1;}iterator begin() const {return this->_head->_next;}iterator end() const {return this->_tail->_next;}void clear() {_node *cur = this->_head->_next;_node *old = this->_head;while(!empty()) {pop_back();}}private:size_t _size;_node *_head; // 虚拟头节点 _node *_tail;
};}int main() {my::deque<int> dq;_PrintLine_("input");std::cout << "dq.init..." << std::endl;for (int i = 0; i < 10; ++i) {dq.push_back(i);}std::cout << "dq.init done." << std::endl;_PrintLine_("size");std::cout << "dq.size() = " << dq.size() << std::endl;_PrintLine_("pop and front");std::cout << "dq.pop..." << std::endl;for (int i = 0; i < 10; ++i) {std::cout << dq.front() << std::endl;dq.pop_front();}std::cout << "dq.pop done" << std::endl;_PrintLine_("init again");for (int i = 0; i < 10; ++i) {dq.push_back(i);}_PrintLine_("clear and empty");std::cout << "dq.clear() ..." << std::endl;dq.clear();std::cout << "dq.clear() done" << std::endl;if (dq.empty()) {std::cout << "dq is empty." << std::endl;} else {std::cout << "dq isn't empty." << std::endl;}std::cout << "init again..." << std::endl;for (int i = 0; i < 10; ++i) {dq.push_back(i);}if (dq.empty()) {std::cout << "dq is empty." << std::endl;} else {std::cout << "dq isn't empty." << std::endl;}_PrintLine_("auto text");for (auto x : dq) {std::cout << x << std::endl;}return 0;
}

运行结果：

❯ ./deque
===================="input"====================
dq.init...
dq.init done.
===================="size"====================
dq.size() = 10
===================="pop and front"====================
dq.pop...
0
1
2
3
4
5
6
7
8
9
dq.pop done
===================="init again"====================
===================="clear and empty"====================
dq.clear() ...
dq.clear() done
dq is empty.
init again...
dq isn't empty.
===================="auto text"====================
0
1
2
3
4
5
6
7
8
9

:wq 拜拜～～～～

这篇关于C++迈向精通：STL的Deque复现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1046682。

相关文章

【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
2024/9/8 c++ smart

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2