目录

1.链表节点的构建

2.迭代器的初步实现

3.成员变量以及默认构造

4.普通迭代器接口

5.插入接口

6.删除与find接口

7.const迭代器实现与接口

8.范围拷贝与拷贝构造

9.如果实例化参数是自定义类型

10.析构函数

11.完整代码

1.链表节点的构建

链表的节点有指针与和数据域，所以无法用任何一个内置类型来表示它，我们需要自定义好节点的类型。list容器使用的是带头双向循环链表。

	template struct list_node		//节点类型{list_node* _next;list_node* _prev;T _val;list_node(const T& val = T()) :_val(val),_next(nullptr),_prev(nullptr){}};

2.迭代器的初步实现

链表的节点所占用的内存空间是不连续的，所以不能使用原生指针来代替迭代器。我们需要自定义迭代器的行为(例如++是从前一个节点移动到后一个节点)。

template struct list_iterator{typedef list_node node;node* pnode;list_iterator(node* p):pnode(p){}list_iterator& operator++(){pnode = pnode->_next;return *this;}bool operator!=(list_iterator& lt){return pnode != lt.pnode;}};

3.成员变量以及默认构造

定义空容器时，容器是存在头节点(哨兵卫)的。

	template class list{public:typedef list_node node;typedef list_iterator iterator;void empty_init(){_head = new node(T());		//哨兵卫_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();		//复用}private:node* _head;size_t size;		//记录有节点个数(除哨兵卫)};

4.普通迭代器接口

iterator begin()
{return iterator(_head->_next);
}
iterator end()
{return iterator(_head);		//尾后迭代器
}

5.插入接口

插入有头插、尾插、随机插。我们重点实现随机插，头插和尾插复用随机插。

void push_back(const T& val)
{insert(end(), val);		//在哨兵卫头插就是尾插
}void push_front(const T& val)
{insert(begin(), val);
}iterator insert(iterator pos, const T& val)
{node* newnode = new node(val);node* prev = pos.pnode->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = pos.pnode;pos.pnode->_prev = newnode;++_size;return iterator(newnode);		//返回插入节点的位置(防止迭代器失效)
}

6.删除与find接口

删除有头删、尾删、随机删。我们重点实现随机删，头删和尾删复用随机删。

void pop_back()
{erase(end().pnode->_prev);
}void pop_front()
{erase(begin());
}iterator erase(iterator pos)
{assert(end() != pos);		//不能删除哨兵卫node* prev = pos.pnode->_prev;node* next = pos.pnode->_next;prev->_next = next;next->_prev = prev;delete pos.pnode;--_size;return iterator(next);		//返回删除节点的下一个节点位置(防止迭代器失效)}iterator find(iterator first, iterator last, const T& val)
{assert(first != last);while (first != last){if (*first == val) return first;++first;}return end();
}

7.const迭代器实现与接口

不能使用const成员函数重载，因为我们要的效果是底层const而非顶层const(即指向的内容不可变，迭代器本身可变)。所以我们有两套方案，一是再构建一个迭代器类模板；二是在原来的迭代器模板基础上添加一个模板参数。再构建一个迭代器的方案与原模板的唯一区别就是返回值不同。所以否决第一套设计方案。

现在先统一一下迭代器接口：

typedef list_iterator iterator;
typedef list_iterator const_iterator;const_iterator begin() const
{return const_iterator(_head->_next);
}
const_iterator end() const
{return const_iterator(_head);
}

迭代器设计：

template 		//多使用一个模板参数
struct list_iterator
{typedef list_node node;typedef list_iterator self;		//为了方便node* pnode;list_iterator(node* p):pnode(p){}ref operator*(){return pnode->_val;}self& operator++(){pnode = pnode->_next;return *this;}bool operator!=(self& lt){return pnode != lt.pnode;}
};

8.范围拷贝与拷贝构造

我们实现更加全面的构造接口。

template 
list(InputIterator first, InputIterator last)		//范围拷贝
{empty_init();while (first != last){push_back(*first);++first;}
}void swap(list& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
list(const list& lt)		//拷贝构造现代写法
{empty_init();list tmp(lt.begin(), lt.end());swap(tmp);
}list& operator=(list lt)		//赋值运算符重载现代写法
{swap(lt);return *this;
}

9.如果实例化参数是自定义类型

如果链表的节点是一个自定义类型，那么使用 * 将无法读取自定义类型的数据。所以我们需要完善访问自定义类型成员的功能，即 -> 运算符重载。此重载函数的返回值是实例化参数类型的指针，这个指针也有const与非const之分，并且调用此重载的对象可能是const或非const对象，也就是说迭代器可能是const迭代器与非const迭代器。那么我们依然为迭代器模板添加一个参数，并且完善迭代器的功能。

别忘了对迭代器的重命名需要更新一下：

typedef list_iterator iterator;
typedef list_iterator const_iterator;

template 		//多使用一个模板参数
struct list_iterator
{typedef list_node node;typedef list_iterator self;		node* pnode;list_iterator(node* p):pnode(p){}ref operator*(){return pnode->_val;}ptr operator->(){return &pnode->_val;}self& operator++(){pnode = pnode->_next;return *this;}self operator++(int)		//后置++{node* tmp(pnode);pnode = pnode->_next;return tmp;}self& operator--(){pnode = pnode->_prev;return *this;}self operator--(int)		//后置--{node* tmp(pnode);pnode = pnode->_prev;return tmp;}bool operator!=(const self& lt){return pnode != lt.pnode;}bool operator==(const self& lt){return pnode == lt.pnode;}
};

10.析构函数

释放分为两个部分，一是不释放哨兵卫，将有效节点释放；而是全部释放。我们实现一个clear接口，让析构复用此接口。

~list()
{clear();delete _head;_head = nullptr;
}void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

11.完整代码

这里只实现了list容器常用的接口，并没有完全依照标准库1：1模拟实现。代码会有很多细节没有处理好，并不是会报错，而是有些地方显得不够严谨。

#include 
#include 
namespace ly
{template struct list_node		//节点类型{list_node* _next;list_node* _prev;T _val;list_node(const T& val = T()) :_val(val),_next(nullptr),_prev(nullptr){}};template 		//多使用一个模板参数
struct list_iterator
{typedef list_node node;typedef list_iterator self;		node* pnode;list_iterator(node* p):pnode(p){}ref operator*(){return pnode->_val;}ptr operator->(){return &pnode->_val;}self& operator++(){pnode = pnode->_next;return *this;}self operator++(int)		//后置++{node* tmp(pnode);pnode = pnode->_next;return tmp;}self& operator--(){pnode = pnode->_prev;return *this;}self operator--(int)		//后置--{node* tmp(pnode);pnode = pnode->_prev;return tmp;}bool operator!=(const self& lt){return pnode != lt.pnode;}bool operator==(const self& lt){return pnode == lt.pnode;}
};template class list{public:typedef list_node node;typedef list_iterator iterator;typedef list_iterator const_iterator;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);}void empty_init(){_head = new node(T());		//哨兵卫_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();		//复用}template list(InputIterator first, InputIterator last)		//范围拷贝{empty_init();while (first != last){push_back(*first);++first;}}void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(const list& lt)		//拷贝构造现代写法{empty_init();list tmp(lt.begin(), lt.end());swap(tmp);}list& operator=(list lt)		//赋值运算符重载现代写法{swap(lt);return *this;}void pop_back(){erase(end().pnode->_prev);}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(end() != pos);		//不能删除哨兵卫node* prev = pos.pnode->_prev;node* next = pos.pnode->_next;prev->_next = next;next->_prev = prev;delete pos.pnode;--_size;return iterator(next);		//返回删除节点的下一个节点位置(防止迭代器失效)}iterator find(iterator first, iterator last, const T& val){assert(first != last);while (first != last){if (*first == val) return first;++first;}return end();}void push_back(const T& val){insert(end(), val);		//在哨兵卫头插就是尾插}void push_front(const T& val){insert(begin(), val);}iterator insert(iterator pos, const T& val){node* newnode = new node(val);node* prev = pos.pnode->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = pos.pnode;pos.pnode->_prev = newnode;++_size;return iterator(newnode);		//返回插入节点的位置(防止迭代器失效)}private:node* _head;size_t _size;		//记录有节点个数(除哨兵卫)};
}