通过比较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;//tipTIP:在迭代器的类型中我们又分为随机，双向和单向迭代器，从左向右为父级关系。在使用库中的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;//tip
typedef list_iterator<T,const T&,const T*> const_iterator;//tip
list()
{
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