通过比较list与vector在简单模拟实现时的不同进一步理解STL的底层

 cplusplus.com/reference/list/list/?kw=list

当我们大致阅读完list的cplusplus网站的文档时，我们会发现它提供的接口大致上与我们的vector相同。当然的，在常用接口的简单实现上它们也大体相同，但是它们的构造函数与迭代器的实现却大有不同。(食用本文时建议与文末的模拟实现代码一起食用，效果更佳)

一，list与vector在构造函数上的不同

 1.1成员封装的不同

我们在vector中，需要封装的成员只有我们顺序表的起始指针，有效元素的末尾指针，以及用来记录空间结束位置的指针：

如果我们在list中，便无法再这样封装，因为我们的list存放数据的内存并不连续，所以我们需要对链表的节点用额外的结构体封装，而在原本的list类里面我们封装的成员则是链表的头结点：

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;};
template<class T>
class list
{
void empty_init()
{_head = new Node();_head->_next = _head;_head->_prev = _head;
}
list()
{empty_init();
}
typedef list_node<T> Node;
private:Node* _head;
};

1.2迭代器的封装的不同 

在vector中，迭代器可以直接简单的设置为我们存储数据类型的对应指针。但是在list中，我们发现迭代器需要指向的是一个节点，有人说那我直接照搬vector不也OK。但是这时候就会有个问题，因为我们的节点相当于一个自定义类型，后面在进行调用的时候不可避免的会去调用它的构造函数，同时我们迭代器又会有许多的函数去使用，所以迭代器也需要额外的用一个类来封装。

template<class T, class Ref, class Ptr>
struct list_iterator//tip
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;
};

TIPS:这里将迭代器与结点成员设置为公开是为了方便list类的调用，实际上我们在使用list时也无法直接调用这些成员，这也是对成员的保护方式。

二，list与vector在迭代器上的不同(重点) 

 2.1对迭代器的const修饰

在我们的vector中，由于我们的迭代器本身就是我们存储数据的类型的相应指针，所以我们可以通过直接加const的方式来实现我们的const_iterator。但是在list中，由于我们的迭代器是指向一个自定义类型的指针，而我们的自定义类型中存储数据。如果我们直接用const来修饰，会发现我们此时无法修改迭代器指向的结点，从而无法完成我们后续的遍历。如果我们要为const来再额外封装一个类，会使代码看上去非常冗余。

在stl的源码中有着这样的几行代码：

template <class T, class Ref, class Ptr>
struct __slist_iterator : public __slist_iterator_base
{typedef __slist_iterator<T, T&, T*>             iterator;typedef __slist_iterator<T, const T&, const T*> const_iterator;typedef __slist_iterator<T, Ref, Ptr>           self;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __slist_node<T> list_node;

我们发现，它的模板参数有三个。其实由于我们的目的是为了源结点中的值无法被改变，只需要我们在返回结点中的值时加上const修饰，而我们获取存储数据的方式无非两种，一种是对迭代器解引用(其中_node是当前迭代器指向的结点)：

T& operator*()
{return _node->_data;
}

或者通过->来获取：

T* operator->()
{return &_node->_data;
}

 所以我们只需要对T*与T&在模板实例化时用const修饰即可：

typedef list_iterator<T,T&,T*> iterator;//tip
typedef list_iterator<T,const T&,const T*> const_iterator;//tip

 TIP:在迭代器的类型中我们又分为随机，双向和单向迭代器，从左向右为父级关系。在使用库中的sort时对list无法使用快排，因为他是双向迭代器，而vector之所以可以使用是因为他是随机迭代器。

2.2list反向迭代器的实现

通过上面的多个模板参数的引出，我们可以对反向的迭代器Reverse_iterator来封装进行封装：

template<class Iterator>
class ReverseListIterator
{// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIterator<Iterator> Self;
public://// 构造ReverseListIterator(Iterator it) : _it(it) {}//// 具有指针类似行为Ref operator*() {Iterator temp(_it);--temp;return *temp;}Ptr operator->() { return &(operator*()); }//// 迭代器支持移动Self& operator++() {--_it;return *this;}Self operator++(int) {Self temp(*this);--_it;return temp;}Self& operator--() {++_it;return *this;}Self operator--(int){Self temp(*this);++_it;return temp;}//
// 迭代器支持比较
bool operator!=(const Self& l)const{ return _it != l._it;}
bool operator==(const Self& l)const{ return _it != l._it;}
Iterator _it;
};

原理其实就是我们2.1中介绍到的，这里我们直接给出模拟实现代码。

三，list与vector其他方面不同的总结(不仅是模拟实现上)

附件：list的简单模拟实现代码(常用接口) 

/
#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <list>
using namespace std;namespace ELY {template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};template<class T,class Ref,class Ptr>struct list_iterator//tip{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;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};template<class T>class list{void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}public:typedef list_node<T> Node;typedef list_iterator<T,T&,T*> iterator;//tiptypedef list_iterator<T,const T&,const T*> const_iterator;//tiplist(){empty_init();}list(const list<T>& list){empty_init();for (auto i : list){push_back(i);}}list<T>& operator=(list<T> list){swap(list);return *this;}list(size_t n, const T& val = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end() {return iterator(_head);}const_iterator end() const{return const_iterator(_head);}void push_back(const T& x = T()){Node* newnode = new Node(x);Node* tail = _head->_prev;newnode->_next = _head;newnode->_prev = tail;tail->_next = newnode;_head->_prev = newnode;}iterator insert(iterator pos, const T& val)//tip{Node* newnode = new Node(val);Node* cur = pos._node;cur->_prev->_next = newnode;newnode->_prev = cur->_prev;cur->_prev = newnode;newnode->_next = cur;return iterator(newnode);}iterator push_front(const T& val){return insert(begin(), val);}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;cur->_next->_prev = cur->_prev;cur->_prev->_next = cur->_next;pos = cur->_next;delete cur;return pos;}iterator pop_front(){return erase(begin());}iterator pop_back(){return erase(--end());}void clear(){auto i = begin();while (i != end()){i = erase(i);}}void swap(list<T>& list){std::swap(_head, list._head);}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;};
}
/
mylist.h