目录
一,实现list所需要包含的三个类
二,三个类的实现
1.list_node
2.list类
3.iterator_list类
三,功能实现
1.list类里的push_back()
2.iterator类里的运算符重载
3,list类里面的功能函数
1.insert()
2.erase()函数
3.clear()与析构函数
4.拷贝构造函数赋值运算符重载
5.打印函数
一,实现list所需要包含的三个类
因为list是一个带头双向循环链表。所以list的实现会比较的复杂一些。总得来说,实现一个双向带头循环链表需要构造三个类。1.list类,2.list_node类,3.list_iterator类。前两个类相信大家会比较的熟悉。第三个类大家会比较不熟悉,因为它是一个迭代器的类。也就是说这个类是迭代器的封装。它的实现很有价值,因为它能让我们在使用list时也可以像之前的数据结构一样方便。
二,三个类的实现
1.list_node
这首先要实现的便是节点类。这个类是最容易实现的。这个类的作用便是给要产生的节点画一个图,定义一下这个节点的结构和类型。代码如下:
template<class T>//模板
struct list_node
{
list_node(const T& val =T()//匿名对象 )//构造函数起初始化的作用
:val(val)
, prev(nullptr)
, next(nullptr)
{}
T val;
list_node<T>* prev;
list_node<T>* next;
};
现在你看到了,这个节点的结构便是这样。其实这与之前实现的那个带头双向循环链表的结构差不多。不过,在cpp中引入了模板的概念,所以这个节点便可以调用模板参数来进行泛化。
2.list类
list类的定义可太简单了。list的成员变量只有一个参数,便是_head。这是哨兵位的头节点。当然还有一个无参的构造函数和一个功能函数。代码如下:
template<class T>
class list
{ public:
typedef list_node<T> Node;
void empty()//初始化功能函数。
{
_head = new Node;
_head->prev = _head;
_head->next = _head;
}
list()//构造函数
{
empty();
}
private:
Node* _head;
};
当然,这里的list类也是要用模板来进行泛化的。
3.iterator_list类
这个类就算是比较复杂的一个类了。因为迭代器要实现两种重载版本:1.普通版本。2.const版本。所以迭代器类的模板参数会有三个:
template <class T, class Ref, class ptr>
这三个模板参数会重载两种版本的三个参数:T对象,T&,T指针类型。在这个类里面也只有一个成员:_node。类型与list类里面的成员类型相同。该类代码如下:
template <class T, class Ref, class ptr>
struct iterator_list
{
typedef list_node<T> Node;
iterator_list(Node* node)
:_node(node)
{}
Node* _node;
};
三,功能实现
1.list类里的push_back()
首先来实现一个push_back()函数,这个函数的作用便是实现尾插数据。逻辑十分简单,代码如下:
void push_back(const T& val)
{
Node* newnode = new Node(val);
Node* tail = _head->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = _head;
_head->prev = newnode;
}
写完这个以后,我便想要通过显示list里的数据来验证答案,但是很显然,我们做不到。因为list是一个自定义的类。但是我们有办法,所以我们便可以通过iterator来达到这个目的。所以我们必须在iterator类里面实现几个运算符重载。
2.iterator类里的运算符重载
首先先实先这三个运算符重载:1.*,2.++,3.!=
代码如下:
Ref operator *()//Ref代表T&
{
return _node->val;
}
self operator++()
{
_node = _node->next;
return *this;
}
bool operator!=(self& it)
{
return _node != it._node;
}
然后再在list类里面实现begin()与end()函数之后便可以实现范围for的使用了,end与begin代码如下:
//实现两个版本的begin与end
iterator begin()
{
return _head->next;
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->next;
}
const_iterator end()const
{
return _head;
}
在实现了上面的代码以后,为了让迭代器的功能更加全面,那我们再实现几个函数重载。再iterator_list里面的全部运算符重载如下:
Ref operator *()
{
return _node->val;
}
self& operator++()//前置++
{
_node = _node->next;
return *this;
}
self operator++(int)//后置++
{
Node* tmp(*this);
_node = _node->next;
return tmp;
}
self& operator --()//前置--
{
_node = _node->prev;
return *this;
}
self operator--(int)//后置--
{
Node* tmp(*this);
_node = _node->prev;
return tmp;
}
bool operator!=(const self& it)//若用引用便要加上const
{
return _node != it._node;
}
bool operator==(self& it)
{
return _node == it._node;
}
self& operator+(int n)
{
while (n)
{
_node = _node->next;
n--;
}
return *this;
}
ptr operator->()//箭头解引用
{
return &_node->val;
}
在实现了这些运算符重载以后,list类里面的功能函数便好写了许多。
3,list类里面的功能函数
1.insert()
这个函数实现的功能便是在pos位置之前插入一个新的节点。这个pos的类型是迭代器类型。在list类里边的迭代器重定义为:
typedef iterator_list<T, T& ,T*> iterator;
typedef iterator_list<T, const T&, const T*> const_iterator;
我们只需要关注第一个迭代器即可,因为第二个迭代器修饰的对象是不可以修改的。所以insert的实现代码如下:
iterator insert(iterator pos, const T& x)//在pos位置之前插入新节点
{
Node* newnode = new Node(x);
Node* prev = pos._node->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos._node;
pos._node->prev = newnode;
return pos._node->prev;//防止迭代器失效,所以返回pos的前一个位置
}
检验一下,检验代码如下:
void test_list2()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
l1.insert(l1.begin(), 9);
l1.insert(l1.end(), 99);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
}
结果:正确
在实现了insert()函数以后便可以复用实现push_back()与push_front()。代码如下:
void push_back(const T& val)
{
insert(begin(), val);
}
void push_front(const T& val)
{
insert(end(), val);
}
2.erase()函数
erase()函数实现的功能便是传入一个位置,然后将该位置上的节点删除掉。代码实现如下:
iterator erase(iterator pos)
{
Node* prev = pos._node->prev;
Node* next = pos._node->next;
Node* cur = pos._node;
delete cur;
prev->next = next;
next->prev = prev;
return iterator(next);//返回新的迭代器
}
复用erase实现尾删与头删,代码如下:
void pop_back()
{
erase(--end());//尾巴是--end()的位置
}
void pop_front()
{
erase(begin());
}
实验代码:
void test_list3()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
l1.insert(l1.begin(), 9);
l1.insert(l1.end(), 99);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
l1.pop_back();
l1.pop_front();
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
}
结果:正确
3.clear()与析构函数
实现了erase()函数以后再接再厉,接着复用实现clear函数,代码如下:
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);//erase()每次都会返回下一个位置
}
}
从上面代码的逻辑便可以看出clear()函数是不会删除掉头节点的。但是析构函数需要。于是复用clear()函数后析构函数代码如下:
~list()
{
clear();
delete _head;
}
4.拷贝构造函数赋值运算符重载
拷贝构造函数实现过程大概分三步,首先new出来一个空间。然后再复用push_back()函数将要赋值的数据拷贝到新节点内。实现代码如下:
list(const list<T>& l1)
{
empty();
for (auto e : l1)
{
push_back(e);
}
}
实现了拷贝构造以后,按照惯例,赋值也要被安排上了。赋值运算符重载实现代码如下:
list<T>& operator =( list<T>& l1)
{
if (this!= &l1)
{
clear();
for (auto e : l1)
{
push_back(e);
}
}
return *this;
}
这是一个传统写法的运算符重载。如果想要更加精简可以写成现代写法,代码如下:
void swap( list<T>& l1)//别加const
{
std::swap(_head, l1._head);//记得这个swap是std里面的swap
}
list<T>& operator=(list<T> l1)
{
if (this != &l1)
{
swap(l1);
}
return *this;
}
5.打印函数
在这里,我们每次打印一个list对象时会很麻烦,每次都要用范围for来实现打印的功能。为了偷懒,我就想实现一个打印函数print来实现打印功能。实现代码如下:
template<class T>
void print(list<T>& l1)
{
typename list<T>::iterator it = l1.begin();//这里要用typename为前缀来告诉编译器等list<T>实例化以后再来执行这条语句
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
}
但是上面的代码针对的类型时list类的泛型,如果想要实现能加载更多容器的print()函数那就得改一下类型,改为如下代码:
template <class Contains>
void print(Contains& l1)
{
typename Contains::iterator it = l1.begin();
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
}