C++初阶：适合新手的手撕list（模拟实现list）

🕗 发布于 2024-09-30 11:13 c++ list windows

1. 基本结构与文件规划

list.h头文件：包含类的全部(函数的声明与定义)

test.cpp源文件：进行调用test函数，测试和完善功能

基本结构：

#pragma once

namespace CH
{
//定义节点，采用struct，是因为struct的结构体是公有的
template <class T>
struct list_node
{
list_node<T>* _prve;
list_node<T>* _next;
T _val;

list_node(const T& val=T())
:_prve(nullptr)
,_next(nullptr)
,_val(val)
{
}

};


//迭代器
template <class T,class Ref,class Prt>
struct  list_iterator
{
typedef list_node<T> Node;//重命名
typedef list_iterator<T, Ref ,Prt> self;//重命名
Node* _node;//定义节点0

//构造函数
list_iterator(Node* node )//这里定义节点作为形参，因为在my_list中会传节点来初始化

Ref operator* ()//换成这个，如果调用的是const类型的，就返回const类型的，不是就返回正常类型的
Prt operator->()

//前置++
self& operator++()//返回迭代器类型

//后置++
self operator++(int)//返回迭代器类型

//前置--
self& operator--()

//后置--
self operator--(int)

bool operator!=(const self& it)

bool operator==(const self& it)
};


template <class T>
class my_list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T& ,T*> iterator;//如果不是const类型的就调用这个
typedef list_iterator<T, const T&,const T*> const_iterator;//是const类型的调这个

        //迭代器
iterator begin()//返回迭代器类型会调用迭代器的构造函数
iterator end()
const_iterator begin()const
const_iterator end()const

//初始化，并且创造一个头节点
void empty_init()

//构造函数
my_list()

//拷贝构造
my_list(const my_list<T>& lt)

//析构函数
~my_list()


//交换
void swap(my_list<T>& lt)

//"="
my_list& operator=(my_list<T> lt)

//全部删除
void clear()

//尾插
void push_back(const T& x)

//头插
void push_front(const T& x)

//尾删
void pop_back()

//头删
void pop_front()

//插入
iterator insert(iterator pos, const T& x)//返回删除之后下一个迭代器的位置

//删除
iterator erase(iterator pos)//返回删除之后下一个迭代器的位置

//记录节点个数
size_t size()

private:
Node* _head;//定义头节点
size_t _size;//记录节点的个数
};

};

list_node 结构体：

定义了链表的节点结构，包含了三个成员变量：前驱指针 _prev、后继指针 _next 和数据 _data。
构造函数初始化了这些成员变量，允许在创建节点时指定初始值。

my_list 类：

包含了迭代器的定义、构造函数、析构函数以及一系列的操作函数。
定义了两种迭代器类型：iterator 和 const_iterator，分别用于可修改的迭代和只读的迭代。
实现了一系列的操作函数

2. 默认函数

2.1 构造函数

我将私有变量初始化单独放在了一个函数中，以后初始化直接调用就行

//初始化
void empty_init()
{
_head = new Node;//开辟头节点，并且头节点不存数据
_head->_prve = _head;
_head->_next = _head;

_size = 0;
}

//空参构造函数
my_list()
{
empty_init();
}

//这也是一种构造函数
my_list(size_t n,const T& x=T())
{
    empty_init();
    for(size_t i=0;i<10;i++)
    {
         oush_back(x);
    }
}

//迭代器构造
template <class Iterator>//为什么使用模版：因为可能使用其他类型的迭代器来进行初始化
my_list(Iterator first, Iterator last)
{
    while (first != last)
    {
        push_back(*first);
        first++;
    }
}

2.2 拷贝构造

//拷贝构造
my_list(const my_list<T>& lt)
{
empty_init();
for (auto& x : lt)//这里用引用，因为自定义类型拷贝代价大
{
push_back(x);
}
}

2.3 析构函数

//析构函数
~my_list()
{
clear();
delete _head;
_head = nullptr;
}

3. 迭代器（iterator）(begin(),end())

这里为什么我们要把迭代器封装为一个类呢？明明之前模拟vector和string时，就直接typedef了

迭代器从某种程度来说也可以理解为是节点的地址，返回就是返回这个节点的地址

之前模拟vector和string时，二者底层都是连续的，想要到下一个可以直接++；想要得到里面的数据可以直接*。

但是现在对于list是不行的，我们就需要重载各种运算符，但是底层又是一个指针（内置类型）不能重载，现在就只能封装进一个类里，就能重载了

#pragma once
//#include<iostream>
//using namespace std;

namespace CH
{
//迭代器
template <class T,class Ref,class Prt>
struct  list_iterator
{
typedef list_node<T> Node;//重命名
typedef list_iterator<T, Ref ,Prt> self;//重命名
Node* _node;//定义节点0

//构造函数
list_iterator(Node* node )//这里定义节点作为形参，因为在my_list中会传节点来初始化
:_node(node)
{
}

Ref operator* ()//换成这个，如果调用的是const类型的，就返回const类型的，不是就返回正常类型的
{
return _node->_val;
}

Prt operator->()
{
return &_node->_val;
}

//前置++
self& operator++()//返回迭代器类型
{
_node = _node->_next;
return *this;
}
//后置++
self operator++(int)//返回迭代器类型
{
self tmp(*this);
            _node = _node->_next;
return tmp;
}

//前置--
self& operator--()
{
_node = _node->_prve;
return *this;
}

//后置--
self operator--(int)
{
self tmp(*this);
_node = _node->_prve;
return tmp;
}

bool operator!=(const self& it)
{
return _node != it._node;
}

bool operator==(const self& it)
{
return _node == it._node;
}

};

template <class T>
class my_list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T& ,T*> iterator;//如果不是const类型的就调用这个
typedef list_iterator<T, const T&,const T*> const_iterator;//是const类型的调这个


iterator begin()//返回迭代器类型会调用迭代器的构造函数
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
private:
Node* _head;//定义头节点
size_t _size;//记录节点的个数
};

};

