【C++】list的模拟实现
目录
前言：list的简单介绍
一、Member variables
二、iterator
1、__list_iterator
2、begin()、end()
3、const_begin()、const_end()
4、operator!=、==
5、operator++
6、operator--
7、operator*
8、operator->
三、Modifiers
1、push_back
2、push_front
3、insert
4、pop_back
5、pop_front
6、erase
7、swap
8、clear
四、constructor
1、无参构造
2、迭代器区间构造
3、拷贝构造
五、destructor
六、operator=
总结
前言：list的简单介绍
list是C++STL中十分重要的容器，这个容器不可以使用[ ]来对链表进行操作
list的优点是按需索取，不会占用过多的空间，同时它的头部和尾部的插入删除时间复杂度是O(1)
因为它是带头双向循环链表，找头和尾的时间复杂度都是O(1)
同时还有会造成内存碎片的问题，因为它的节点是通过new出来的，频繁的new和delete必然会导致内存碎片。
list的遍历只能通过迭代器，因此它的迭代器是我们要重点实现的部分
一、Member variables
链表的成员变量很明显就是，链表的节点，而链表的节点是一个聚合类型，所以很明显链表节点是一个类，一个带头双向循环链表的成员一定有它当前节点的值，指向下一个节点的指针，和指向上一个节点的指针。同时还要有它的构造函数，构造函数就比较简单了，类似于数据结构带头双向循环链表的BuyNode函数，开一个空间，将当前节点的next和prev指针都指向空，然后在插入时链接到链表中就可以了，经过前面的叙述，我们可以得知这个类应该使用struct来定义是最好的，因为我们要访问节点的成员变量。
//带头双向循环链表
//链表节点
template<class T>
struct list_node
{
list_node(const T& value = T())
:_value(value)
,_next(nullptr)
,_prev(nullptr)
{}
T _value;
list_node<T>* _next;
list_node<T>* _prev;
};二、iterator
链表的迭代器与我们的vector和string有很大的不同，因为vector和string的空间是连续的，而list的空间是不连续的，它是一个一个的节点组成的
迭代器的定义是使用起来像指针，vector和string空间连续，所以直接是原生指针
而list空间不连续.。
C++相比于C语言的优势在于函数重载和封装，所以我们可以将指针封装成一个迭代器，分别实现++ -- * 等操作符重载就可以实现迭代器
1、__list_iterator
这个类就是迭代器，既然是迭代器，它会看起来像是一个指针，而这个"指针"是指向链表结点的，所以要想完成上面的操作，必然会需要我们向__list_iterator传一个节点
所以__list_iterator的成员函数就是节点list_node
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T> iterator;
__list_iterator(Node* node)
:_node(node)
{}
Node* _node;
};这就是__list_iterator的简单框架
2、begin()、end()
要实现这两个成员函数，首先要想清楚begin()和end()到底指向哪个位置？
在STL的规范中begin是指向第一个元素的，end是指向尾元素的下一个位置的
因为我们的list是带头的，而头是不存储有效数据的，所以begin不能指向头，所以begin指向的应该是_head->next，而尾的下一个元素就是_head，因为是双向循环链表
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}这里特别说明一点，begin和end是list这个类的成员函数，并不是__list_iterator类里面的成员函数
下面的const_begin和const_end同理
因为都是迭代器的功能所以放在了这里，这里的排列顺序是根据实现顺序来排列的
3、const_begin()、const_end()
到了const版本的时候这里就出现了问题，如果还是按照我们的vector和string的方式写const迭代器就会出现问题
因为const迭代器必然是为了const对象也能够调用，函数重载的规则可没有根据返回值不同来区分重载的函数，而如果我们在函数后面加上const
const_iterator begin()const
{
return _head->next;
}它也会出现编译错误，无法解引用const对象的成员变量，因为我们要返回的是head的next
这个操作一定会将list类的成员变量_head解引用来找到它的下一个节点，所以不能在函数后面加const，那么这到底要怎么写才能够使const对象也能够调用呢？
我们可以看一下STL的源码
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
//…………………………
};我们发现它的迭代器一共有三个模板参数，分别是T, Ref, Ptr
const迭代器有三个参数T, const T&, const T*
STL源码是通过实例化出的对象类型不同来区分是普通对象还是const对象的
因为无论是const对象还是普通对象，调用begin()的操作基本类似，唯一不同的是返回值类型，const对象要返回的是const 类型，普通对象返回普通类型
因此我们使用模板参数显示的控制就可以了，模板参数分别是T(普通类型)，Ref(引用类型),Ptr(指针类型)
这三个参数还要在后面的操作符重载函数中有用，具体细节在下面
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}4、operator!=、==
在前面的内容铺垫下这两个操作符是很容易实现的，这就是判断两个迭代器想不想等，换句话来说就是判断这两个迭代器所指向的节点想不想同
bool operator!=(const iterator& it)const
{
return _node != it._node;
}
bool operator==(const iterator& it)const
{
return _node == it._node;
}5、operator++
++分为前置++和后置++
所谓的++就是将迭代器移动到下一个节点，就是cur->next
iterator& operator++()
{
_node = _node->_next;
return *this;
}
iterator operator++(int)
{
//浅拷贝就够用了，返回的是tmp的拷贝
iterator tmp(*this);
_node = _node->_next;
return tmp;
}细心的同学会发现我们的__list_iterator并没有实现=操作符重载，因为没有必要，浅拷贝就足够了
后置++返回的是我们没有++的值，我们直接传值返回临时对象就可以了，我们不可能会对++之前的值进行操作。
6、operator--
--与++同理，因为是双向链表，--就是将迭代器移动到cur->prev
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
iterator operator--(int)
{
iterator tmp(*this);
_node = _node->_prev;
return tmp;
}7、operator*
在实现这个成员函数时，我们应该仔细想一想，迭代器解引用得到的是list节点的值，而不是整个节点，所以只要返回节点值就可以了，对应的返回值类型应该是Ref
Ref operator*()
{
return _node->_value;
}8、operator->
这个操作符也是，要想一想它的应用场景，它一般应用在结构体指针中，并且它的左操作数必须是指针类型，那么我们自然就很清楚，我们要返回的是指针类型Ptr
与*操作符重载的不同就在于返回的类型不同而已
Ptr operator->()
{
return &(operator*());
}三、Modifiers
这几个函数都是十分的简单，在链表的博客中都已经写明了如何实现，在这里就不再赘述
1、push_back
void push_back(const T& x)
{
Node* newNode = new Node(x);
Node* tail = _head->_prev;
tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _head;
_head->_prev = newNode;
}2、push_front
void push_front(const T& x)
{
insert(begin(), x);
}3、insert
iterator insert(iterator pos, const T& x)
{
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;
return iterator(newNode);
}4、pop_back
void pop_back()
{
erase(--end());
}5、pop_front
void pop_front()
{
erase(begin());
}
6、erase
//返回的是删除元素的下一个位置
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}7、swap
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}8、clear
主要说一下clear与析构函数的区别：clear是清空list，但是list中还保留这头节点
而析构函数是将整个list全部清理
void clear()
{
iterator it = begin();
while(it != end())
{
it = erase(it);
}
}四、constructor
list的构造函数与vector的特别像
1、无参构造
list的无参构造与带头双向循环链表的init函数类似
不过STL中的无参构造调用了empty_init()这个函数，我们为了仿照库中的实现，也定义了这个函数
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}无参构造，我们直接让无参构造调用empty_init就可以
list()
{
empty_init();
}2、迭代器区间构造
这个构造与vctor相同，完全的一模一样就不再赘述
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while(first != last)
{
push_back(*first);
first++;
}
}3、拷贝构造
拷贝构造我们使用现代写法，调用迭代器区间的构造函数，然后将临时对象的头节点与我们的头节点交换就完成了操作
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}这里调用了empty_init是为了先要有头节点，只有有了头节点push_back才不会崩溃
五、destructor
析构函数也与vector类似，不过我们可以先调用clear，然后手动释放头节点
~list()
{
clear();
delete _head;
_head = nullptr;
}六、operator=
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}总结
以上就是今天要讲的内容，本文仅仅简单的模拟实现了list，list的空间配置器和反向迭代器还没有实现