1. list的介绍

list其实就是就是我们所熟知的链表（双向循环带头结点），但其是作为STL中的一个类模板而存在。

也就是说，list是可以用来存储任意类型数据的顺序表，既可以是内置类型，也可以是自定义类型，或是STL中的其他容器。

除了底层的实现不同以外，用法与vector基本相同，但不支持随机访问，以及与随机访问有关的接口。

具体以list - C++ Reference为准，本文为该文档的一个简单总结与标注。

2. list的重要接口

以下表格中的函数都不是官方库中的函数原型，而是为了方便学习和理解而进行了简化的。

2.1 默认成员函数

2.1.1 构造函数

四种构造方式

(1) list();	默认构造
(2) list(size_t n, const T& val = T());	用val初始化list前n个数据
(3) template<class InputIterator> list(InputIterator first, InputIterator last);	用迭代器区间进行初始化
(4) list(const list& x);	拷贝构造

 2.1.2 赋值重载

 2.2 迭代器相关

begin	返回开始位置的迭代器
end	返回最后一个数据的下一个位置的迭代器
rbegin	用于逆向迭代
rend	用于逆向迭代
cbegin	用于const修饰的容器的迭代
cend	用于const修饰的容器的迭代
crbegin	用于const修饰的容器的逆向迭代
crend	用于const修饰的容器的逆向迭代

2.3 大小容量相关

bool empty() const;	判断list是否为空
size_t size() const;	返回list中的数据个数
size_t max_size() const;	返回由于系统或数据库限制，list能够存储数据的最大容量（并不一定能达到）

2.4 访问相关

(1) T& front(); (2) constT& front() const;	返回第一个元素的引用
(1) T& back(); (2) constT& back() const;	返回最后一个元素的引用

2.5 元素修改相关

(1) template<class InputIterator>      void assign(InputIterator first, InputIterator last); (2) void assign(size_t n, const T& val);	给list赋新的值，效果类似于重新构造这个list
void push_front(const T& val);	在list头部插入一个元素
void push_back(const T& val);	在list尾部插入一个元素
void pop_front();	删除list头部的一个元素
void pop_back();	删除list尾部的一个元素
(1) iterator insert(iterator pos, const T& val); (2) void insert(iterator pos, size_t n, const T& val); (3) template <class InputIterator>      void insert(iterator position, InputIterator first，InputIterator last);	在指定位置插入元素，常数时间O(1)，效率很高，不会导致迭代器失效
(1) iterator erase(iterator pos); (2) iterator erase(iterator first, iterator last);	删除指定位置的数据，常数时间O(1)，效率很高，会导致当前位置迭代器失效
void swap(list<T>& x);	交换两个list的数据
void resize(size_t n, T val = T());	改变list的元素个数，使其容纳n个元素，n<size则删除多余的，n>size则加入n个值与val相同的元素
void clear();	清空list

2.6 list结点移动

(1) void splice(iterator position, list& x); (2) void splice(iterator position, list& x, iterator i); (3) void splice(iterator position, list& x, iterator first, iterator last);	(1) 将x的结点全部移动到position位置 (2) 将x中i指向的结点移动到position位置 (3) 将x中first到last的结点移动到position位置
void remove(const T& val);	移除list中与val值相同的结点
template <class Predicate> void remove_if(Predicate pred);	按照pred(*it)函数的返回值(true移除/false不移除)来移除结点
(1) void unique(); (2) template <class BinaryPredicate>      void unique(BinaryPredicate binary_pred);	(1) 移除值连续相等(operator==)的几个结点，只留下这组结点中的第一个(在处理经过排序的list时，能确保各种值得结点只留下一个) (2) 按照binary_pred(*it, *(it-1))给出的逻辑判断结点的值是否相等，进而删除结点
(1) void merge(list& x); (2) template <class Compare>      void merge(list& x, Compare comp);	(1) 将x合并到调用函数的list中(x的结点全部移动到list中，并确保合并后的list中的结点也是有序(operator<)的，但要求两个list事先都是有序的。如果list==*this，该函数无行为) (2) 按照comp函数给出的比较方式来进行有序的合并
(1) void sort(); (2) template <class Compare>      void sort(Compare comp);	(1) 按照operator<进行排序 (2) 按照comp给出的比较方式排序
void reverse();	逆置list

3. 迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

4. list不完全模拟实现示例

<code>#pragma once

#include<iostream>

using namespace std;

namespace lbz