4.增删改查

4.1 insert()

//插入
iterator insert(iterator pos, const T& x)//返回删除之后下一个迭代器的位置
{
Node* newnode = new Node(x);//在迭代器中找到这个位置的节点
Node* tmp = pos._node;
Node* prve = tmp->_prve;

prve->_next = newnode;
newnode->_prve = prve;

newnode->_next = tmp;
tmp->_prve = newnode;

++_size;

return newnode;
}

4.2 push_back()和push_front()

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

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

4.3 erase()

//删除
iterator erase(iterator pos)//返回删除之后下一个迭代器的位置
{
Node* tmp = pos._node;//在迭代器中找到这个位置的节点
Node* prve = tmp->_prve;
Node* next = tmp->_next;

prve->_next = next;
next->_prve = prve;

delete tmp;
--_size;

return next;
}

4.3 pop_back()和pop_front()

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

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

5. 其他函数

5.1 swap()和clear()

//交换
void swap(my_list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}

//全部删除
void clear()
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}

_size = 0;
}

5.2 size()和"="

//"="
my_list& operator=(my_list<T> lt)
{
swap(lt);
return *this;
}

//节点个数
size_t size()
{
return _size;
}

7. 全部代码

list.h

#pragma once

namespace CH
{
//定义节点，采用struct，是因为struct的结构体是公有的
template <class T>
struct list_node
{
list_node<T>* _prve;
list_node<T>* _next;
T _val;

list_node(const T& val=T())
:_prve(nullptr)
,_next(nullptr)
,_val(val)
{
}

};

//迭代器
template <class T,class Ref,class Prt>
struct  list_iterator
{
typedef list_node<T> Node;//重命名
typedef list_iterator<T, Ref ,Prt> self;//重命名
Node* _node;//定义节点0

//构造函数
list_iterator(Node* node )//这里定义节点作为形参，因为在my_list中会传节点来初始化
:_node(node)
{
}

Ref operator* ()//换成这个，如果调用的是const类型的，就返回const类型的，不是就返回正常类型的
{
return _node->_val;
}

Prt operator->()
{
return &_node->_val;
}

//前置++
self& operator++()//返回迭代器类型
{
_node = _node->_next;
return *this;
}
//后置++
self operator++(int)//返回迭代器类型
{
self tmp(*this);
            _node = _node->_next;
return tmp;
}

//前置--
self& operator--()
{
_node = _node->_prve;
return *this;
}

//后置--
self operator--(int)
{
self tmp(*this);
_node = _node->_prve;
return tmp;
}

bool operator!=(const self& it)
{
return _node != it._node;
}

bool operator==(const self& it)
{
return _node == it._node;
}

};

template <class T>
class my_list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T& ,T*> iterator;//如果不是const类型的就调用这个
typedef list_iterator<T, const T&,const T*> const_iterator;//是const类型的调这个

iterator begin()//返回迭代器类型会调用迭代器的构造函数
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}

//初始化
void empty_init()
{
_head = new Node;//开辟一个节点，并且头节点不存数据
_head->_prve = _head;
_head->_next = _head;

_size = 0;
}

//构造函数,并且创造一个头节点
my_list()
{
empty_init();
}

//拷贝构造
my_list(const my_list<T>& lt)
{
empty_init();
for (auto& x : lt)
{
push_back(x);
}
}

//析构函数
~my_list()
{
clear();
delete _head;
_head = nullptr;
}

//交换
void swap(my_list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}

//"="
my_list& operator=(my_list<T> lt)
{
swap(lt);
return *this;
}

//全部删除
void clear()
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}

_size = 0;
}

//尾插
void push_back(const T& x)
{
//Node* newnode = new Node(x);
//Node* tmp = _head->_prve;//找到头节点的前一个，也就是最后一个节点

//tmp->_next = newnode;
//newnode->_prve = tmp;

//newnode->_next = _head;
//_head->_prve = newnode;

//++_size;

insert(end(), x);
}

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

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

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

//插入
iterator insert(iterator pos, const T& x)//返回删除之后下一个迭代器的位置
{
Node* newnode = new Node(x);//在迭代器中找到这个位置的节点
Node* tmp = pos._node;
Node* prve = tmp->_prve;

prve->_next = newnode;
newnode->_prve = prve;

newnode->_next = tmp;
tmp->_prve = newnode;

++_size;

return newnode;
}

//删除
iterator erase(iterator pos)//返回删除之后下一个迭代器的位置
{
Node* tmp = pos._node;//在迭代器中找到这个位置的节点
Node* prve = tmp->_prve;
Node* next = tmp->_next;

prve->_next = next;
next->_prve = prve;

delete tmp;
--_size;

return next;
}

size_t size()
{
return _size;
}

private:
Node* _head;//定义头节点
size_t _size;//记录节点的个数
};
};

原文地址：https://blog.csdn.net/weixin_70067429/article/details/142450854

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

上一篇：ChatGPT的150个角色提示场景实测（9）讲故事
下一篇：基于SpringBoot实现QQ邮箱发送短信功能 | 免费短信服务

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30