当前位置：个人在线分享 > 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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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复现
    admin

    admin 钻石

    分享到：

    相关推荐

    E-->