【c++】【STL】list详解

list的作用

list是c++的stl库提供的链表容器，链表作为我们熟知的数据结构之一，其与顺序表相比，在任意位置插入删除方面具有绝对的优势，但在随机读取方面不如顺序表，两者属于互补关系，stl中的list底层是用双向链表实现的，以实现反向迭代器的反向读取，stl中还有forward_list，它是由单向链表实现的。

list的接口

构造函数

//默认构造
explicit list (const allocator_type& alloc = allocator_type());
//指定链表初始化大小和链表初始化的值
explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
//使用迭代器进行构造           
template <class InputIterator>list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
//拷贝构造
list (const list& x);

四种构造方式都较为常用

赋值运算符重载

list& operator= (const list& x);

重载了来链表复制，代码更加易读。

迭代器相关

      iterator begin();
const_iterator begin() const;iterator end();
const_iterator end() const;reverse_iterator rbegin();
const_reverse_iterator rbegin() const;reverse_iterator rend();
const_reverse_iterator rend() const;const_iterator cbegin() const noexcept;const_iterator cend() const noexcept;const_reverse_iterator crbegin() const noexcept;const_reverse_iterator crend() const noexcept;

由于链表是非连续性容器，所以迭代器还是很实用的。

size

size_type size() const;

返回链表尺寸。

empty

bool empty() const;

链表判空。

front

      reference front();
const_reference front() const;

返回对链表第一个元素的引用。

back

      reference back();
const_reference back() const;

返回对链表最后一个元素的引用。

assign

template <class InputIterator>void assign (InputIterator first, InputIterator last);//迭代器初始化
void assign (size_type n, const value_type& val);//指定初始化大小和内容

重新初始化链表。

push_front

void push_front (const value_type& val);

头插。

pop_front

void pop_front();

头删。

push_back

void push_back (const value_type& val);

尾插。

pop_back

void pop_back();

尾删。

insert

//插入一个
iterator insert (iterator position, const value_type& val);//插入一段
void insert (iterator position, size_type n, const value_type& val);//插入迭代器表示的一段
template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);

插入函数，链表的插入函数效率很高。

erase

iterator erase (iterator position);//删除一个
iterator erase (iterator first, iterator last);//删除一段

删除函数，链表的删除函数效也很高。

swap

void swap (list& x);

交换函数，交换两个链表。

resize

void resize (size_type n, value_type val = value_type());

重新指定链表的大小，如果n大于链表此时的size，就扩充到n大小，然后将扩充后的节点的值初始化成指定内容（缺省为0）；如果n小于链表此时的size，就减小到n大小，然后删除并销毁超出的部分。

clear

void clear();

清空链表。

splice

void splice (iterator position, list& x);//转移一整个
void splice (iterator position, list& x, iterator i);//转移指定位置的元素
void splice (iterator position, list& x, iterator first, iterator last);//转移指定的一段。

将链表中的元素转移到另一个链表中，position是插入位置。

remove

void remove (const value_type& val);

删除链表中所有与给定值相等的元素。

remove_if

template <class Predicate>void remove_if (Predicate pred);

删除链表中所有Predicate pred返回true的元素的函数，这允许我们删除满足特定复杂条件的元素。

unique

void unique();
template <class BinaryPredicate>void unique (BinaryPredicate binary_pred);

这个函数可以让链表中等于特定值或满足特定条件的元素唯一，与remove和remove_if函数类似，只不过他们是全部删除，unique是要留一个。

merge

  void merge (list& x);
template <class Compare>void merge (list& x, Compare comp);

将两个已经满足一定顺序的链表合并为一个满足这个顺序的新链表，默认顺序是升序，也就是说合并两个升序链表时可以用第一个函数，其他的都需要写仿函数。

sort

void sort();默认升序
template <class Compare>void sort (Compare comp);//自定义

list自己的排序函数。

reverse

void reverse();

list自己的反转函数。

关系运算符重载（非成员函数）