{

// List的节点类

template<class T>

struct ListNode

{

ListNode(const T& val = T())

:_val(val)

,_pPre(nullptr)

,_pNext(nullptr)

{}

ListNode<T>* _pPre;

ListNode<T>* _pNext;

T _val;

};

//List的迭代器类

template<class T, class Ref, class Ptr>

struct ListIterator

{

typedef ListNode<T>* PNode;

typedef ListIterator<T, Ref, Ptr> Self;

typedef Ref _Ref;

typedef Ptr _Ptr;

public:

ListIterator(PNode pNode = nullptr)

:_pNode(pNode)

{}

ListIterator(const Self& l)

:_pNode(l._pNode)

{}

T& operator*()

{

return _pNode->_val;

}

// 按理来说在使用时需要两个->，但编译器为了可读性做了优化

T* operator->()

{

return &(_pNode->_val);

}

Self& operator++()

{

_pNode = _pNode->_pNext;

return (*this);

}

Self operator++(int)

{

Self tmp = (*this);

_pNode = _pNode->_pNext;

return tmp;

}

Self& operator--()

{

_pNode = _pNode->_pPre;

return (*this);

}

Self& operator--(int)

{

Self tmp = (*this);

_pNode = _pNode->_pPre;

return tmp;

}

bool operator!=(const Self& l) const

{

return (this->_pNode != l._pNode);

}

bool operator==(const Self& l) const

{

return (this->_pNode == l._pNode);

}

PNode _pNode;

};

template<class iterator>

struct reverseListIterator

{

typedef typename iterator::_Ref Ref;

typedef typename iterator::_Ptr Ptr;

typedef reverseListIterator<iterator> Self;

reverseListIterator(iterator it)

:_it(it)

{}

Ref operator*()

{

iterator tmp(_it);

--tmp;

return *tmp;

}

Ptr operator->()

{

return &(operator*());

}

Self& operator++()

{

--_it;

return *this;

}

Self& operator++(int)

{

Self tmp(*this);

--_it;

return tmp;

}

Self& operator--()

{

++_it;

return *this;

}

Self& operator--(int)

{

Self tmp(*this);

++_it;

return tmp;

}

bool operator==(const Self& rit) const

{

return _it == rit._it;

}

bool operator!=(const Self& rit) const

{

return _it != rit._it;

}

iterator _it;

};

//list类

template<class T>

class list

{

typedef ListNode<T> Node;

typedef Node* PNode;

public:

typedef ListIterator<T, T&, T*> iterator;

typedef ListIterator<T, const T&, const T&> const_iterator;

typedef reverseListIterator<iterator> reverse_iterator;

typedef reverseListIterator<const_iterator> const_reverse_iterator;

public:

///

// List的构造

list()

{

CreateHead();

}

list(int n, const T& value = T())

{

CreateHead();

while (n--)

{

push_back(value);

}

}

template <class Iterator>

list(Iterator first, Iterator last)

{

CreateHead();

while (first != last)

{

push_back(*first);

++first;

}

}

list(const list<T>& l)

{

CreateHead();

list tmp(l.begin(), l.end());

swap(tmp);

}

// 支持用大括号参数列表构造/隐式类型转换

list(initializer_list<T> il)

{

CreateHead();

for (auto& e : il)

{

push_back(e);

}

}

list<T>& operator=(const list<T> l)

{

list tmp(l.begin(), l.end());

swap(tmp);

return *this;

}

~list()

{

clear();

delete _pHead;

_pHead = nullptr;

}

///

// List Iterator

iterator begin()

{

return iterator(_pHead->_pNext);

}

iterator end()

{

return iterator(_pHead);

}

const_iterator begin() const

{

return const_iterator(_pHead->_pNext);

}

const_iterator end() const

{

return const_iterator(_pHead);

}

const_iterator cbegin() const

{

return const_iterator(_pHead->_pNext);

}

const_iterator cend() const

{

return const_iterator(_pHead);

}

reverse_iterator rbegin()

{

return reverse_iterator(end());

}

reverse_iterator rend()

{

return reverse_iterator(begin());

}

const_reverse_iterator crbegin() const

{

return const_reverse_iterator(cend());

}

const_reverse_iterator crend() const

{

return const_reverse_iterator(cbegin());

}

///

// List Capacity

size_t size()const

{

return _size;

}

bool empty()const

{

return !_size;

}

// List Access

T& front()

{

return _pHead->_pNext->_val;

}

const T& front()const

{

return _pHead->_pNext->_val;

}

T& back()

{

return _pHead->_pPre->_val;

}

const T& back()const

{

return _pHead->_pPre->_val;

}

// List Modify

void push_back(const T& val) { insert(end(), val); }

void pop_back() { erase(--end()); }

void push_front(const T& val) { insert(begin(), val); }

void pop_front() { erase(begin()); }

// 在pos位置前插入值为val的节点

iterator insert(iterator pos, const T& val)

{

PNode newnode = new Node(val);

newnode->_pNext = pos._pNode;

newnode->_pPre = pos._pNode->_pPre;

pos._pNode->_pPre->_pNext = newnode;

pos._pNode->_pPre = newnode;

_size++;

return pos;

}

// 删除pos位置的节点，返回该节点的下一个位置

iterator erase(iterator pos)

{

pos._pNode->_pNext->_pPre = pos._pNode->_pPre;

pos._pNode->_pPre->_pNext = pos._pNode->_pNext;

iterator ret = pos._pNode->_pNext;

delete pos._pNode;

--_size;

return ret;

}

void clear()

{

PNode cur = _pHead->_pNext->_pNext;

while (cur != _pHead->_pNext)

{

delete cur->_pPre;

cur = cur->_pNext;

}

_pHead->_pNext = _pHead;

_pHead->_pPre = _pHead;

_size = 0;

}

void swap(list<T>& l)

{

std::swap(_pHead, l._pHead);

std::swap(_size, l._size);

}

private:

void CreateHead()

{

_pHead = new Node;

_pHead->_pNext = _pHead;

_pHead->_pPre = _pHead;

}

PNode _pHead;

size_t _size = 0;

};

};

