一.list介绍
list底层是一个双向带头循环链表,这个我们以前用C语言模拟实现过,->双向带头循环链表
下面是list的文档介绍: list文档介绍
我们会根据 list 的文档来模拟实现 list 的增删查改及其它接口。
二.list模拟实现思路
既然是用C++模拟实现的,那么一定要封装在类里。
为了适合各种类型的数据,会使用模板。
节点 Node
了解双向循环带头链表的都知道,我们需要一个节点 (Node),之前用C语言实现的时候,我们写了一个叫做 BuynewNode 的函数来获取节点,而在C++里我们用类封装一个,注意这个用 struct 封装比较好,因为 struct 默认是公有的,这样方便我们访问,所以可以写一个类:
struct list_node
迭代器 iterator
我们知道,C++提供了一种统一的方式来访问容器,这就是迭代器,string 和 vector 的迭代器模拟实现很简单,因为 string 和 vector 底层是用数组实现的,数组是一段连续的物理空间,支持随机访问,所以它是天然的迭代器;
但是链表不一样,它不是一段连续的物理空间,不支持随机访问,所以想让 list 的迭代器在表面上和 string,vector 的迭代器用起来没有区别,我们在底层上就需要用类封装迭代器,然后再迭代器类的内部,重载 ++ -- * -> != == 这些迭代器会用到的运算符;
所以创建一个迭代器类:
struct list_iterator
const 迭代器 const_iterator
实现的普通的迭代器,还有 const 迭代器,const 迭代器的意思是让指针指向的内容不变,而指针本身可以改变,例如指针++,指针-- 这种操作,所以 const 迭代器与普通迭代器的不同只有 重载 * 运算符的返回值不同,它是 const T& (T是模板参数),重写一个const 迭代器类又显得太冗余,代码的可读性就降低了;
前面在学习模板时,我们知道不同的模板参数,编译器会生成不同的函数,所以我们选择加一个模板参数 :Ref 。这样只要在显示实例化模板参数时:
普通迭代器就传 T&;
const 迭代器就传 const T&;
-> 运算符重载
看下面这段代码:
using namespace std;
struct A
{
A(int a1,int a2)
:_a1(a1)
,_a2(a2)
{}
int _a1;
int _a2;
};
void test_list()
{
list<A> lt; //实例化自定义类型
lt.push_back(A(1, 1));
lt.push_back(A(2, 2));
lt.push_back(A(3, 3));
lt.push_back(A(4, 4));
list<A>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->_a1 << " " << it->_a2 << endl; //像指针一样访问自定义类型里的成员变量
it++;
}
}
int main()
{
test_list();
return 0;
}
有时候,实例化的模板参数是自定义类型,我们想要像指针一样访问访问自定义类型力的成员变量,这样显得更通俗易懂,所以就要重载 -> 运算符,它的返回值是 T* ,但是正常来说这里应该是这样访问的: it -> -> _a1
因为迭代器指向的是 整个自定义类型,要想再访问其内部成员应该再使用一次 -> (这个->就不是重载的 -> ,就是普通的 -> ),但是上面的代码为什么就写了一个 -> ,这个是C++语法把这里特殊化了。
那该怎么在迭代器类里重载 -> 运算符呢?
和const 迭代器一样,只需要再加一个模板参数 :Ptr
显示实例化的时候传 T* 就行了。
迭代器类 模拟实现源码: struct list_iterator
以上的都算 list 模拟实现的难点,其他的像 重载 ++ 什么的,对于学过数据结构的小伙伴们是非常简单的,就不赘述了,没学过的可以看看这篇文章:双向带头循环链表
template<class T,class Ref,class Ptr> //三个模板参数
struct list_iterator //封装迭代器
{
typedef list_node<T> Node; //重命名节点
typedef list_iterator<T, Ref, Ptr> self; //重命名迭代器类型
Node* _node;
list_iterator(Node*node) //构造函数,单参数的构造函数支持隐式类型转换
:_node(node)
{}
//重载 * ++ -- != == ->
Ref operator*() const
{
return _node->_val;
}
Ptr operator->() const
{
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->_prev;
return *this;
}
self operator--(int) //后置--
{
self tmp = *this;
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& lt) const
{
return _node != lt._node;
}
bool operator==(const self& lt) const
{
return _node == lt._node;
}
};
list
我们在用C语言实现双向带头循环链表时,会先初始化链表的头(head),即让它的 前驱指针(prev)和后继指针(next)都指向自己;
在C++的模拟实现 list 中,我们会创建一个类 list 来管理链表的节点并实现增删查改及其它接口,所以 list 的构建函数就是初始化 头(head)节点。
三.源码
list.h
我们可以模拟实现以上接口,具体函数的逻辑可以查阅文档,实现起来都是很简单的。
namespace nagi //把模拟实现list的类都放在一个命名空间里封装起来
{
template<class T>
struct list_node //创建节点
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node(const T& val = T()) //构造函数,初始化节点
:_prev(nullptr)
,_next(nullptr)
,_val(val)
{}
};
template<class T,class Ref,class Ptr> //三个模板参数
struct list_iterator //封装迭代器
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> self;
Node* _node;
list_iterator(Node*node) //构造函数,单参数的构造函数支持隐式类型转换
:_node(node)
{}
//重载 * ++ -- != == ->
Ref operator*() const
{
return _node->_val;
}
Ptr operator->() const
{
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->_prev;
return *this;
}
self operator--(int) //后置--
{
self tmp = *this;
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& lt) const
{
return _node != lt._node;
}
bool operator==(const self& lt) const
{
return _node == lt._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator; //重命名普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator; //重命名const迭代器
void empty_init() //因为构造函数和拷贝构造都会初始化头节点,所以就写成一个函数了
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_sz = 0;
}
list() //构造函数
{
empty_init();
}
//普通迭代器
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
//const迭代器
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
iterator insert(iterator pos, const T& x) //在pos之前插入
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
_sz++;
return newnode;
}
iterator erase(iterator pos) //删除pos位置,注意删除的时候不能把头节点也删了,所以要做pos检查
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_sz--;
return next; //库里规定返回删除节点的下一个节点
}
void push_back(const T& x) //尾插
{
insert(end(), x);
}
void push_front(const T& x) //头插
{
insert(begin(), x);
}
void pop_back() //尾删
{
erase(--end());
}
void pop_front() //头删
{
erase(begin());
}
void clear() //清楚除了头节点以外的所有节点
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
_sz = 0;
}
~list() //析构函数
{
clear();
delete _head;
_head = nullptr;
}
list(const list<T>& lt) //拷贝构造
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_sz, lt._sz);
}
list<T>& operator=(list<T> lt) //赋值重载
{
swap(lt);
return *this;
}
private:
Node* _head; //头节点
size_t _sz; //记录链表的长度
};
}
🐬🤖本篇文章到此就结束了, 若有错误或是建议的话,欢迎小伙伴们指出;🕊️👻
😄😆希望小伙伴们能支持支持博主啊,你们的支持对我很重要哦;🥰🤩
😍😁谢谢你的阅读。😸😼