template <class T, class Alloc>bool operator== (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator!= (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator<  (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator<= (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator>  (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator>= (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);

list的模拟实现

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>using namespace std;namespace jiunian
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()) :_pPrev(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPrev;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;ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_val;}Ptr 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->_pPrev;return *this;}Self& operator--(int){Self tmp(*this);_pNode = _pNode->_pPrev;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;};//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;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++));}}list(const list<T>& l){CreateHead();for (auto& e : l){push_back(e);}}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin()const{return _pHead->_pNext;}const_iterator end()const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _pHead == _pHead->_pNext;//size == 0;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPrev->_val;}const T& back()const{return _pHead->_pPrev->_val;}// List Modifyvoid 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){Node* newnode = new Node(val);newnode->_pPrev = pos._pNode->_pPrev;newnode->_pNext = pos._pNode;pos._pNode->_pPrev->_pNext = newnode;pos._pNode->_pPrev = newnode;++_size;return newnode;}//iterator insert(iterator pos, const T& x)//{//    Node* cur = pos._pNode;//    Node* prev = cur->_pPrev;//    Node* newnode = new Node(x);//    prev->_pNext = newnode;//    newnode->_pNext = cur;//    cur->_pPrev = newnode;//    newnode->_pPrev = prev;//    //++_size;//    return newnode;//}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;iterator ret = pos._pNode->_pNext;delete pos._pNode;--_size;return ret;}void clear(){iterator cur = begin();while (cur != end()){cur = erase(cur);}_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->_pPrev = _pHead;}PNode _pHead;size_t _size = 0;};
};

对于list这种存储不连续的容器，其迭代器的实现就不能像string和vector一样直接对指针进行封装，虽然对于迭代器来说，其底层的实现离不开指针，但其还是有别于string和vector的。

结点类

在对于迭代器进行说明之前，我还是要先介绍一下链表的结点类，结点是组成链表的基本单位，是需要单独封装的。

// List的节点类
template<class T>
struct ListNode
{ListNode(const T& val = T()) :_pPrev(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPrev;ListNode<T>* _pNext;T _val;
};

由于我们创建的是一个双向带头链表，所以一个节点要给一个指针指向前一个结点，也要给一个指针指向后一个节点，再者因为ListNode中的成员之后都要被list类频繁使用，所以我们直接将类定义成struct，因为struct的元素在不加访问限定符的情况下都是默认共有的（兼容c语言）。最后我们为这个类写上构造函数就完成了。

迭代器类

//List的迭代器类
template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_val;}Ptr 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->_pPrev;return *this;}Self& operator--(int){Self tmp(*this);_pNode = _pNode->_pPrev;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;
};

之后就是迭代器的说明了，在有了对于string和vector的实现经验之后，其实对于list这个类本身的实现已经很轻松了，因为stl库中的容器之间是有很强的共性的，实现的思路大差不差，但对于list的迭代器还是有所不同的，因为list要实现不连续内存容器的随机访问。首先我们看向这个类所给的模板参数，有三个，这其实是一个令人疑惑的点，因为通常来说我们只需要给一个模板参数说明迭代器指向的节点中的val是什么类型不就行了，但这里所给的参数有足足三个，这里直接理解是理解不同的，我们不妨先往下看。

typedef的妙用

typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;

这两句代码我想要单独拎出来讲，如果我们有一些阅读源码的经历，我们会发现写源码的那些大佬会经常性的使用typedef，一层套一层，看起来像是脱裤子放屁，但其实不然，比如这里，假如我们不使用typedef，那会阻碍我们书写代码吗？答案是不会的，typedef无非只是个替换，不使用无非只是麻烦一点，多写几个模板参数实例化的事（其实省事这一点就足以成为我们使用它的理由了），但倘若我们书写完代码之后因为某些原因要改变ListNode或ListIterator的模板参数数量或者模板参数名就麻烦了，我们要把之前写ListNode和ListIterator都写一遍，如果代码量巨大，那将是一场噩梦，但倘若我们用了typedef，不仅书写时就省了事，书写之后万一要对typedef的内容进行更改也是很轻松的，只要把typedef的地方一改其他地方都会改。说到底，这样写本质上降低了代码之间的关联度（耦合度），我们作为代码学习者，可能会从某些地方听说过高内聚低耦合的概念，高内聚低耦合就是指尽量使一个模块的代码专注于完成单一任务，且模块与模块之间的关联度尽可能地低。我们这里使用typedef就大大地降低了代码之间的关联度，这样一处代码的修改带来的连锁反应会尽可能地小，这是我们在书写代码时要时刻注意的。

*运算符重载

Ref operator*()
{return _pNode->_val;
}

这段代码是对于*的运算符重载这不难看出，但是我们看想这个函数的返回值，只是我们之前所说的三个模板参数中的第二个，我们仔细想想，倘若这里不使用模板参数，我们应该写什么呢？当然是_val类型的引用，解引用运算符之后的变量更改会影响原指针指向的数，所以要用引用。但为什么要用模板参数呢，这时我们看向list类的这一段，

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

对于迭代器来说，不仅有普通迭代器，还有const版的，而普通迭代器和const迭代器除了*和->运算符重载不一样之外，其他的都是一致的，所以我们通过传三个参数的方式成功偷了一波懒，一个类干了别人两个类干的事，剩下的事由编译器来完成。

->运算符重载

Ptr operator->()
{return &(_pNode->_val);
}

这个函数可以访问_val的对象成员（前提是_val得有对象成员，没有用不到），这个函数笔者在一开始理解时非常困惑，因为笔者认为迭代器视为指向链表结点的指针，而->被用来在使用指针的情况下访问对象元素，所以这个->是用来访问系欸但元素的，也就是_val、_pPrev和_pNext，但事实上不是，这里迭代器不应该被看作为一个指向结点的指针，而应该看作为一个指向_val的指针，因为我是在实现这个类的基础之上去理解这个迭代器的，我先入为主了，最为使用者来说，我并不清楚list类的底层如何实现，我也就不用会知道list其实有一个前置的类叫ListNode，也并不知道ListNode中有三个元素_val、_pPrev和_pNext，在使用者看来，迭代器就是指向容器元素本身，使用->访问的就是元素这个对象本身的元素（前提是有元素）。理解了这个函数本身的作用之后，我们看向这个函数的返回值，返回值类型使用了单独的模板参数，这在前一个解引用运算符重载中讲过了，这里也是如此，

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

这里的Ptr指的T*（或const T*）。我们再看向返回值本身，_pNode->_val取地址，这个函数返回之后会发生什么呢，假如我们写了以下代码

std::cout << it->a << std::endl;

it->使用运算符重载返回了一个指针，那代码就变成了一个指针和一个元素中间没有运算符，这因该是会报错的操作，但这里是会正常编译通过的，因为c++在这里又做了特殊处理给这两个变量中间加上了一个->，所以时候事实上来说代码应该是这样的

std::cout << it->->a << std::endl;//演示一下，事实上会报错

可以看出c++为了增加代码可读性还是做出了很多妥协的。

++、–运算符重载

Self& operator++()
{_pNode = _pNode->_pNext;return *this;
}Self operator++(int)
{Self tmp(*this);_pNode = _pNode->_pNext;return tmp;
}Self& operator--()
{_pNode = _pNode->_pPrev;return *this;
}Self& operator--(int)
{Self tmp(*this);_pNode = _pNode->_pPrev;return tmp;
}

之后还要说明的就是迭代器的++和–的运算符重载，因为之前我们也说过，list是内存不连续的容器，所以++和–运算符都不能直接以指针++和–的形式实现，而是使用ListNode中_pPrev和_pNext指针来实现迭代，至于前置++（–）和后置++（–）的书写区别，之前的文章也讲过，因为它们是单参运算符，无法通过位置识别从而进行不同的操作，所以c++特别规定++（–）运算符重载时在参数列表多加上int的是后置++（–），没加的是前置++（–）。

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;
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++));}}list(const list<T>& l){CreateHead();for (auto& e : l){push_back(e);}}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin()const{return _pHead->_pNext;}const_iterator end()const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _pHead == _pHead->_pNext;//size == 0;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPrev->_val;}const T& back()const{return _pHead->_pPrev->_val;}// List Modifyvoid 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){Node* newnode = new Node(val);newnode->_pPrev = pos._pNode->_pPrev;newnode->_pNext = pos._pNode;pos._pNode->_pPrev->_pNext = newnode;pos._pNode->_pPrev = newnode;++_size;return newnode;}//iterator insert(iterator pos, const T& x)//{//    Node* cur = pos._pNode;//    Node* prev = cur->_pPrev;//    Node* newnode = new Node(x);//    prev->_pNext = newnode;//    newnode->_pNext = cur;//    cur->_pPrev = newnode;//    newnode->_pPrev = prev;//    //++_size;//    return newnode;//}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;iterator ret = pos._pNode->_pNext;delete pos._pNode;--_size;return ret;}void clear(){iterator cur = begin();while (cur != end()){cur = erase(cur);}_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->_pPrev = _pHead;}PNode _pHead;size_t _size = 0;
};

