list模拟实现【C++】
liuyunluoxiao 2024-07-17 12:35:01 阅读 92
文章目录
全部的实现代码放在了文章末尾准备工作包含头文件定义命名空间类的成员变量为什么节点类是用struct而不是class呢？为什么要写get_head_node?
迭代器迭代器在list类里的实例化和重命名普通迭代器operator->()的作用是什么？
const迭代器反向迭代器迭代器的获取
构造函数默认构造使用n个val构造迭代器区间构造解决迭代器区间构造 和 用n个val构造的冲突initializer_list构造拷贝构造
析构函数swap赋值运算符重载erase删除pos迭代器指向的节点为什么要返回next？
删除迭代器区间
insert在迭代器pos之前插入一个节点为什么要返回newnode?在迭代器pos之前插入一个迭代器区间的数据
push_backpush_frontpop_frontpop_backsizeemptybackfrontassignresizeclear全部代码
全部的实现代码放在了文章末尾
准备工作
创建两个文件，一个头文件<code>mylist.hpp，一个源文件test.cpp
【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件mylist.hpp中】
mylist.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义
test.cpp：存放main函数，以及测试代码
包含头文件
iostream：用于输入输出
assert.h：用于使用报错函数assert
定义命名空间
在文件mylist.hpp中定义上一个命名空间mylist
把list类和它的成员函数放进命名空间封装起来，防止与包含的头文件中的函数/变量重名的冲突问题
类的成员变量
参考了stl源码中的list的实现，stl中list的底层链表是双向带头循环链表
【可以看我这篇文章了解双向带头循环链表的实现：链表的极致——带头双向循环链表】
成员变量只有一个，就是指向双向带头循环链表的头节点的指针。
节点类：
为什么节点类是用struct而不是class呢？
因为节点类里面的成员变量在实现list的时候需要经常访问，所以需要节点类的成员变量是公有的【使用友元也可以，但是比较麻烦】
struct的默认访问权限就是公有，不用加访问限定符了，stl中实现的节点类也是struct
class的默认访问权限是私有的
list类：
为什么要写get_head_node?
因为插入节点之前<code>必须要有头节点
所以把创建初始头节点的操作写成了一个函数，用于
所有构造函数插入节点之前进行申请头节点
迭代器
因为list存储数据的方式是创建一个一个的节点存储数据
所以存储数据的空间不是连续的，所以不能直接用指针作为迭代器
因为指向一个节点的指针直接++,是不一定能指向下一个节点的
所以要把迭代器实现成一个类，这样才可以正确地支持++，- -，*等操作
迭代器在list类里的实例化和重命名
普通迭代器
<code>template<class T, class R, class F>
struct Iterator
{
把自己的类型重命名一下
typedef Iterator<T, R, F> Self;
成员变量的类型是 双向带头循环链表的节点类型
listnode<T>* _n;
Iterator(listnode<T>*l=nullptr) 构造函数
{
_n = l;
}
Self& operator++()前置++
{
++就是指向下一个节点
_n = _n->_next;
return *this;
}
Self operator++(int) 后置++
{
Self tmp =*this; 先记录一下++之前的值
_n = _n->_next; 再++
return tmp;
}
Self& operator--() 前置--
{
--就是指向上一个节点
_n = _n->_prev;
return *this;
}
Self operator--(int) 后置--
{
Self tmp = *this; 先记录一下--之前的值
_n = _n->_prev; 再--
return tmp;
}
R operator*()const
{
类比指针
*就是获取 节点中存储的数据
return _n->_data;
}
F operator->()const
{
返回 节点中 存储数据的成员变量的 地址
return &(_n->_data);
}
bool operator!=(const Self&obj)const
{
return _n != obj._n;
}
bool operator==(const Self& obj)
{
return !(*this != obj);
}
};
operator->()的作用是什么？
为了实现：
当节点中存储的数据是自定义类型的变量时，可以直接使用 迭代器->访问自定义类型中的成员
【原来访问需要调用两次->，为了可读性，省略了一个->】
例
const迭代器
const迭代器与普通迭代器的区别是什么？
区别就只有==<code>不能通过const迭代器改变节点中存储的数据==
转换一下就是：
不能使用迭代器的operator*()改变节点中存储的数据，即把operator*()的返回值改成const T&就可以了不能使用迭代器的operator->()改变节点中存储的数据的成员，即把operator->()的返回值改成const T*就可以了
所以const迭代器与普通迭代器的区别就只有两个函数的返回值类型不同，所以增加两个模板参数：R和F
普通迭代器实例化时:R就是T&，F就是T*
const迭代器实例化：R就是const T&，F就是const T*
反向迭代器
反向迭代器与普通迭代器的实现上的区别就是：
普通迭代器++是指向下一个节点
反向迭代器++是指向上一个节点
普通迭代器- -是指向上一个节点
反向迭代器- -是指向下一个节点
template<class T, class R, class F>
struct Reverse_iterator
{
把自己的类型重命名一下
typedef Reverse_iterator<T, R, F> Self;
成员变量的类型是 双向带头循环链表的节点类型
listnode<T>* _n;
Reverse_iterator(listnode<T>* l) 构造函数
{
_n = l;
}
Self& operator++()
{
反向迭代器++，是移动到 前 一个节点
_n = _n->_prev;
return *this;
}
Self operator++(int)
{
Self tmp = *this;
_n = _n->_prev;
return tmp;
}
Self& operator--()
{
反向迭代器--，是移动到 后 一个节点
_n = _n->_next;
return *this;
}
Self operator--(int)
{
Self tmp = *this;
_n = _n->_next;
return tmp;
}
R operator*()const
{
return _n->_data;
}
F operator->()const
{
return &(_n->_data) ;
}
bool operator!=(const Self& obj)const
{
return _n!=obj._n;
}
bool operator==(const Self& obj)const
{
return !(*this != obj);
}
};
迭代器的获取
iterator begin()
{
头节点的下一个节点 才是第一个节点
return _head->_next;
}
const修饰的对象只能调用const修饰的成员函数
const_iterator begin()const
{
头节点的下一个节点 才是第一个节点
return _head->_next;
}
iterator end()
{
最后一个节点的下一个节点是 头节点
因为是循环链表
return _head;
}
const修饰的对象只能调用const修饰的成员函数
const_iterator end()const
{
return _head;
}
reverse_iterator rend()
{
反向迭代器的rend返回的是第一个节点的 前一个节点
return _head;
}
const修饰的对象只能调用const修饰的成员函数
const_reverse_iterator rend()const
{
return _head;
}
reverse_iterator rbegin()
{
反向迭代器的rbegin()返回的是 最后一个节点
最后一个节点是 头节点的前一个
因为是循环链表
return _head->_prev;
}
const_reverse_iterator rbegin()const
{
return _head->_prev;
}
构造函数
默认构造
使用n个val构造
迭代器区间构造
解决迭代器区间构造 和 用n个val构造的冲突
当重载了<code>迭代器区间构造和使用n个val构造的时候
如果传入的两个参数都是int类型的话就会报错
为什么？
因为在模板函数构成重载时，编译器会调用更合适的那一个
什么叫更合适？
就是不会类型转
如果传入的两个参数都是int类型，那么调用的应该是使用n个值构造，因为没有int类型的迭代器
但是使用n个值构造的第一个参数是size_t , int传进去要隐式类型转换
而调用迭代器区间构造，两个int的实参传进去，就会直接把InputIterator推导成int，不会发生类型转换，所以编译器会调用迭代器区间构造
解决方法：
再重载一个使用n个值构造的函数，把第一个参数改成int，这样根据模板偏特化，就会在都不类型转换时优先调用第一个参数特化成int的那个构造函数
initializer_list构造
写了这个构造函数，就可以支持直接使用{}初始化了
例
<code>initializer_list是iostream库里面的自定义类型，它可以直接接收{ }里面的值 进行初始化，而且有迭代器
所以可以直接使用迭代器循环+尾插进行对list的构造
拷贝构造
析构函数
swap
只需要交两个list对象的<code>头指针中存储的地址就可以了
因为两个list对象都有头结点，交换了头指针中存储的地址，就相当于把这两个对象的头指针的指向交换了，
而链表的所有节点都是由头节点出发去找到的
<code>void swap(list& obj)
{
调用库里面的swap，交换头指针
std::swap(_head, obj._head);
}
赋值运算符重载
list& operator= (list obj)
{
swap(obj);
return *this;
}
为什么上面的两句代码就可以完成深拷贝呢？
这是因为：
使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去
赋值运算符的左操作数，*this再与传入的临时对象obj交换，就直接完成了拷贝
在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束
obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁
erase
删除pos迭代器指向的节点
为什么要返回next？
因为使用了erase之后的迭代器会失效，需要提供更新的方法
为什么使用了erase之后的迭代器会失效？
因为pos指向的节点erase之后，节点被释放了
stl库里面规定erase的返回值是<code>指向删除数据的下一个数据的迭代器，下一个数据就是next指向的数据，所以返回next【没有接收返回值的迭代器，在检测较严格的编译器中，不管指向的位置是否正确，都会禁止使用，使用了就报错】
删除迭代器区间
insert
在迭代器pos之前插入一个节点
为什么要返回newnode?
<code>list的迭代器pos在使用完insert之后其实是不会失效的
但是为了与其他容器的nsert的返回值进行统一，所以也返回了指向新插入的节点的迭代器
在迭代器pos之前插入一个迭代器区间的数据
push_back
复用insert即可
<code>void push_back(const T&val)
{
insert(end(), val);
}
push_front
复用insert即可
void push_front(const T& val)
{
insert(begin(), val);
}
pop_front
复用erese即可
void pop_front()
{
erase(begin());
}
pop_back
复用erese即可
void pop_back()
{
erase(--end());
}
size
empty
back
front
assign
resize
clear
复用erase
全部代码
#include<assert.h>
using namespace std;
namespace mylist
{
template<class T>
struct listnode//双向带头循环链表的节点类
{
T _data;//节点存储的数据
listnode* _next;//指向下一个节点的指针
listnode* _prev;//指向前一个节点的指针
};
template<class T, class R, class F>
struct Iterator
{
//把自己的类型重命名一下
typedef Iterator<T, R, F> Self;
//成员变量的类型是 双向带头循环链表的节点类型
listnode<T>* _n;
Iterator(listnode<T>*l=nullptr)//构造函数
{
_n = l;
}
Self& operator++()//前置++
{
//++就是指向下一个节点
_n = _n->_next;
return *this;
}
Self operator++(int)//后置++
{
Self tmp =*this;//先记录一下++之前的值
_n = _n->_next;//再++
return tmp;
}
Self& operator--()//前置--
{
//--就是指向上一个节点
_n = _n->_prev;
return *this;
}
Self operator--(int)//后置--
{
Self tmp = *this;//先记录一下--之前的值
_n = _n->_prev;//再--
return tmp;
}
R operator*()const
{
//类比指针
//*就是获取 节点中存储的数据
return _n->_data;
}
F operator->()const
{
//返回 节点中 存储数据的成员变量的 地址
return &(_n->_data);
}
bool operator!=(const Self&obj)const
{
return _n != obj._n;
}
bool operator==(const Self& obj)
{
return !(*this != obj);
}
};
template<class T, class R, class F>
struct Reverse_iterator
{
//把自己的类型重命名一下
typedef Reverse_iterator<T, R, F> Self;
//成员变量的类型是 双向带头循环链表的节点类型
listnode<T>* _n;
Reverse_iterator(listnode<T>* l)//构造函数
{
_n = l;
}
Self& operator++()
{
//反向迭代器++，是移动到 前 一个节点
_n = _n->_prev;
return *this;
}
Self operator++(int)
{
Self tmp = *this;
_n = _n->_prev;
return tmp;
}
Self& operator--()
{
//反向迭代器--，是移动到 后 一个节点
_n = _n->_next;
return *this;
}
Self operator--(int)
{
Self tmp = *this;
_n = _n->_next;
return tmp;
}
R operator*()const
{
return _n->_data;
}
F operator->()const
{
return &(_n->_data) ;
}
bool operator!=(const Self& obj)const
{
return _n!=obj._n;
}
bool operator==(const Self& obj)const
{
return !(*this != obj);
}
};
template<class T>
class list
{
//把双向带头循环链表的节点类型重命名成node
typedef listnode<T> node;
private:
node* _head;//唯一的成员变量
//获取初始头结点
node* get_head_node()
{
//申请一个节点大小的空间
node* tmp = new node;
//最开始的头节点的prev和next都指向自己
tmp->_next = tmp;
tmp->_prev = tmp;
return tmp;
}
public:
typedef Iterator<T, T&, T*> iterator;//普通迭代器
typedef Iterator<T, const T&, const T*> const_iterator;//const迭代器
typedef Reverse_iterator<T, T&, T*> reverse_iterator;//反向迭代器
typedef Reverse_iterator<T, const T&, const T*> const_reverse_iterator;//const反向迭代器
list()
{
//获取头结点
//为之后的插入操作做准备
_head=get_head_node();
}
list(size_t n, const T& val=T())
{
//必须先获取头节点，才能进行插入数据
_head = get_head_node();
for (int i = 0; i < n; i++)
{
push_back(val);//尾插n次
}
}
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
//必须先获取头节点，才能进行插入数据
_head = get_head_node();
while (first != last)
{
//把解引用之后的值，一个一个尾插进去
push_back(*first);
first++;
}
}
list(int n, const T& val = T())
{
//必须先获取头节点，才能进行插入数据
_head = get_head_node();
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
list(initializer_list<T> il)
{
//必须先获取头节点，才能进行插入数据
_head = get_head_node();
auto it = il.begin();
while (it != il.end())
{
//把解引用之后的值，一个一个尾插进去
push_back(*it);
it++;
}
}
list(const list& obj)
{
//必须先获取头节点，才能进行插入数据
_head = get_head_node();
//使用const迭代器接收 const修饰的对象的迭代器
const_iterator it = obj.begin();
while (it != obj.end())
{
//把解引用之后的获得的值，一个一个尾插进去
push_back(*it);
it++;
}
}
~list()
{
//先把list里面除了头结点
//以外的节点全部删除
clear();
//再把头结点申请的空间释放
delete _head;
_head = nullptr;
}
list& operator= (list obj)
{
swap(obj);
return *this;
}
void swap(list& obj)
{
//调用库里面的swap，交换头指针
std::swap(_head, obj._head);
}
iterator begin()
{
//头节点的下一个节点 才是第一个节点
return _head->_next;
}
//const修饰的对象只能调用const修饰的成员函数
const_iterator begin()const
{
//头节点的下一个节点 才是第一个节点
return _head->_next;
}
iterator end()
{
//最后一个节点的下一个节点是 头节点
//因为是循环链表
return _head;
}
//const修饰的对象只能调用const修饰的成员函数
const_iterator end()const
{
return _head;
}
reverse_iterator rend()
{
//反向迭代器的rend返回的是第一个节点的 前一个节点
return _head;
}
//const修饰的对象只能调用const修饰的成员函数
const_reverse_iterator rend()const
{
return _head;
}
reverse_iterator rbegin()
{
//反向迭代器的rbegin()返回的是 最后一个节点
//最后一个节点是 头节点的前一个
//因为是循环链表
return _head->_prev;
}
const_reverse_iterator rbegin()const
{
return _head->_prev;
}
void push_back(const T&val)
{
/*node* tail = _head->_prev;
node* newnode = new node;
newnode->_data = val;
newnode->_next = _head;
newnode->_prev = tail;
tail->_next = newnode;
_head->_prev = newnode;*/
insert(end(), val);
}
iterator erase(iterator pos)
{
//不能 把 头节点 给删了
assert(pos!=end());
//记录pos的前一个节点（prev）
// 和后一个节点（next）
node* prev = pos._n->_prev;
node* next = pos._n->_next;
//让prev的下一个节点变成next
prev->_next = next;
//让prev的上一个节点变成next
next->_prev = prev;
//释放pos指向的节点
delete pos._n;
//返回被删除的节点的下一个节点
//用于更新迭代器
return next;
}
iterator erase(iterator first, iterator last)
{
iterator it = first;
while (it != last)
{
//删除it指向的节点
//删除后让it接收返回值，进行更新
it = erase(it);
}
//返回被删除的 最后一个节点 的下一个节点
//用于更新迭代器
return last;
}
bool empty() const
{
//size==0就 是空 返回true
//size!=0就 不是空 返回false
return size() ==0 ;
}
size_t size()const
{
//用count记录节点个数
size_t count = 0;
//使用const迭代器接收 const修饰的对象的迭代器
const_iterator it = begin();
//遍历链表
while (it != end())
{
count++;
++it;
}
return count;
}
T& back()
{
//list不能为空，为空就报错
assert(!empty());
//end（）返回的迭代器指向 头结点
//头结点的上一个节点就是，最后一个节点
//因为是循环链表
return *(--end());
}
//const修饰的成员，只能调用const修饰的成员函数
const T& back() const
{
assert(!empty());
return *(--end());
}
T& front()
{
//list不能为空，为空就报错
assert(!empty());
//begin()返回的迭代器 就指向第一个节点
return *begin();
}
//const修饰的成员，只能调用const修饰的成员函数
const T& front()const
{
assert(!empty());
return *begin();
}
template <class InputIterator>
void assign(InputIterator first, InputIterator last)
{
//先把数据现有的节点(除了头结点)都删除
clear();
//再循环把数据一个一个尾插进去
while (first != last)
{
//尾插
push_back(*first);
first++;
}
}
void assign(size_t n, const T& val)
{
clear();
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
void assign(int n, const T& val)
{
clear();
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
iterator insert(iterator pos, const T& val)
{
//记录指向 pos 前一个节点的指针
node* prev = pos._n->_prev;
//申请新节点的空间
node* newnode = new node;
//存储数据
newnode->_data = val;
newnode->_next = pos._n;
newnode->_prev = prev;
prev->_next = newnode;
pos._n->_prev = newnode;
//返回指向新插入的节点的迭代器
//用于更新迭代器
return newnode;
}
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)
{
while (first!=last)
{
//循环插入即可
//因为list的迭代器使用完insert之后 不会失效
//所以不用接收返回值 也可以
insert(pos,*first);
first++;
}
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
void resize(size_t n, const T& val = T())
{
//获取一下size，加快后续比较效率
//因为获取size()的时间复杂度为 O(N)
size_t size = this->size();
if (n > size)
{
//缺失的数据用val填上
//填到size()==n为止
while (size < n)
{
push_back(val);
++size;
}
}
else
{
//把多出来的数据（节点）删除
//删除到n==size()为止
while (n < size)
{
pop_back();
n++;
}
}
}
void clear()
{
//[begin(),end())之间的数据
//就是所有的有效数据(节点)
//复用erase删除即可
erase(begin(), end());
}
};
}
上一篇： Warning: apt-key is deprecated. Manage keyring files in trusted.gpg.d instead (see apt-key(8))
本文标签
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。