C++STL系列之list

---

前言

这个是C语言中的带头双向循环链表，这么设计更方便头插尾插，end()迭代器指向头部，既然是带头双向循环链表，意味着每个结点都存放一个next和prev指针，通过头结点可以快速找到尾结点，任意位置插入都在常数时间内(得益于迭代器)。

如果熟悉C语言模拟的带头双向循环链表，list就会熟悉，list真正比较难的点在于迭代器和const迭代器，因为内部空间物理上不连续，逻辑上连续，无法像vector和string那样typedef T* iterator;这里留个悬念，后面讲。

---

一、list类以及常用接口和函数

官方文档

构造函数

和vector对比一下发现基本上一样，也没啥可说的了。

迭代器

既然是双向,就和vector的一样，普通，const，反向，const反向。

容量

和vector差别很大了，因为他是链表，无法提前扩容，也没有capacity一说。

重要函数

也和vector类似，vector没实现头插和头删因为效率太低（可以insert(begin())来哦头插），但是list的头插，头删，尾插，尾删效率非常高，其余接口没啥可说的。

操作

演示：

void Test_splice(list<int> lt,list<int> lt1)
{lt.splice(lt.begin(),lt1);cout << "splice后:";for (auto e : lt) {cout << e << ' ';}cout << endl;
}
void Test_remove(list<int> lt)
{lt.remove(2);lt.remove(4);cout << "remove后:";for (auto e : lt) {cout << e << ' ';}cout << endl;
}
void Test_remove_if(list<int> lt)
{lt.remove_if([](int a) {return a % 2 == 0; });cout << "remove偶数后:";for (auto e : lt) {cout << e << ' ';}cout << endl;
}
void Test_unique(list<int> lt)
{lt.unique();cout << "unique后:";for (auto e : lt) {cout << e << ' ';}cout << endl;
}
void Test_merge(list<int> lt,list<int> lt1)
{	lt.sort(), lt1.sort();lt.merge(lt1);cout << "merge后:";for (auto e : lt) {cout << e << ' ';}cout << endl;
}
void Test_sort(list<int> lt)
{lt.sort();cout << "sort后:";for (auto e : lt) {cout << e << ' ';}cout << endl;
}
void Test_reverse(list<int> lt)
{lt.reverse();cout << "reverse后:";for (auto e : lt) {cout << e << ' ';}cout << endl;
}int main()
{list<int> lt{5,3,1,2,2,5,4,6};list<int> lt1{ 7,8,9,10,11 };cout << "原lt为{5,3,1,2,2,5,4,6}" << endl;cout << "原lt1为{ 7,8,9,10,11 }" << endl;Test_splice(lt, lt1);Test_remove(lt);Test_remove_if(lt);Test_unique(lt);Test_merge(lt, lt1);Test_sort(lt);Test_reverse(lt);return 0;
}

用法用几次基本就会了，但是有几个需要注意的点：

1.splice

注意，如果传的是右值属性，或者传的拷贝，此时splice后，右值x被悬空，不能使用x。

2.merge

要求合并前两个list均有序。

3，sort

我问你，库里有一个sort，那这个sort还有用吗？当然，因为库里要求的是随机迭代器，list是双向迭代器。但是sort的意义不大，因为如果想要有序用list本身就不是一个明智的选择，list排序很麻烦，不如vector / set。

二、迭代器失效问题

insert

insert会失效吗？不会，因为insert不会涉及到开空间，只是把结点连接起来就可以，但是为了保持一致性，库里的insert同样返回的是新插入元素位置的迭代器。

erase

erase会失效吗？包的，你那个位置都没了当然失效了，所以erase会导致当然位置的迭代器失效，解决方法：返回值给原迭代器下一个迭代器的位置

三、list的模拟实现

list除了迭代器还是比较简单的，把_prev和_next链接好就可以，注意控制好_head

结点：

template<class T>
struct list_node 
{T _val;list_node<T>* _next;list_node<T>* _prev;list_node(const T&x):_val(x),_next(nullptr),_prev(nullptr){}
};

list基本框架

还是加一个_sz来存储数据，这样求size()就可以快速拿到，否则还要遍历。

namespace myspace {template<class T>class list {typedef list_node<T> Node;public:list(){_head = new Node;_head->_prev = _head;_head->_next = _head;_sz = 0;}void push_back(const T& x){Node* newnode = new Node(x);Node* _tail = _head->_prev;_head->_prev = newnode;newnode->_next = _head;_tail->_next = newnode;newnode->_prev = _tail;_sz++;}private:Node* _head;size_t sz;};
}