list类的实现就比较公式化了，值得一说的就几个，下面一一讲解。

CreateHead（头节点创建）

void CreateHead()
{_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPrev = _pHead;
}

首先是CreateHead()，这个函数被用于创建头节点，我们实现的list的底层是带头双向链表，头节点是必须的，这个函数在很多成员函数中都会用到，所以单独封装并放进private访问限定符中限制外部访问。函数实现思路也很简单，new一个节点出来，指针首尾相连就行。

insert

iterator insert(iterator pos, const T& val)
{Node* newnode = new Node(val);newnode->_pPrev = pos._pNode->_pPrev;newnode->_pNext = pos._pNode;pos._pNode->_pPrev->_pNext = newnode;pos._pNode->_pPrev = newnode;++_size;return newnode;
}

之后是insert函数，insert函数可以被反复复用到一些成员函数之中，十分方便。实现思路就是创建一个节点插入pos迭代器指向的节点的前面，接一下指针就行，之后返回新插入的结点防止迭代器失效。

erase

iterator erase(iterator pos)
{pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;iterator ret = pos._pNode->_pNext;delete pos._pNode;--_size;return ret;
}

erase函数也可以被复用到一些成员函数之中，非常方便，实现思路就是将pos指向的结点的前一个和后一个相接之后删除这个结点，之后返回原本pos指向的结点的下一个结点。

赋值运算符重载

list<T>& operator=(list<T> l)
{swap(l);return *this;
}

赋值运算符重载，这里我们故意不用引用，这样传过来的参数就是拷贝构造好的需要被赋值成的对象，直接交换，由于临时变量的生命周期出了作用域就没了，所以正好把之前的对象的销毁，完美完成交换。