模拟实现STL中的list

🕗 发布于 2024-11-18 11:30 c++ 开发语言

1.设计list的结点

2.设计list的迭代器

3.list类的设计总览

1.设计list的结点

STL中的list采用的底层数据结构是带头双向循环链表，我们也采用这种方式，因此，结点可以这样来设计。

代码如下：为了满足容器中可以存放各种类型的数据这一需求，我们使用模板元编程的思想，将结点设计为模板类型。

/* 定义节点 */
template<class T>       // T表示存储的数据的类型 
struct ListNode
{
ListNode<T>* _prev; // 指向前一个结点
ListNode<T>* _next; // 指向后一个结点
T _data;            // 存储数据

ListNode(const T& x = T()) // 构造函数
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};

2.设计list的迭代器

list的底层空间不像string和vector那样是连续的，因此，list的迭代器需要对结点的指针进行封装，来模拟指针的行为。比如：连续空间上的指针进行++操作，直接就能到达后一个数据的位置，但是不连续空间上的指针进行++操作不能到达后一个数据的位置。

同样，我们需要将迭代器设计为模板类型，我们设计三个模板参数，分别是：

T：存储的数据的类型。
Ref：存储的数据的引用类型，相当于T&。
Ptr：存储的数据的指针类型，相当于T*。

template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;

// 成员变量
Node* _node; // 对结点的指针进行封装
};

之所以遮掩设计是为了同时满足const对象和非const对象的需求，const对象需要调用const版本的迭代器，非const兑现需要调用非const版本的迭代器。

代码如下：迭代器模仿的是原生指针的行为，因此，我们实现迭代器的时候，至少需要实现以下操作。

前置++和后置++
前置--和后置--
指针的解引用（*）操作
指针的箭头（->）操作
判断相等和不相等操作

/* 
* 迭代器
* T：存储的元素类型
* Ref：该类型的引用T&
* Ptr：该类型的指针T*
*/
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;

/* 成员变量 */
Node* _node; // 对结点的指针进行封装即可

/* 成员函数 */
__list_iterator(Node* x)
:_node(x)
{}

// ++it
self& operator++()        // 前置++，让当前迭代器指向下一个节点
{
_node = _node->_next;
return *this;         // 返回++以后的值
}

// it++
self operator++(int)      // 后置++，让当前迭代器指向下一个节点
{
//__list_iterator<T> tmp(*this);
self tmp(*this);

_node = _node->_next;

return tmp;           // 返回++之前的值
}

// --it
self& operator--()        // 前置--，让当前迭代器指向上一个节点
{
_node = _node->_prev;
return *this;         // 返回--之后的值
}

// it--
self operator--(int)      // 后置--，让当前迭代器指向上一个节点
{
self tmp(*this);

_node = _node->_prev; // 返回--之前的值

return tmp;
}

Ref operator*()           // 返回当前结点的数据域的引用
{
return _node->_data;
}

Ptr operator->()          // 返回当前结点中数据域的指针
{
return &(_node->_data);
}

bool operator!=(const self& s) // 判断两个迭代器是否不相等
{
return _node != s._node;
}

bool operator==(const self& s) // 判断两个迭代器是否相等
{
return _node == s._node;
}
};

3.list类的设计总览

我们的list类设计如下：

成员变量只有一个头结点的指针。
成员函数涉及迭代器的相关操作，四个特殊的成员函数，插入和删除操作。

template<class T> // T表示存储的数据的类型
class list
{
private:
typedef ListNode<T> Node; // 对结点类型重命名
Node* _head;              // 定义一个头结点
public:
/* 迭代器的声明 */
typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器

/* 迭代器的相关操作 */
iterator begin();             // 返回第一个元素的迭代器
iterator end();               // 返回最后一个元素的后一个位置的迭代器
const_iterator begin() const; // 提供给const对象的begin
const_iterator end() const;   // 提供给const对象的end

/* 四个特殊的成员函数 */
list();                                // 无参的默认构造函数
~list();                               // 析构函数
list(const list<T>& lt);               // 拷贝构造
list<T>& operator=(const list<T>& lt); // 赋值运算符重载函数

/* 插入操作 */
iterator insert(iterator pos, const T& x); // 在指定位置之前插入指定元素
void push_back(const T& x);             // 尾插
void push_front(const T& x);           // 头插

/* 删除操作 */
iterator erase(iterator pos); // 删除指定位置的元素           
void pop_back();          // 尾删
void pop_front();          // 头删
};