当然，库里push_back还是复用的insert,所以我们来讲迭代器的实现。

普通迭代器

list的迭代器库里设计的很有意思，让我们一点一点讲下去。
首先想普通迭代器怎么设计？ 直接使用T*一定不行，内存上不连续，使用不了，这里C++类里可以重载++，–，*的优势就来了，我们可以定义一个类，只分装一个结点指针，++就是让这个指针往next走，解引用就是拿到_node里的值，相等就是判断_node相不相等，begin就是iterator(_head->next)来构造。
大致写一个就是：

template<class T>
struct list_iterator
{typedef list_node<T> Node; typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*(){return _node->_val;}Self& operator++()//前置加加{_node = _node->_next;return *this;}Self operator++(int)//后置加加{Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& x)const{return _node != x._node;}bool operator==(const Self& x)const{return _node == x._node;}T* operator->(){return &(operator*());}
};//list类里
typedef list_iterator<T> iterator;//迭代器
iterator begin()
{return iterator(_head->_next);
}
iterator end()
{return iterator(_head);
}

这里operator->的实现很有意思，当然可以直接对val取地址，这两个结果一样。
设一个Self是因为名字过长，这样比较方便。
这样遍历的代码就能跑起来了。

const迭代器

下一步：const迭代器怎么设计？先想一个问题，const迭代器是什么变成const属性？其实也就是operator* 和 operator->拿到的内容不能改变，有一种比较明显的思路，就是再分装一个类叫const_list_iterator去控制，当然这样是可以的，但是库里很杜绝这种非常冗余的行为，就是两份非常相似的代码不写一份而写两份，这块我们在set和map还会充分提现这个思想，库里怎么设计的呢？只能说真的很牛这个设计，它额外控制了两个模板参数来控制operator* 和operator->的返回值，在list里通过传const类型就是const迭代器，非const就是普通迭代器，

//list迭代器
template<class T,class Ref,class Ptr>
struct list_iterator
{typedef list_node<T> Node; typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Self& operator++()//前置加加{_node = _node->_next;return *this;}Self operator++(int)//后置加加{Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& x)const{return _node != x._node;}bool operator==(const Self& x)const{return _node == x._node;}Ptr operator->(){return &(operator*());}
};

list类内部：

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

这样设计就可以只用一份代码来实现const和非const迭代器，但是这里实际上还是两份代码，因为模板会编译出两份。

有了迭代器插入和删除就好写了，这也是为什么可以O(1)插入的原因。

insert

iterator insert(iterator pos, const T& x)
{Node* _node = pos._node;Node* _prev = pos._node->_prev;Node* newnode = new Node(x);_prev->_next = newnode;newnode->_prev = _prev;_node->_prev = newnode;newnode->_next = _node;_sz++;return iterator(newnode);
}

erase

iterator erase(iterator pos)
{assert(pos != end());Node* _prev = pos._node->_prev;Node* _next = pos._node->_next;_prev->_next = _next;_next->_prev = _prev;delete pos._node;_sz--;return iterator(_next);
}

其余头插头删和尾插尾删均可以复用erase和insert。
完善一下其他函数

构造

list(const initializer_list<T>& x)
{empty_init();auto it = x.begin();while (it != x.end()){push_back(*it);it++;}}
list(const myspace::list<T>& x)
{empty_init();auto it = x.begin();while (it != x.end()){push_back(*it);++it;}
}
private:
void empty_init()
{
_head = new Node;_head->_prev = _head;_head->_next = _head;_sz = 0;
}

重载operator=

void swap(list<T>& x)
{std::swap(_head, x._head);std::swap(_sz, x._sz);
}
myspace::list<T>& operator=(const myspace::list<T>& x)
{list<T> tmp(x);swap(tmp);return *this;
}
myspace::list<T>& operator=(myspace::list<T>&& x)
{swap(x);return *this;
}

析构

void clear()
{iterator it = begin();while (it != end()){it = erase(it);it++;}_sz = 0;
}
~list()
{clear();delete _head;_head = nullptr;
}

写clear和empty_init主要是为了方便，不写也可以。

完整模拟

个人gitee

四、list的优缺点

和vector相对：
优点就是插入和删除效率很高，适合频繁插入和删除的场景，也不涉及扩容问题
缺点：1.不支持随机访问，访问元素是O(n)
2.底层空间不连续，缓存效率低，空间利用率低

五、总结

list的迭代器需要掌握，后面的map和set还会用到类似的思想。
还需要掌握vector和list的区别，可以从底层，随机访问，插入删除，空间，迭代器等场景来做对比。