【C++】深入剖析list

news/2025/3/19 20:55:42/

本期我们来深入list的实现原理:

目录

一、STL中的list

二、list的模拟实现

2.1 搭建list的框架

2.2 list迭代器的实现

2.2.1 普通迭代器的实现

2.2.2 const类型迭代器的实现 

2.2.3 迭代器中->运算符重载实现

2.3 其他功能函数的实现

2.3.1 insert

2.3.2 erase

2.3.3 clean

2.3.4 析构函数

2.3.5 迭代器区间构造函数

2.3.6 拷贝构造函数

2.3.7 operator=

三、模拟实现list完整代码


一、STL中的list

我们先来看看在STL中是怎么定义list中的节点的:

template <class T>
struct __list_node {typedef void* void_pointer;void_pointer next;void_pointer prev;T data;
};

我们可以看到定义该节点时用的是struct关键字而不是class,这是因为在STL标准库想要开放节点中的指针供编译人员访问。

下面是对于list这个类的定义:

template <class T, class Alloc = alloc>
class list {
protected:typedef void* void_pointer;typedef __list_node<T> list_node;typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:      typedef T value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef list_node* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;public:typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;
}

剩下的源码我们就不过多解释,下面开始模拟实现:

二、list的模拟实现

2.1 搭建list的框架

我们先来简单写一写list的简单主要功能,搭建一个框架:

namespace lhs
{template<class T>struct _list_node{_list_node<T>* _prev;_list_node<T>* _next;T _data;//构造函数_list_node(const T& val = T()):_prev(nullptr),_next(nullptr),_data(val){}};template<class T>class list{public:typedef _list_node<T> node;//构造函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//尾插void push_back(const T& val){node* newnode = new node(val);newnode->_next = _head;newnode->_prev = _head->_prev;_head->_prev->_next = newnode;_head->_prev = newnode;}//头插void push_front(const T& val){node* newnode = new node(val);newnode->_next = _head->_next;newnode->_prev = _head;_head->_next->_prev = newnode;_head->_next = newnode;}private:node* _head;};
}

上面对于可以熟练运用带头双向循环链表的我们来说就是小菜一碟~

2.2 list迭代器的实现

2.2.1 普通迭代器的实现

我们在string和vector中实现迭代器十分的容易,因为它们的存储空间物理上都是连续的,我们可以对重命名的迭代器++即可。但是在list中就不可能了,因为基于链表实现的list存储空间并非是连续的。所以想要实现list中的迭代器要自定义另一个类型进行运算符重载:

template<class T>
struct __list_iterator
{typedef _list_node<T> node;typedef __list_iterator<T> self;node* _node;//构造函数__list_iterator(node* t):_node(t){}//运算符重载T& operator*(){return _node->_data;}self& operator++()//前置++{_node = _node->_next;return *this;}self& operator++(int)//后置++{self tmp(*this);//保存++之前的数据_node = _node->_next;return tmp;}self& operator--()//前置--{_node = _node->_prev;return *this;}self& operator--(int)//后置--{self tmp(*this);//保存++之前的数据_node = _node->_prev;return tmp;}self& operator-(size_t n){for (size_t i = 0; i < n; ++i){_node = _node->_prev;}return *this;}self& operator+(size_t n){for (size_t i = 0; i < n; ++i){_node = _node->_next;}return *this;}bool operator!=(self n){return _node != n._node;}bool operator==(self n){return _node == n._node;}
};

有了这个自定义类,我们直接将list中的节点传入该类型让其进行运算符重载即可:

template<class T>
class list
{
public:typedef _list_node<T> node;//构造函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//迭代器typedef __list_iterator<T> iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}
private:node* _head;
};

2.2.2 const类型迭代器的实现 

但是对于const成员呢?我们可以像下面代码一样构建一个const版本的迭代器:

但是这个const迭代器和普通迭代器的唯一区别只在于重载*运行时的返回值不同,如果这样子写会造成代码的冗余

下面我们可以在自定义实现的迭代器里多加入一个模版参数Ref,来判断list调用迭代器时传入的是否是const类型的节点:

template<class T, class Ref>//增加一个Ref模版参数来判断调用的是什么类型的迭代器
struct __list_iterator
{typedef _list_node<T> node;typedef __list_iterator<T, Ref> self;node* _node;//构造函数__list_iterator(node* t):_node(t){}//运算符重载Ref operator*()//通过第二个模版参数确定是不是const类型的返回值{return _node->_data;}
};template<class T>
class list
{
public:typedef _list_node<T> node;//构造函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//迭代器typedef __list_iterator<T, T&> iterator;//第二个模版参数传入T&调用普通迭代器typedef __list_iterator<T, const T&> const_iterator;//第二个模版参数传入const T&调用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;
};

2.2.3 迭代器中->运算符重载实现

如果list中存的是自定义类型的数据我们难免会用到->来访问具体数据

例如:

struct A
{int _a1;int _a2;
};
void test2()
{list<A> l;A a = { 7,8 };l.push_back(a);l.push_back(a);l.push_back(a);list<A>::iterator it = l.begin();while (it != l.end()){std::cout << (*it)._a1 << "," << (*it)._a2 << std::endl;++it;}std::cout << std::endl;
}

在上述代码中,我们想要对list中的A类型自定义变量具体成员进行访问,需要对迭代器*操作之后再加上.

这样十分的奇怪,不方便我们具体操作,所以下面我们来重载->操作符:

template<class T,class Ref>
struct __list_iterator
{typedef _list_node<T> node;typedef __list_iterator<T, Ref> self;node* _node;//构造函数__list_iterator(node* t):_node(t){}//运算符重载T* operator->(){return &(_node->_data);}
}

下面我们就可以使用->来访自定义类型的内部成员了:

void test2()
{list<A> l;A a = { 7,8 };l.push_back(a);l.push_back(a);l.push_back(a);list<A>::iterator it = l.begin();while (it != l.end()){std::cout << it->_a1 << "," << it->_a2 << std::endl;++it;}std::cout << std::endl;
}

不过上面测试代码奇怪的是:it后面加上->构成运算符重载,该运算符返回的是T*类型的地址所以后面还要加上->才能指向所要访问的成员变量才对啊,所以不应该是it->->_a1才对吗?

这是由于编译器对代码的优化,让我们可以少写一个->就可以直接访问到成员变量了,看起来更直观。

但是下面又出现了一个问题:如果我们使用const类型的迭代器返回的应该是const T*类型才对,那我们可以模仿之前const类型迭代器的实现,再加一个模版参数Ptr来判断传入的类型是否为const:

template<class T, class Ref, class Ptr>//增加两个Ref和Ptr模版参数来判断传入数据的类型
struct __list_iterator
{typedef _list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;//构造函数__list_iterator(node* t):_node(t){}//运算符重载Ref operator*()//通过第二个模版参数确定是不是const类型的返回值{return _node->_data;}Ptr operator->()//通过第三个模版参数确定是不是const类型的返回值{return &(_node->_data);}
};template<class T>
class list
{
public:typedef _list_node<T> node;//构造函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//迭代器typedef __list_iterator<T, T&, T*> iterator;//第二和第三个模版参数传入T&和T*调用普通迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;//第二和第三个模版参数传入const T&和const T*调用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;
};

 

2.3 其他功能函数的实现

我们有了迭代器就好实现其各种函数了:

2.3.1 insert

//任意位置前插入数据
void insert(iterator pos, const T& val)
{node* newnode = new node(val);newnode->_next = pos._node;newnode->_prev = pos._node->_prev;pos._node->_prev->_next = newnode;pos._node->_prev = newnode;
}

有了insert函数,我们刚开始搭建的push_back和push_front函数就可以直接复用了:

//尾插
void push_back(const T& val)
{insert(end(), val);
}
//头插
void push_front(const T& val)
{insert(begin(), val);
}

 

2.3.2 erase

void erase(iterator pos)
{assert(pos != end());//避免删除头节点pos._node->_prev->_next = pos._node->_next;pos._node->_next->_prev = pos._node->_prev;delete pos._node;
}

要注意了,使用erase函数后传入的迭代器会失效,因为其指向的空间会被释放。所以我们最好将erase这个函数设置一个返回值来进行修正:

iterator erase(iterator pos)
{assert(pos != end());node* next = pos._node->_next;pos._node->_prev->_next = pos._node->_next;pos._node->_next->_prev = pos._node->_prev;delete pos._node;return iterator(next);
}

有了erase函数,头删和尾删我们信手拈来:

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

2.3.3 clean

//删除所有有效数据
void clean()
{iterator it = begin();while (it != end()){it = erase(it);}
}

2.3.4 析构函数

//析构
~list()
{clean();delete _head;_head = nullptr;
}

2.3.5 迭代器区间构造函数

template<class InputIterato>
list(InputIterato begin, InputIterato end)//迭代器区间构造
{_head = new node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}
}

