C++——list模拟实现
目录
前言
一、list的结构
二、默认成员函数
构造函数
析构函数
clear
拷贝构造
赋值重载
swap
三、容量相关
empty
size
四、数据访问
front/back
五、普通迭代器
begin/end
六、const迭代器
begin/end
七、插入数据
insert
push_back
push_front
八、删除数据
erase
pop_back
pop_front
九、代码
总结
前言
我们之前讲解了string和vector的模拟实现，它们都是类似于顺序表的结构，string的底层是一个指针，一个元素的数量，一个空间总容量，而vector的底层是三个指针，这是它们结构上不一样的地方，但是实现的方法和原理还是大差不差的，那本篇我们来谈谈list，list的迭代器和之前的容器是不一样的，而且是一个双向带头循环链表，任意位置的插入删除效率都是O(1)，那我们开始正题
一、list的结构
list的结构是一个一个的节点，所以我们在定义的时候就要去定义一个节点
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
};_prev指向前一个节点
_next指向下一个节点
_val表示节点中存储的值
list_node这个类可以写成class，然后放成公有，也可以直接定义成struct的，因为这个类中的成员在list这个类中会用到，所以像这种节点类就直接放成公有就好
template<class T>
class list
{
typedef list_node<T> Node;
private:
Node* _head;
size_t _size;
};
对于list这个类，我们需要先把list_node这个类给typedef，否则一直用他太长了，而且要带上模版参数，要注意的是，typedef也会受到访问限定符的限制，所以在外面是看不到Node的，然后我们用这个Node来定义一个头结点，也就是指向头节点的指针_head，然后还有一个成员函数是_size，_size是用来返回链表内的数据个数的，如果没有_size的话就只能遍历求一遍，这样增加一个成员变量代价反而小了
二、默认成员函数
构造函数
构造函数要来初始化成员变量，所以就需要先去给_head去new一个节点，然后它的前驱和后继都指向自己，_size初始化成0就好了，因为头节点不存储有效数据，所以也就不算做元素个数了
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}对于Node这个类在new的时候会去调用它的构造函数，所以我们要给Node类补上一个构造，用匿名对象做这里的缺省参数
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)
{}
};析构函数
析构函数需要把所有的节点都释放了，因为所有节点都是new出来的，那就先来实现一个clear函数
clear
clear是要清空除头节点外链表中所有的节点，就要从头节点的下一个节点开始，去删除每一个节点，但是删除了当前节点就会找不到下一个节点，所以要先保存一下下一个节点
void clear()
{
Node* cur = _head->_next;
while (cur != _head)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
}cur表示的是当前节点，next记录下一个节点的位置，循环判断的条件就是不等于头结点就继续删，删到最后一个节点，那它的next就是头结点了，也就证明删完了，循环结束
那在析构函数中就先去调用clear先把后面链接的节点全部删掉，然后再把头节点删掉并置空就好了
~list()
{
clear();
delete _head;
_head = nullptr;
}拷贝构造
这里就不能再去用memcpy或者赋值来写了，因为list在物理上并不是连续的空间，不可以用下标来访问，所以采用的方法是遍历有数据的这个容器，然后依次尾插进被拷贝的容器中
//l2(l1)
list(const list<T>& l)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
for (auto e : l)
{
push_back(e);
}
}然后这里的l2在插入数据前一定要去初始化，要把头节点new出来再把前后都指向自己，否则在访问时会出问题，这里用的是范围for，那就需要支持迭代器才可以，并且push_back也还没有实现，所以暂时这个拷贝构造是不能跑的，大家可以等下面的实现完再回来看
赋值重载
赋值就写一个现代写法去调用拷贝构造就可以，这个我们很详细的说过了，在这里就不再多赘述了
swap
void swap(list<T>& l)
{
std::swap(_head, l._head);
std::swap(_size, l._size);
}//l2 = l1
list<T>& operator=(list<T> l)
{
swap(l);
return *this;
}三、容量相关
empty
判空的逻辑是判断头节点的前驱和后继是不是指向自己，且元素个数是否为0
bool empty() const
{
return _head->_next == _head
&& _head->_prev == _head
&& _size == 0;
}size
size函数只需要返回_size的值就可以
size_t size() const
{
return _size;
}四、数据访问
front/back
front就是返回第一个节点里存储的值，back返回最后一个节点里的值，一定要注意是第一个存储有效数据的节点，所以是头结点的下一个节点，而不是头节点中存储的值
front和back各自分别有两个版本，一个普通版本，一个const版本，跟我们之前讲的一样，普通对象优先调用普通版本，如果没有普通版本再去调用const版本，const对象只能调用const版本
T& front()
{
return _head->_next->_val;
}
const T& front() const
{
return _head->_next->_val;
}
T& back()
{
return _head->_prev->_val;
}
const T& back() const
{
return _head->_prev->_val;
}五、普通迭代器
我们在最开始的时候说过，list的迭代器与前面的有些不一样，我们就来看看list的迭代器有哪些不一样，可以说list最重要的部分就是迭代器，大家先来看可不可以这么写我们的迭代器呢？
typedef Node* iterator答案显而易见，肯定是不可以的，因为迭代器我们解引用是要拿到数据，但是现在解引用拿到的是一个节点，而且++要向下一个位置走，--要向前一个位置走，现在这个迭代器++走到哪去谁能知道呢？所以我们要用运算符重载来控制这里的逻辑，也就要再封装一个迭代器的类来控制
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
Node* _node;
};在外面需要去访问这个类中的成员函数，所以我们把这个迭代器类定义成struct的，里面有一个节点的指针_node，我们先来实现下*和->，*就是返回数据的引用，->是返回数据的地址
T& operator*()
{
return _node->_val;
}
T* operator->()
{
return &(_node->_val);
}然后是++和--，++就是向下一个节点走，--就是向前一个节点走，而++和--呢又分为前置和后置，我们先实现前置，前置的话就是_node走完返回迭代器的本身，那这个迭代器类的名字太长了，我们也同样来typedef一下
typedef __list_iterator<T> Self;这个typedef就和Node的typedef放在一起就行
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}前置++返回的是迭代器走完的结果，所以就可以用引用返回
后置是返回++或者--之前的值，那就需要先保存一份才可以，然后返回保存的这一份，区分前置和后置，就是给后置加上一个int类型的参数
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}迭代器判断循环结束的条件还有一个不等于，我们来实现一下，就是比较两个指针一不一样就可以了
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}begin/end
begin就是返回头节点的下一个位置，因为迭代器是左闭右开，所以end应该返回的是最后一个有效数据的下一个位置，也就是头节点_head
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}那在list这个类中需要用到iterator，我们就把这个类给嵌到list这个类里，这个要放成公有的，外面要用迭代器
public:
typedef __list_iterator<T> iterator;而且还要给迭代器类实现一个构造函数，用节点指针去构造迭代器，现在的begin和end是隐式类型转换，构造加拷贝构造，拷贝构造我们不需要实现，迭代器去浅拷贝就可以了，也可以返回匿名对象或者是先构造出来对象再返回这个对象，这三种都可以，我们这种是最简单的，直接隐式类型的转换
__list_iterator(Node* node)
:_node(node)
{}我们再结合迭代器的使用来看
int main()
{
hx::list<int> l;
hx::list<int>::iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}需要什么我们就写什么就可以了，迭代器也就是需要这几个函数，不需要实现其他功能了，那我们的普通迭代器就实现好了
六、const迭代器
下面我们来看一下const迭代器，有了刚才的封装，那const迭代器可不可以直接套上一个const呢？
typedef __list_iterator<T> iterator;
typedef const __list_iterator<T> const_iterator;这样写也是不行的，因为这样写就是修饰迭代器本身不能修改了，那迭代器本身都不能修改了还怎么++/--呢？所以const迭代器也是需要我们自己去封装一个自定义类型来控制，那我们就照葫芦画瓢来实现一个
template<class T>
struct __list_const_iterator
{
typedef __list_const_iterator<T> Self;
typedef list_node<T> Node;
Node* _node;
__list_const_iterator(Node* node)
:_node(node)
{}
const T& operator*()
{
return _node->_val;
}
const T* 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->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
那大家有没有发现，普通迭代器和const迭代器不一样的地方就在于*和->的返回值，其他的地方全都一样，那这样设计就太冗余了，我们有没有办法可以就用一个类来控制一下*和->的返回值呢？其实很好办，只需要增加模版参数就可以
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_iterator<T, Ref, Ptr> Self;
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr 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->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};Ref是引用，也就是operator*的返回值，Ptr是指针，也就是operator->的返回值，然后不要忘记在typedef Self的时候把这两个模版参数给加上，然后在list类中我们把后面的两个模版参数写死就可以了
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;begin/end
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}begin和end还是一样的实现逻辑，返回值变一样，再设计成const成员函数就可以
那迭代器部分我们就说到这里，因为这里可能会比较复杂，三个类互相缠绕，所以在文章的最后会把所有的代码给贴出来，如果大家对这里还有不太懂的地方可以去参考
七、插入数据
insert
insert是在某个迭代器插入一个val，那就是把这个迭代器里存的节点指针定义出来，然后找到前一个，再新创建一个节点，把他们之间互相链接起来就行了，最后返回新插入的这个节点的迭代器
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return newnode;
}push_back
push_back是尾插，直接去复用insert，给一个迭代器位置
void push_back(const T& val)
{
insert(end(), val);
}end就是头结点，那在头节点的前面插入也就是尾插
push_front
push_back是头插，直接去复用insert，给一个迭代器位置
void push_front(const T& val)
{
insert(begin(), val);
}begin就是头结点的下一个位置，在begin之前插入，也就是在头结点和第一个节点之间插入，就是头插
八、删除数据
erase
erase是要删除某个迭代器位置，那也是把迭代器里存的节点指针定义出来，然后找到前后节点，把前后节点互相连起来就好了，最后再删除，然后要返回删除的这个位置的下一个节点的迭代器
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return next;
}pop_back
pop_back是尾删，直接去复用erase，给一个迭代器位置
void pop_back()
{
erase(--end());
}end是头节点的位置，那--end就是头结点的前一个，也就是最后一个节点
pop_front
pop_front是头删，直接去复用erase，给一个迭代器位置
void pop_front()
{
erase(begin());
}begin是头结点的下一个位置，也就是第一个存放有效数据的节点
九、代码
namespace hx
{
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_iterator<T, Ref, Ptr> Self;
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr 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->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
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_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//l2(l1)
list(const list<T>& l)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
for (auto e : l)
{
push_back(e);
}
}
//l2 = l1
list<T>& operator=(list<T> l)
{
swap(l);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void swap(list<T>& l)
{
std::swap(_head, l._head);
std::swap(_size, l._size);
}
bool empty() const
{
return _head->_next == _head
&& _head->_prev == _head
&& _size == 0;
}
size_t size() const
{
return _size;
}
void clear()
{
Node* cur = _head->_next;
while (cur != _head)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
}
T& front()
{
return _head->_next->_val;
}
const T& front() const
{
return _head->_next->_val;
}
T& back()
{
return _head->_prev->_val;
}
const T& back() const
{
return _head->_prev->_val;
}
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return newnode;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return next;
}
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
private:
Node* _head;
size_t _size;
};
}总结
本篇文章我们讲了list，以及关于迭代器部分，list的迭代器类型是一个自定义类型，跟以前不太一样，但是这种方式在以前也还是很常见的，比如map/set，unordered map/unordered set，还是要这么用，迭代器部分都要去这样封装，大家还是要习惯这种方式，那本篇文章就到这里啦，如果觉得下篇写的不错的小伙伴，可以给小编一个一键三连表示支持，感谢大家！！！