网硕互联帮助中心一.list的简单介绍
list是一个带头双向循环的链表，通过头结点分隔开首末尾。它和vector的使用方法类似，可以进行头插尾插，++/–等操作，区别在于list的结点在内存上不是连续的。list属于双向迭代器即可以++/–，不能想vector一样可以进行随机访问。
二.list模拟实现的三个类
1.结点类
根据list的特点带头双向循环，我们可以得知，他需要一个前置结点prev，以及后置结点next，保证能向前向后找到结点。 每个结点存有数据data，我们可以用模板T来进行复用。
template <class T>
struct list_node
{
list_node(const T& x = T())//模板有x时情况
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
list_node<T>* _next;
list_node<T>* _prev;
T _data;
};
2.迭代器类
我们知道迭代器分为普通迭代器和const迭代器，在实现string类和vector类时我们并没有单独对迭代器这一类进行实现，这是因为vector和string类在底层空间上是连续的，可以直接进行++/–，解引用操作。但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)
{}
T& operator*()
{
return _node->_data;
}
T& operator++()//前置
{
_node = _node->_next;
return *this;
}
T& operator++(int)//后置,后置++区分前置要加入括号
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
T& operator–()//前置
{
_node = _node->_prev;
return *this;
}
T& operator–(int)//前置
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
T* operator->()
{
return &_node->_data;
}
bool operator!=(const T& it)
{
return _node != it._node;
}
bool operator==(const T& it)
{
return _node == _it._node;
}
};
如上我们对迭代器进行了初步的实现，里面的实现内容较为简单就不一一展开叙述。这时候又有了另一个问题，如果迭代器是const类型的该怎么办呢？还是像上面这样，重新封装一个const_iterator类吗？
这样操作固然是没有问题的，但是还不够简略。
我们可以仔细想想，普通迭代器与const迭代器的区别不就是多了一个const吗？所以我们可以考虑用模板来套用实现。
template<class T,class Ref,class Ptr>//提供模板参数，为const类型提供模板参数,ref代替引用，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;
}
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;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == _it._node;
}
};
我们将原先的T& 用模板Ref来替代，T* 用模板Ptr来代替。这样就对代码进行了缩减。所以用ref和ptr模板我们就不需要关心是不是const类型迭代器，只要传就是什么，我们就无需关心。
3.链表类
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 list_iterator(_head->_next);
}
iterator end()
{
return list_iterator(_head);
}
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
list()
{
empty_init();
}
list(initializer_list<T> it)
{
for (auto& e : it)
{
push_back(e);
}
}
list(const list<T>& it)
{
empty_init();
for (auto& e : it)
{
push_back(e);
}
}
~list()
{
clear();
}
void swap(list<T>& it)
{
std::swap(_head, it._head);
}
list<T>& operator=(list<T> it)
{
swap(it);
return *this;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;
newnode->_prev = tail;
tail->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;
}
void push_front(const T& x)
{
insert(begin(), x);
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(–end());
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* nextNode = cur->_next;
Node* prevNode = cur->_prev;
prevNode->_next = nextNode;
nextNode->_prev = prevNode;
delete cur;
return iterator(nextNode);
}
private:
Node* _head;
};
}
上述只需要注意一点，就是erase的用法。erase在官方库中是有返回值的，在使用时，例如析构时需要用变量来接收erase的返回值，否则容易导致迭代器失效。
链表部分的实现不难，基本都是先前vector类实现的功能相差无几，构造函数，拷贝函数，析构函数，迭代器的运用，以及增删等操作。
三.总结
本篇文章最关键的内容就是对于模板的复用，在面对代码相似度较高，实现功能类似的情况下，我们需要优先考虑模板的复用。
下面放上完整代码：
#pragma once
#include <iostream>
using namespace std;
namespace wu
{
template <class T>
struct list_node
{
list_node(const T& x = T())//模板有x时情况
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
list_node<T>* _next;
list_node<T>* _prev;
T _data;
};
template<class T,class Ref,class Ptr>//提供模板参数，为const类型提供模板参数,ref代替引用，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;
}
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;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == _it._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 list_iterator(_head->_next);
}
iterator end()
{
return list_iterator(_head);
}
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
list()
{
empty_init();
}
list(initializer_list<T> it)
{
for (auto& e : it)
{
push_back(e);
}
}
list(const list<T>& it)
{
empty_init();
for (auto& e : it)
{
push_back(e);
}
}
~list()
{
clear();
}
void swap(list<T>& it)
{
std::swap(_head, it._head);
}
list<T>& operator=(list<T> it)
{
swap(it);
return *this;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;
newnode->_prev = tail;
tail->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;
}
void push_front(const T& x)
{
insert(begin(), x);
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(–end());
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* nextNode = cur->_next;
Node* prevNode = cur->_prev;
prevNode->_next = nextNode;
nextNode->_prev = prevNode;
delete cur;
return iterator(nextNode);
}
private:
Node* _head;
};
}
评论前必须登录！
注册