4.list类的迭代器操作

begin()系列接口用于获取第一个元素的迭代器，也就是头结点后面那个元素的迭代器。

end()系列接口用于获取最后一个元素后面那个元素的迭代器，也就是头结点的迭代器。

为了满足const对象和非const对象的不同需求，我们提供const版本和非const版本。

/* 迭代器的声明 */
typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器

iterator begin()         // 返回第一个元素的迭代器
{
return _head->_next; // 利用单参数的构造函数进行隐式的类型转换
}

iterator end()    // 返回最后一个元素的后一个位置的迭代器
{
return _head; // 利用单参数的构造函数进行隐式的类型转换
}

const_iterator begin() const // 提供给const对象的begin
{
return _head->_next;
}

const_iterator end() const   // 提供给const对象的end
{
return _head;
}

5.list类的四个特殊的默认成员函数

无参的默认构造函数

只需要构造出一个起哨兵作用的头结点即可

// 无参的默认构造函数
list()   
: _head(new Node)
, _head->_next(_head)
, _head->_prev(_head);
{}

拷贝构造函数

list的拷贝构造函数可以复用尾插实现。（尾插在后面会讲解，先用起来）

// 拷贝构造
list(const list<T>& lt)
: _head(new Node)
, _head->_next(_head)
, _head->_prev(_head);
{
for (const auto& e : lt)
{
push_back(e); // 复用尾插实现
}
}

赋值运算符重载函数

传统写法：释放赋值list的所有结点，然后复用尾插接口将被赋值list的所有结点尾插进来。

// 传统写法的赋值运算符重载函数
list<T>& operator=(const list<T>& lt)
{
if (this != &lt)
{
// 释放之前的所有结点
iterator it = begin();
while (it != end())
{
it = erase(it);
}

// 复用push_back尾插所有结点
for (const auto& e : lt)
{
push_back(e);
}
}

return *this;
}

现代写法：

现代写法依赖于交换函数，所以我们先实现交换两个list的函数，交换两个list只需要交换list中的 _head 指针即可。
在现代写法中，我们以传值传参的方式传递参数，此时的参数就相当于被赋值对象的一份临时拷贝，也就是复用拷贝构造函数，然后将当前对象与这个临时拷贝的对象进行交换。并且这个临时对象析构的时候，自动调用析构函数，析构的是赋值对象之前的值，避免了手动释放结点。

void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}

// 现代写法的赋值运算符重载函数
list<T>& operator=(const list<T> lt)
{
swap(lt);
return *this;
}

析构函数

list类涉及到资源的管理，析构函数需要显示给出，在析构的时候，需要逐个释放结点。

// 析构函数
~list()
{
    // 逐个释放节点
iterator it = begin();
while (it != end())
{
it = erase(it);
}
    
    // 释放哨兵位的头结点
delete _head;
_head = nullptr;
}

6.list类的插入操作

在指定位置之前插入：

// 在指定位置之前插入指定元素

iterator insert(iterator pos, const T& x)
{
// prev newnode cur
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);

// 连接prev和newnode
prev->_next = newnode;
newnode->_prev = prev;

// 连接newnode和cur
newnode->_next = cur;
cur->_prev = newnode;

return newnode;
}

尾插：在最后一个结点之后插入

// 尾插
void push_back(const T& x)
{
// head -> …… -> tail -> newnode ->head
Node* newnode = new Node(x);
Node* tail = _head->_prev;

// 连接tail和newnode
tail->_next = newnode;
newnode->_prev = tail;

// 连接newnode和head
newnode->_next = _head;
_head->_prev = newnode;
}

// 复用insert实现尾插
void push_back(const T& x)
{
insert(end(), x);
}

头插：复用insert在begin()之前插入。

// 头插
void push_front(const T& x)
{
insert(begin(), x);
}