2.3.6 拷贝构造函数

list(const list<T>& val)
{_head = new node;_head->_next = _head;_head->_prev = _head;const_iterator it = val.begin();while (it != val.end()){push_back(*it);++it;}
}

上面代码是一个比较传统的写法,下面我们可以先复用迭代器区间构造函数创建一个临时对象,再构建一个swap函数来交换this的头节点和临时对象的头节点即可:

void swap(list<T>& l)//交换
{node* tmp = _head;_head = l._head;l._head = tmp;
}
list(const list<T>& val)
{_head = new node;_head->_next = _head;_head->_prev = _head;list<T> tmp(val.begin(), val.end());//创建临时对象swap(tmp);//交换数据使this的头节点窃取临时对象的成果
}

2.3.7 operator=

list<T>& operator=(list<T> val)//这里传参没有使用&是为了防止对val数据的破坏
{swap(val);return *this;
}

注意上述代码传参使用&是为了让形参拷贝构造实参,防止swap函数将实参的数据进行交换

三、模拟实现list完整代码

#include<iostream>
#include<assert.h>
namespace lhs
{template<class T>struct _list_node{_list_node<T>* _prev;_list_node<T>* _next;T _data;//构造函数_list_node(const T& val = T()):_prev(nullptr),_next(nullptr),_data(val){}};template<class T,class Ref,class Ptr>//增加两个Ref和Ptr模版参数来判断传入数据的类型struct __list_iterator{typedef _list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;//构造函数__list_iterator(node* t):_node(t) {}//运算符重载Ref operator*()//通过第二个模版参数确定是不是const类型的返回值{return _node->_data;}Ptr operator->()//通过第三个模版参数确定是不是const类型的返回值{return &(_node->_data);}self& operator++()//前置++{_node = _node->_next;return *this;}self& operator++(int)//后置++{self tmp(*this);//保存++之前的数据_node = _node->_next;return tmp;}self& operator--()//前置--{_node = _node->_prev;return *this;}self& operator--(int)//后置--{self tmp(*this);//保存++之前的数据_node = _node->_prev;return tmp;}self& operator-(size_t n){for (size_t i = 0; i < n; ++i){_node = _node->_prev;}return *this;}self& operator+(size_t n){for (size_t i = 0; i < n; ++i){_node = _node->_next;}return *this;}bool operator!=(self n){return _node != n._node;}bool operator==(self n){return _node == n._node;}};template<class T>class list{public:typedef _list_node<T> node;//构造函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}template<class InputIterato>list(InputIterato begin, InputIterato end)//迭代器区间构造{_head = new node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}}void swap(list<T>& l)//交换{node* tmp = _head;_head = l._head;l._head = tmp;}list(const list<T>& val){_head = new node;_head->_next = _head;_head->_prev = _head;list<T> tmp(val.begin(), val.end());//创建临时对象swap(tmp);//交换数据使this的头节点窃取临时对象的成果}//运算符重载list<T>& operator=(list<T> val)//这里传参没有使用&是为了防止对val数据的破坏{swap(val);return *this;}//尾插void push_back(const T& val){insert(end(), val);}//头插void push_front(const T& val){insert(begin(), val);}//迭代器typedef __list_iterator<T, T&, T*> iterator;//第二和第三个模版参数传入T&和T*调用普通迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;//第二和第三个模版参数传入const T&和const T*调用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 insert(iterator pos, const T& val){node* newnode = new node(val);newnode->_next = pos._node;newnode->_prev = pos._node->_prev;pos._node->_prev->_next = newnode;pos._node->_prev = newnode;}//删除任意位置的元素iterator erase(iterator pos){assert(pos != end());node* next = pos._node->_next;pos._node->_prev->_next = pos._node->_next;pos._node->_next->_prev = pos._node->_prev;delete pos._node;return iterator(next);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}//删除所有有效数据void clean(){iterator it = begin();while (it != end()){it = erase(it);}}//析构~list(){clean();delete _head;_head = nullptr;}private:node* _head;};
}

本期到这里又要结束了,感谢各位的阅览~

我们下期见~


http://www.ppmy.cn/news/980997.html

相关文章

【论文阅读】A Comprehensive Survey

论文来源&#xff1a;Li M , Liu Y , Liu X ,et al.The Deep Learning Compiler: A Comprehensive Survey[J]. 2020.DOI:10.1109/TPDS.2020.3030548. 这是一篇关于深度学习编译器的综述类文章。 什么是深度学习编译器 深度学习&#xff08;Deep Learning&#xff09;编译器将…

在nginx上部署nuxt项目

先安装Node.js 我安的18.17.0。 安装完成后&#xff0c;可以使用cmd&#xff0c;winr然cmd进入&#xff0c;测试是否安装成功。安装在哪个盘都可以测试。 测试 输入node -v 和 npm -v&#xff0c;&#xff08;中间有空格&#xff09;出现下图版本提示就是完成了NodeJS的安装…

Scaling Instruction-Finetuned Language Models

Paper name Scaling Instruction-Finetuned Language Models Paper Reading Note Paper URL: https://arxiv.org/pdf/2210.11416.pdf TL;DR 2022 年谷歌出的文章&#xff0c;对指令微调的影响因素进行分析&#xff0c;提出了一些提升指令微调效果的方案。与该文章一起出品…

时序预测 | MATLAB实现BiLSTM时间序列未来多步预测

基本介绍 双向LSTM或biLSTMQ是一种序列处理模型,由两个LSTM组成:一个在前向接收输入,另个在后向接收输入。BiLSTMs有效地增加了网络可用的信息量。利用LSTM对句子进行建模还存在一个问题:无法编码从后到前的信息。在更细粒度的特征挖掘时缺乏能力,通过BiLSTM可以更好的捕…

最全SWAT教程:SWAT模型系统学习(建模方法、实例应用、高级进阶)

目前&#xff0c;水环境问题逐渐成为制约社会经济和环境可持续发展的重要因素。根据国内外研究表明&#xff0c;受全球环境变化和经济快速发展的影响&#xff0c;面源污染已逐渐成为水环境污染的第一因素。但面源污染由于具有排放分散、隐蔽&#xff0c;排污随机、不确定、不易…

opencv-19 图像色彩空间转换函数cv2.cvtColor()

cv2.cvtColor() 函数是 OpenCV 中用于图像颜色空间转换的函数。它允许你将图像从一个色彩空间转换为另一个色彩空间。在 Python 中&#xff0c;你可以使用这个函数来实现不同色彩空间之间的转换。 函数的基本语法为&#xff1a; cv2.cvtColor(src, code[, dst[, dstCn]])参数…

存储简单了解

存储目前常用的有磁盘&#xff08;磁性存储器&#xff09;和固态硬盘&#xff08;半导体存储器&#xff09; 磁盘由盘片&#xff0c;磁头和移动磁头的机械装置组成。磁盘从空间结构上分为扇区和磁道&#xff0c;每个扇区存储大小一致。 固态硬盘由多个闪存芯片组成&#xff0c;…

自然语言处理NLP介绍——NLP简介

目录 内容先进性说明内容大纲概要云服务器的使用 内容先进性说明 内容大纲概要 云服务器的使用