【C++】list底层的模拟实现
个人主页
文章目录
- 🎄一、前言
- 🏠二、基本框架
- 🎡三、list节点类的实现
- 🎉四、list迭代器类
- 1.Ref operator*()
- 2.Ptr operator->()
- 3.Self& operator++()前置和Self& operator--()前置
- 4.Self operator++(int)后置和Self operator--(int)后置
- 5.bool operator!=(const Self& s) const和bool operator==(const Self& s) const
- ⭐五、list类
- 1.初始化
- 2.构造函数
- 4.析构函数和clear函数
- 5.深拷贝
- 6.深赋值
- 7.头插和头删函数
- 8.尾插和尾删函数
- 9.insert和erase函数
- 10.迭代器的实现（普通和const)
- 11.判空
- 12.size()函数
- 🚀六、vector和list函数的区别
- 🏝️七、源代码
🎄一、前言
list是一个双向链表的容器，它可以在其内部中存储各种类型的元素，并且支持动态地添加、删除和修改元素。
🏠二、基本框架
list可以分为三部分：一个是list节点类，一个是迭代器类，还有一个是list类本身。
它们三个类底层的成员变量又分别代表不同的功能。
其中list节点类封装了list的元素以及前后指针，且完成了节点的初始化。
迭代器类封装了指向节点的指针，还负责重载++、–等运算符。
list类本身负责初始化以及负责插入和删除等功能。
🎡三、list节点类的实现
链表中数据以及前后指针的类型都是由模板自动生成的，可以为内置类型或自定义类型。
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
//构造
list_node(const T& data = T())
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{};
};
🎉四、list迭代器类
因为迭代器涉及普通迭代器和const迭代器，因此我们可以使用模板，在模板里面设置三个不同的类型，分别为节点的数据类型、引用类型和指针类型。
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
//用来访问Node类型的成员变量
Node* _node;
};
迭代器的默认构造函数因为支持基本的隐式类型转换，因此实现起来也很简单。
list_iterator(Node* node)
:_node(node)
{}
1.Ref operator*()
负责重载迭代器的解引用，直接返回当前该迭代器指向的节点数据即可。
Ref operator*()
{
return _node->_data;
}
2.Ptr operator->()
由于我们想把迭代器当成指针使用，因此重载->是必要的，其返回值为节点元素的地址。为什么是返回地址呢？这是因为在使用迭代器->时，编译器会自动优化成->->。
Ptr operator->()
{
return &_node->_data;
}
3.Self& operator++()前置和Self& operator–()前置
直接让节点指向下一个和前一个即可。
//前置++
Self& operator++()
{
_node = _node->_next;
return *this;
}
//前置--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
4.Self operator++(int)后置和Self operator–(int)后置
我们只需把当前迭代器实例化的对象拷贝给一个新的迭代器对象tmp，然后把当前的数据进行处理，最后将tmp进行返回即可。
//后置++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
//后置--
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
5.bool operator!=(const Self& s) const和bool operator==(const Self& s) const
判断节点是否相等不能只判断值是否相等，因为不同的节点可以存放相同的值，因此需要比较其节点是否相等即可。
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
⭐五、list类
1.初始化
初始化只需初始化头结点即可。
//无参初始化
list()
{
//通过调用这一函数来创建头节点
empty_init();
}
//空初始化
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
2.构造函数
当链表为空时，_head节点的头和尾都指向它自己，因此在后续有节点插入时，只需改变一下prev和next指向的位置即可。
list()
{
_head = new Node<T>();
_head->next = _head;
_head->prev = _head;
}
4.析构函数和clear函数
析构函数是用来释放节点空间的，因此需要先定义一个clear函数用来释放所有的有效节点，确保没有有效节点后再把哨兵位的_head进行删除，然后将_head置为空。
//析构
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
5.深拷贝
先对其进行空初始化操作，然后用迭代器依次对其进行访问然后插入即可。
//深拷贝
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
6.深赋值
我们可以调用swap函数将两者数据进行交换即可。
//深赋值
void swap(list<int>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
7.头插和头删函数
头插函数就是每次在begin位置之前进行插入，因为begin是第一个有效的元素；而头删就是每次在begin位置进行删除。
void push_front(const T& x)
{
Insert(begin(), x);
}
void pop_front()
{
erase(--begin());
8.尾插和尾删函数
尾插就是每次在end()位置进行插入，因为end是最后一个有效的元素；而尾删则是在end()的位置上进行删除。
由于我们实现了insert函数，因此就可以调用insert函数在其尾部插入数据即可。
void push_back(const T& x)
{
Insert(end(), x);
++_size;
}
void pop_back()
{
erase(--end());
}
9.insert和erase函数
insert函数就是在pos位置插入值。
iterator Insert(iterator pos, const T& x)
{
//取到pos位置的节点
Node* cur = pos._node;
//保留之前的节点
Node* prev = cur->_prev;
//创建新节点
Node* newnode = new Node(x);
//改变指向，最后更新一下_size
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
return newnode;
}
erase函数首先要进行断言，防止删除哨兵位。然后将pos位置节点的前和后进行连接，最后删除pos位置的节点，更新一下_size的大小。
iterator erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}
10.迭代器的实现（普通和const)
由于存在普通成员变量和const成员变量的调用，因此需要实现两个迭代器。
begin迭代器是返回第一个有效位置，由于哨兵位_head并没有数据，因此返回哨兵位的下一个位置。end迭代器是返回最后一个元素的下一个位置，而这个位置是无效的，双向链表无效的位置就只有哨兵位这一个位置，因此返回哨兵位即可。
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
//const迭代器
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
11.判空
直接判断_size是否为空即可。
//判空
bool empty() const
{
return _size == 0;
}
12.size()函数
直接返回_size即可。
size_t size() const
{
return _size;
}
🚀六、vector和list函数的区别
首先，vector是一个动态数组，在插入和删除数据的时候会挪动后面的元素，这就有可能会导致迭代器失效；而list则为链表，它可以在任意位置进行插入和删除，因此迭代器的稳定性就更高。
其次，vector的迭代器通常为随机访问迭代器，允许向前向后访问元素，而list迭代器可能为双向迭代器，只能向前或向后移动。
最后，vector的随机访问速度快，因此在查找元素时的效率高，但如果频繁的插入或者删除元素时，list通常会更快，因为它不需要移动大量的元素。
🏝️七、源代码
#include<iostream>
#include<assert.h>
#include<list>
using namespace std;
namespace bit
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
//构造
list_node(const T& data = T())
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{};
};
//const迭代器
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*()
{
return _node->_data;
}
Ptr 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;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._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;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
//const迭代器
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
//空初始化
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//无参初始化
list()
{
empty_init();
}
//析构
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
//深拷贝
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//深赋值
void swap(list<int>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
size_t size() const
{
return _size;
}
void push_back(const T& x)
{
Insert(end(), x);
++_size;
}
iterator Insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
return newnode;
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(--begin());
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}
void push_front(const T& x)
{
Insert(begin(), x);
}
//判空
bool empty() const
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
}