7.list类的删除操作

删除指定位置的元素：

// 删除指定位置的元素
iterator erase(iterator pos)
{
assert(pos != end());

// prev cur next
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;

// 断开要删除结点和前后结点的连接
prev->_next = next;
next->_prev = prev;

// 释放要删除的结点
delete cur;

// 返回指向被删除结点的后一个结点的迭代器
return next;
}

复用erase实现尾删和头删：

尾删：end()的上一个位置就是尾结点。
头删：begin()就是第一个结点的位置。

// 尾删
void pop_back()
{
erase(--end());
}

// 头删
void pop_front()
{
erase(begin());
}

8.list.hpp源代码

#include <assert.h>

namespace xy
{
/* 定义节点 */
template<class T>       // T表示存储的数据的类型 
struct ListNode
{
ListNode<T>* _prev; // 指向前一个结点
ListNode<T>* _next; // 指向后一个结点
T _data;            // 存储数据

ListNode(const T& x = T()) // 构造函数
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};

/* 
* 迭代器
* T：存储的元素类型
* Ref：该类型的引用T&
* Ptr：该类型的指针T*
*/
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;

/* 成员变量 */
Node* _node; // 对结点的指针进行封装即可

/* 成员函数 */
__list_iterator(Node* x)
:_node(x)
{}

// ++it
self& operator++()        // 前置++，让当前迭代器指向下一个节点
{
_node = _node->_next;
return *this;         // 返回++以后的值
}

// it++
self operator++(int)      // 后置++，让当前迭代器指向下一个节点
{
//__list_iterator<T> tmp(*this);
self tmp(*this);

_node = _node->_next;

return tmp;           // 返回++之前的值
}

// --it
self& operator--()        // 前置--，让当前迭代器指向上一个节点
{
_node = _node->_prev;
return *this;         // 返回--之后的值
}

// it--
self operator--(int)      // 后置--，让当前迭代器指向上一个节点
{
self tmp(*this);

_node = _node->_prev; // 返回--之前的值

return tmp;
}

Ref operator*()           // 返回当前结点的数据域的引用
{
return _node->_data;
}

Ptr operator->()          // 返回当前结点中数据域的指针
{
return &(_node->_data);
}

bool operator!=(const self& s) // 判断两个迭代器是否不相等
{
return _node != s._node;
}

bool operator==(const self& s) // 判断两个迭代器是否相等
{
return _node == s._node;
}
};


template<class T> // T表示存储的数据的类型
class list
{
private:
typedef ListNode<T> Node; // 对结点类型重命名
Node* _head;              // 定义一个头结点
public:
/* 迭代器的声明 */
typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器

iterator begin()         // 返回第一个元素的迭代器
{
return _head->_next; // 利用单参数的构造函数进行隐式的类型转换
}

iterator end()    // 返回最后一个元素的后一个位置的迭代器
{
return _head; // 利用单参数的构造函数进行隐式的类型转换
}

const_iterator begin() const // 提供给const对象的begin
{
return _head->_next;
}

const_iterator end() const   // 提供给const对象的end
{
return _head;
}

/* 四个特殊的成员函数 */

// 无参的默认构造函数
list()   
: _head(new Node)
, _head->_next(_head)
, _head->_prev(_head);
{}

// 拷贝构造
list(const list<T>& lt)
: _head(new Node)
, _head->_next(_head)
, _head->_prev(_head);
{
for (const auto& e : lt)
{
push_back(e);
}
}

// 传统写法的赋值运算符重载函数
list<T>& operator=(const list<T>& lt)
{
if (this != &lt)
{
// 释放之前的所有结点
iterator it = begin();
while (it != end())
{
it = erase(it);
}

// 复用push_back尾插所有结点
for (const auto& e : lt)
{
push_back(e);
}
}

return *this;
}

void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}

// 现代写法的赋值运算符重载函数
list<T>& operator=(const list<T> lt)
{
swap(lt);
return *this;
}

// 析构函数
~list()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}

delete _head;
_head = nullptr;
}

/* 插入操作 */

// 在指定位置之前插入指定元素
iterator insert(iterator pos, const T& x)
{
// prev newnode cur
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);

