STL详解——list的模拟实现
目录
1.list的定义
2.迭代器
2.1基本功能实现
2.2const迭代器
2.2.1基本迭代器的完善
2.2.2const迭代器的基本实现
2.2.3模板优化语法
2.3自定义类型数据迭代器
2.3.1使用情景
2.3.2嵌套类模板
3.其他接口的实现
3.1insert与erase
3.2头插与头删
3.3析构与拷贝构造
3.4赋值运算符重载与构造扩展
1.list的定义
STL中的list容器不同于数据结构中常见的单链表，而是一种带头双向链表，因此在实现过程中也以此结构为基础实现。对于链表，最基本的便的其结点，因此我们先实现结点的定义：
template<class T>
struct _list_node
{T val;_list_node* next;_list_node* prev;
};完成结点的定义后，我们便成将list容器抽象为以头结点(哨兵位)为头的多结点链，结点间能通过彼此互相访问。因此list的成员变量便是头结点(_head)。
对list进行初始化，因是带头双向链表，因此初始化就是将头结点初始化为一个next与prev都指向头的结点，但在这之前需要给_head申请(new)一个结点(Node)的空间，new自定义类型的时候会调用结点类的构造函数，因此这时还需要完善结点类的构造函数
//结点
template<class T>
struct _list_node
{T val;_list_node* next;_list_node* prev;//完善构造_list_node():val(0),next(nullptr),prev(nullptr){}
};//list链表
template<class T>
class list
{
public:typedef _list_node<T> Node;//构造list(){_head = new Node;_head->next = _head;_head->prev = _head;}private:Node* _head;
};2.迭代器
2.1基本功能实现
迭代器的基本功能就是通过类指针的形式来遍历容器元素，对于vector这种底层为数据的容器，可以用最简单的指针来完成迭代器的封装，而list这种底层非连续空间的容器，则需要将遍历的方式封装为一种迭代器类。初步接触迭代器封装，可以通过使用来逐步实现：
namespace my_list
{void test01(){list<int> lt1;list<int>::iterator it = lt1.begin();while (it != lt1.end()){cout << *it << ' ';++it;}cout << endl;}
}迭代器最基本的使用无非就是要完成上面的功能，list最基本元素是结点，因此迭代器成员变量代表的也应是结点， 接下来要实现的便是++迭代器能完成指向下一个结点，迭代器解引用能返回结点中的值。代码如下：
//迭代器(一、初代)template<class T>struct _list_iterator{typedef _list_node<T> Node;Node* _node;_list_iterator(Node* node):_node(node){}T& operator*(){return _node->val;}_list_iterator<T> operator++(){_node = _node->next;return *this;}bool operator!=(const _list_iterator<T>& it)//注意不能使用非const引用{return _node != it._node;}};//list链表template<class T>class list{public:typedef _list_node<T> Node;typedef _list_iterator<T> iterator;//构造list(){_head = new Node;_head->next = _head;_head->prev = _head;}//迭代器iterator begin(){return iterator(_head->next);}iterator end(){return iterator(_head);}private:Node* _head;};这里需要注意的是begin与end的返回值为临时对象(具有常性)不能用非const引用来接受，因此在!=重载函数中的参数选择为const引用。
下面通过push_back插入数据来检验一下：
void push_back(const T& x)
{Node* newnode = new Node;newnode->val = x;newnode->next = _head;newnode->prev = _head->prev;_head->prev->next = newnode;_head->prev = newnode;
}namespace my_list
{void test01(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);list<int>::iterator it = lt1.begin();while (it != lt1.end()){cout << *it << ' ';++it;}cout << endl;}
}int main()
{my_list::test01();return 0;
}运行结果如下：
这里也算基本完成迭代器功能。
2.2const迭代器
2.2.1基本迭代器的完善
在完成const迭代器前，先对之前的基本迭代器进行完善，即完善相对应的运算符重载。
_list_iterator<T> operator++(int)
{_list_iterator<T> tmp(*this);_node = _node->next;return *this;
}_list_iterator<T>& operator--()
{_node = _node->prev;return *this;
}_list_iterator<T> operator--(int)
{_list_iterator<T> tmp(*this);_node = _node->prev;return tmp;
}bool operator== (const _list_iterator<T>& it)
{return _node == it._node;
}2.2.2const迭代器的基本实现
const迭代器的功能是迭代器可以修改，但让迭代器指向的内容不能修改。因此这里的迭代器不能像vector中的直接在iterator前加const修饰，因为vector中迭代器底层是指针，const修饰的实际是指针类型；而list中迭代器是一种自定义类型，使用const修饰的效果为迭代器不能修改，但迭代器指向的内容可以修改。
因此这里要实现const迭代器功能主要是让解引用返回的对象不能修改，也就是让返回值变为const T&即可。
但这里的iterator需变为const_iterator，类的类型发生了改变，因此这里需要再重新创建一个const迭代器类：
//二、const迭代器
template<class T>
struct _list_iterator
{typedef _list_node<T> Node;Node* _node;_list_iterator(Node* node):_node(node){}T& operator*(){return _node->val;}_list_iterator<T> operator++(){_node = _node->next;return *this;}bool operator!=(const _list_iterator<T>& it){return _node != it._node;}_list_iterator<T> operator++(int){_list_iterator<T> tmp(*this);_node = _node->next;return *this;}_list_iterator<T>& operator--(){_node = _node->prev;return *this;}_list_iterator<T> operator--(int){_list_iterator<T> tmp(*this);_node = _node->prev;return tmp;}bool operator== (const _list_iterator<T>& it){return _node == it._node;}
};template<class T>
struct _list_const_iterator
{typedef _list_node<T> Node;Node* _node;_list_const_iterator(Node* node):_node(node){}_list_const_iterator(const _list_iterator<T>& it):_node(it._node){ }const T& operator*(){return _node->val;}_list_const_iterator<T> operator++(){_node = _node->next;return *this;}bool operator!=(const _list_const_iterator<T>& it){return _node != it._node;}_list_const_iterator<T> operator++(int){_list_const_iterator<T> tmp(*this);_node = _node->next;return *this;}_list_const_iterator<T>& operator--(){_node = _node->prev;return *this;}_list_const_iterator<T> operator--(int){_list_const_iterator<T> tmp(*this);_node = _node->prev;return tmp;}bool operator== (const _list_const_iterator<T>& it){return _node == it._node;}
};list中迭代器相关函数const重载如下:
//迭代器
iterator begin()
{return iterator(_head->next);
}iterator end()
{return iterator(_head);
}const_iterator begin()const
{return const_iterator(_head->next);
}const_iterator end()const
{return const_iterator(_head);
}在const迭代器类中为支持非const迭代器转换为const迭代器，重载了使用迭代器初始化的拷贝构造。
这里能不能将代码进行简化呢？
2.2.3模板优化语法
const迭代器仅仅是在解引用时返回值不同，按前面写法便要写两个类。若这时将解引用返回的类型用模板表示，这时通过不同的模板实例化也能区分两种类。具体实现方法如下：
//二、const迭代器
template<class T, class Ref>
struct _list_iterator
{typedef _list_node<T> Node;typedef _list_iterator<T, Ref> Self;Node* _node;_list_iterator(Node* node):_node(node){}_list_iterator(const _list_iterator<T, T&>& it):_node(it._node){}Ref operator*(){return _node->val;}Self operator++(){_node = _node->next;return *this;}bool operator!=(const Self& it){return _node != it._node;}Self operator++(int){Self tmp(*this);_node = _node->next;return *this;}Self& operator--(){_node = _node->prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->prev;return tmp;}bool operator== (const Self& it){return _node == it._node;}
};这样通过模板实例化的不同也能实现const迭代器与普通迭代器的分离。
2.3自定义类型数据迭代器
2.3.1使用情景
list作为一种顺序容器，除储存内置类型外，也可储存自定义类型，如储存位置数据(Pos)：
struct Pos
{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}
};void test02()
{list<Pos> lt1;list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){}
}对于这种自定义类型，重载的解引用出来是Pos结构体，要访问其中数据还要自己处理：
void test02()
{list<Pos> lt1;lt1.push_back({ 1,1 });lt1.push_back({ 2,2 });lt1.push_back({ 3,3 });list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){cout << (*it)._row << ':' << (*it)._col << endl;++it;}
}但在STL库中，迭代器对于这种自定义类型还提供了类似结构体指针的访问方法：
但对于我们自己的list容器，迭代器并不是指向该自定义类型指针，因此这里实际是对->运算符的重载。->的重载实际是要返回Pos的指针，这里为了区分const与非const，依旧使用模板优化语法。
template<class T, class Ref, class Ptr>
struct _list_iterator
{typedef _list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> Self;Ptr operator->(){return &(_node->val);}
};但这里需要注意：->重载后返回的是结构体的指针，即整个it->代表的是结构体指针，原则上需要在it->后再使用->调用数据，但编译器简化成了一个->。
2.3.2嵌套类模板
先来看看下面场景：
template <class T>
void Print(const list<T>& lt)
{list<T>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';++it;}cout << endl;
}运行结果如下：
可以看到这种写法是错误的，原因是在类模板未实例化时，不能去找类模板后面东西，编译器分不清const_iterator是嵌套内类，还是静态成员变量。这时可以用typename告诉编译器这里是类型：
template <class T>
void Print(const list<T>& lt)
{typename list<T>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';}cout << endl;
}当然也可以用auto接收迭代器：
auto it = lt.begin();3.其他接口的实现
在实现完迭代器后，便能接着实现许多依托于迭代器功能的接口。
3.1insert与erase
insert与erase接口实现逻辑类似：
iterator insert(const iterator& pos, const T& x)
{Node* newnode = new Node(x);Node* cur = pos._node;newnode->prev = cur->prev;newnode->next = cur;cur->prev->next = newnode;cur->prev = newnode;return iterator(newnode);
}iterator erase(const iterator& pos)
{Node* next = pos._node->next;Node* prev = pos._node->prev;next->prev = prev;prev->next = next;delete pos._node;return iterator(next);
}3.2头插与头删
void push_front(const T& x)
{insert(begin(), x);
}void pop_front()
{erase(begin());
}3.3析构与拷贝构造
void empty_init()
{_head = new Node;_head->next = _head;_head->prev = _head;
}//构造
list()
{empty_init();
}list(const list<T>& lt)
{empty_init();const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}
}~list()
{clear();delete _head;_head = nullptr;
}void clear()
{iterator it = begin();while (it != end()){it = erase(it);}
}3.4赋值运算符重载与构造扩展
list(std::initializer_list<T> il)
{empty_init();for (const auto& e : il){push_back(e);}
}//赋值重载
void swap(list<T>& lt)
{if (this != <){std::swap(_head, lt._head);}
}list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}