5. list的迭代器

由于底层结构的复杂性，list的迭代器不再像string和vector那样可以直接由指针代劳。

我们依然将结点指针作为list迭代器的底层，但是各操作符原本的逻辑已经无法满足我们的需要，均需要进行重载。

于是，我们用ListIterator类对结点的指针进行了包装，并对所需的操作符进行了相应的重载。

//List的迭代器类

template<class T, class Ref, class Ptr>

struct ListIterator

{

typedef ListNode<T>* PNode;

typedef ListIterator<T, Ref, Ptr> Self;

typedef Ref _Ref;

typedef Ptr _Ptr;

public:

ListIterator(PNode pNode = nullptr)

:_pNode(pNode)

{}

ListIterator(const Self& l)

:_pNode(l._pNode)

{}

T& operator*()

{

return _pNode->_val;

}

// 按理来说在使用时需要两个->，但编译器为了可读性做了优化

T* operator->()

{

return &(_pNode->_val);

}

Self& operator++()

{

_pNode = _pNode->_pNext;

return (*this);

}

Self operator++(int)

{

Self tmp = (*this);

_pNode = _pNode->_pNext;

return tmp;

}

Self& operator--()

{

_pNode = _pNode->_pPre;

return (*this);

}

Self& operator--(int)

{

Self tmp = (*this);

_pNode = _pNode->_pPre;

return tmp;

}

bool operator!=(const Self& l) const

{

return (this->_pNode != l._pNode);

}

bool operator==(const Self& l) const

{

return (this->_pNode == l._pNode);

}

PNode _pNode;

};

其中Ref代表T的引用，Ptr代表T的指针，根据这两个参数是否被const修饰，我们可以实例化出普通的迭代器和const迭代器：

typedef ListIterator<T, T&, T*> iterator;

typedef ListIterator<T, const T&, const T&> const_iterator;

6. list反向迭代器

与正向迭代器相比，反向迭代器只是在进行++或--的行为与其不同。

我们可以采用适配器模式（stack和queue也是采用该种模式对其他容器进行包装）来实现反向迭代器：

用迭代器作为反向迭代器的底层，通过对正向迭代器的接口进行包装，使其行为满足我们的需求。

template<class iterator>

struct reverseListIterator

{

typedef typename iterator::_Ref Ref;

typedef typename iterator::_Ptr Ptr;

typedef reverseListIterator<iterator> Self;

reverseListIterator(iterator it)

:_it(it)

{}

Ref operator*()

{

iterator tmp(_it);

--tmp;

return *tmp;

}

Ptr operator->()

{

return &(operator*());

}

Self& operator++()

{

--_it;

return *this;

}

Self& operator++(int)

{

Self tmp(*this);

--_it;

return tmp;

}

Self& operator--()

{

++_it;

return *this;

}

Self& operator--(int)

{

Self tmp(*this);

++_it;

return tmp;

}

bool operator==(const Self& rit) const

{

return _it == rit._it;

}

bool operator!=(const Self& rit) const

{

return _it != rit._it;

}

iterator _it;

};

 同理，我们可以定义出普通反向迭代器和const反向迭代器：

typedef reverseListIterator<iterator> reverse_iterator;

typedef reverseListIterator<const_iterator> const_reverse_iterator;

7. list和vector的区别

容器	list	vector
底层结构	带头结点的双向循环链表	动态顺序表，一段连续空间
随机访问	不支持随机访问，访问某个元素效率O(N)	支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容 增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低
空间利用率	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低	底层为连续空间，不容易造成内存碎片，空间利用 率高，缓存利用率高
迭代器	对原生态指针(节点指针)进行封装	原生态指针
迭代器失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效
使用场景	大量插入和删除操作，不关心随机访问	需要高效存储，支持随机访问，不关心插入删除效率