// 连接prev和newnode
prev->_next = newnode;
newnode->_prev = prev;

// 连接newnode和cur
newnode->_next = cur;
cur->_prev = newnode;

return newnode;
}

// 尾插
void push_back(const T& x)
{
// head -> …… -> tail -> newnode ->head
Node* newnode = new Node(x);
Node* tail = _head->_prev;

// 连接tail和newnode
tail->_next = newnode;
newnode->_prev = tail;

// 连接newnode和head
newnode->_next = _head;
_head->_prev = newnode;
}

//void push_back(const T& x)
//{
//insert(end(), x);
//}

// 头插
void push_front(const T& x)
{
insert(begin(), x);
}

/* 删除操作 */

// 删除指定位置的元素
iterator erase(iterator pos)
{
assert(pos != end());

// prev cur next
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;

// 断开要删除结点和前后结点的连接
prev->_next = next;
next->_prev = prev;

// 释放要删除的结点
delete cur;

// 返回指向被删除结点的后一个结点的迭代器
return next;
}

// 尾删
void pop_back()
{
erase(--end());
}

// 头删
void pop_front()
{
erase(begin());
}
};
}

原文地址：https://blog.csdn.net/D5486789_/article/details/143833799

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Java LinkedList 详解
下一篇：深入解析动态代理：切点执行之前的方法代理是如何生成的？

【MySQL实战45讲笔记】基础篇——事务隔离
简单来说，**事务就是要保证一组数据库操作，要么全部成功，要么全部失败**。在 MySQL 中，事务支持是在**引擎层**实现的。但并不是所有的存储引擎都支持事务，比如MySQL 原生的 MyISAM
阅读更多2024-11-23
MySQL之索引与事务
介绍了MySQL索引的分类，索引的底层数据结构，聚簇索引与非聚簇索引，非聚簇索引导致的回表，索引失效的场景。介绍了事务的特性，事务的隔离级别。
阅读更多2024-11-23
15天大厂真题带刷day1
小美对偶数因子很感兴趣，她将进行 𝑇T 次询问，每次都会给出一个正整数 𝑥x，请你告诉她 𝑥x 是否存在至少一个偶数因子。在一行上输入一个整数 𝑥 (1≤𝑥≤109)x (1≤x≤109) 代表小美询
阅读更多2024-11-23
Fakelocation Server服务器/专业版 Windows11
任务一打开 PowerShell（以管理员身份）命令安装 Chocolatey。任务三打开Fakelocation开源文件 | 查看IP地址。任务四写入Hosts地址文件。任务二可能遇到的错误
阅读更多2024-11-23
Elasticsearch客户端在和集群连接时，如何选择特定的节点执行请求的？
Elasticsearch客户端在和集群连接时，如何选择特定的节点执行请求的？
阅读更多2024-11-23
muduo库的使用
muduo库的使用及其基本原理
阅读更多2024-11-23
Node基本使用
Node基本使用
阅读更多2024-11-23
11 —— 打包模式的应用
需求：在开发模式下想让webpack使用style-loader进行css样式的处理；让它把css代码内嵌在js中；在生产模式下提取css代码。mini-css-extract-plugin插件：提取
阅读更多2024-11-23
04_HDMI20协议解析_General_Control
当通过HDMI传输音频信号时，General_Control是必须要传输的数据包之一, 如果没有，可能会有部分显示器有兼容性问题；General_Control 可以打开或者关闭静音功能；
阅读更多2024-11-23
本地安装YAPI
项目中用到很多的RESTAPI，光靠人工管理或者普通文档肯定是不行的，翻了很多的RESTAPI管理工具，还是选择了YAPI，原因有2，一个是接口位于内网，外网网站上管理测试不到内网接口，另外一个是使用
阅读更多2024-11-23

模拟实现STL中的list

1.设计list的结点

2.设计list的迭代器

3.list类的设计总览

4.list类的迭代器操作

5.list类的四个特殊的默认成员函数

无参的默认构造函数

拷贝构造函数

赋值运算符重载函数

析构函数

6.list类的插入操作

7.list类的删除操作

8.list.hpp源代码

相关文章