1. list
1.1 介绍
-
list是一种可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代； -
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立结点当中，在结点中通过指针指向其前一个元素和后一个元素； -
list与forward_list非常相似，最主要的不同在于forward_list是单链表，只能进行单方向迭代； -
与其他容器相比，list通常在任意位置进行插入、删除元素的执行效率更高； -
list和forward_list最大的缺陷是不支持在任意位置的随机访问，其次，list还需要一些额外的空间，以保存每个结点之间的关联信息（对于存储的类型较小元素来说这可能是一个重要的因素）。
1.2 常用接口的使用
使用STL的list需要包含头文件list
创建链表
构造一个空链表
list<int> lt1;
批量构造n个val的链表
list<int> lt2(10, 5);
拷贝构造
list<int> lt3(lt2);
list<int> lt3 = lt2;
区间构造
string s("hello world");
list<char> lt4(s.begin(),s.end());
数组构造
int arr[] = { 1, 2, 3, 4, 5 };
int sz = sizeof(arr) / sizeof(int);
list<int> lt5(arr, arr + sz);
插入和删除
push_back && push_front
pop_back && pop_front
#include <iostream>
#include <list>
using namespace std;
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test1()
{
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
list<int>::iterator it;
PrintList(ls);
ls.push_front(4);
ls.push_front(3);
ls.push_front(2);
ls.push_front(1);
PrintList(ls);
ls.pop_back();
ls.pop_back();
PrintList(ls);
ls.pop_front();
ls.pop_front();
PrintList(ls);
}
【输出】
1 2 3 4
1 2 3 4 1 2 3 4
1 2 3 4 1 2
3 4 1 2
insert
- 在指定pos位置插入一个值为val的结点；
- 在指定pos位置插入n个值为val的结点；
- 在指定pos位置插入一段迭代器区间围成的结点。
【注意】
- pos位置是迭代器位置；
- 插入迭代器区间的范围是左闭右开。
#include <iostream>
#include <list>
using namespace std;
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
lt.insert(pos, 99);
PrintList(lt);
pos = find(lt.begin(), lt.end(), 3);
lt.insert(pos, 2, 8);
PrintList(lt);
vector<int> v(2, 7);
pos = find(lt.begin(), lt.end(), 1);
lt.insert(pos, v.begin(), v.end());
PrintList(lt);
}
【输出】
1 99 2 3
1 99 2 8 8 3
7 7 1 99 2 8 8 3
1 2 3 4 5
在string和vector的学习中我们知道，find函数是作为通用接口内置在<algorithm>头文件中的。
erase
- 删除指定pos位置的结点；
- 删除迭代器区间围成的结点。
注意点同上。
#include <iostream>
#include <list>
using namespace std;
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
lt.erase(pos);
PrintList(lt);
pos = find(lt.begin(), lt.end(), 4);
lt.erase(pos, lt.end());
PrintList(lt);
}
【输出】
1 3 4 5
1 3
迭代器
begin && end
上面封装的打印函数就使用了迭代器。
void PrintList(const list<T>& l)
{
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
【注意】
这里必须使用!=作为判断的操作符，不能使用>或<，因为list和之前的string以及vector不一样，物理空间不是连续的。
反向迭代器的用法是一样的。
容量相关
size
void test4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
cout << lt.size() << endl;
}
【输出】
4
resize
- 当所给值大于当前的size时，将size扩大到该值，扩大的数据为第二个所给值，若未给出，则默认为容器所存储类型的默认构造函数所构造出来的值；
- 当所给值小于当前的size时，将size缩小到该值。
#include <iostream>
#include <list>
using namespace std;
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test5()
{
list<int> lt(5, 7);
PrintList(lt);
lt.resize(7, 6);
PrintList(lt);
lt.resize(2);
PrintList(lt);
}
【输出】
7 7 7 7 7
7 7 7 7 7 6 6
7 7
empty
void test6()
{
list<int> lt1;
lt1.push_back(1);
list<int> lt2;
cout << lt1.empty() << endl;
cout << lt2.empty() << endl;
}
【输出】
0
1
clear
void test7()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.clear();
cout << lt.empty() << endl;
}
【输出】
1
操作接口
sort
void test8()
{
list<int> lt;
lt.push_back(3);
lt.push_back(2);
lt.push_back(1);
lt.sort();
PrintList(lt);
}
【输出】
1 2 3
【注意】
虽然list内置了sort函数，但是它的效率比std::sort低。所以list内置的sort一般不使用。
虽然它们都是快排，list内置了sort的原因是：list的内存空间不是连续的，而库中sort效率高的主要原因也在于此，并且它还有三数取中的优化。
splice
用于两个list容器之间的拼接：
- 将整个容器拼接到另一个容器指定pos位置；
- 将容器中的某个结点拼接到另一个容器指定的pos位置；
- 将容器指定迭代器区间内的结点拼接到另一个容器指定pos位置。
void test9()
{
list<int> lt1(3, 2);
list<int> lt2(3, 6);
lt1.splice(lt1.begin(), lt2);
PrintList(lt1);
list<int> lt3(3, 3);
list<int> lt4(3, 7);
list<int>::iterator pos = ++lt3.begin();
lt3.splice(pos, lt4, lt4.begin());
PrintList(lt3);
list<int> lt5(3, 4);
list<int> lt6(3, 8);
lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end());
PrintList(lt5);
}
【输出】
6 6 6 2 2 2
3 7 3 3
8 8 8 4 4 4
【注意】
当一个容器作为新元素拼接到另一个容器以后，这个容器会被清空。个人觉得可以把splice理解为Transfers（转移）。
remove
void test10()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(4);
PrintList(lt);
lt.remove(2);
PrintList(lt);
}
【结果】
1 2 2 4
1 4
remove_if
bool func(int& val)
{
return val == 2;
}
void test11()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(4);
PrintList(lt);
lt.remove_if(func);
PrintList(lt);
}
【结果】
1 2 2 4
1 4
unique
void test12()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(4);
PrintList(lt);
lt.unique();
PrintList(lt);
}
【结果】
1 2 2 4
1 2 4
【注意】
如果想用这个接口达到去重的目的，且未知它是否有序，在使用unique接口之前必须对其排序。
merge
- 操作的对象是有序容器，然后将它们合并，类似归并排序。
void test13()
{
list<int> lt1;
lt1.push_back(3);
lt1.push_back(8);
lt1.push_back(1);
lt1.sort();
list<int> lt2;
lt2.push_back(6);
lt2.push_back(2);
lt2.push_back(9);
lt2.push_back(5);
lt2.sort();
lt1.merge(lt2);
PrintList(lt1);
}
【输出】
1 2 3 5 6 8 9
reverse
void test14()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
PrintList(lt);
lt.reverse();
PrintList(lt);
}
【输出】
1 2 3 4
4 3 2 1
assign
用于将新内容分配给容器，替换当前内容：
- 将n个值为val的结点分配给容器；
- 将迭代器区间范围内的结点分配给容器。
void test15()
{
list<char> lt(3, 'a');
lt.assign(3, 'b');
PrintList(lt);
string s("hello world");
lt.assign(s.begin(), s.end());
PrintList(lt);
}
【输出】
b b b
h e l l o w o r l d
swap
void test16()
{
list<int> lt1 = {1, 2, 3, 4};
list<int> lt2 = {5, 6, 7, 8};
lt1.swap(lt2);
PrintList(lt1);
PrintList(lt2);
}
【输出】
5 6 7 8
1 2 3 4
2. list的模拟实现
通过查看源码可以迅速了解list底层的框架。由于用C++实现list的方式和实现vector和string不太一样，且需要使用到许多C++的特性，所以下面给出实现list所需要的类和接口框架。
模拟实现的代码可以在这里获取。
namespace xy {
template<class T>
struct _list_node {
};
template<class T, class Ref, class Ptr>
struct _list_iterator {
typedef Ref reference;
typedef Ptr pointer;
typedef _list_node<T> Node;
Node* _node;
_list_iterator(Node* node)
: _node(node) {}
bool operator==(const iterator& it) const ;
}
bool operator!=(const iterator& it) const ;
}
reference operator*() ;
pointer operator->() ;
iterator& operator++() ;
iterator operator++(int) ;
iterator& operator--() ;
iterator operator--(int) ;
};
template<class T>
class list {
public:
typedef _list_node<T> Node;
list() ;
list(int n, const T& val = T()) ;
list(size_t n, const T& val = T()) ;
template<class Iterator>
list(Iterator begin, Iterator end) ;
list(list<T>& ls) ;
~list() ;
list<T>& operator=(list<T> ls) ;
public:
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
iterator begin() ;
iterator end() ;
const_iterator begin() const;
const_iterator end() const ;
T& front() ;
T& back() ;
const T& front() const ;
const T& back() const ;
iterator insert(iterator pos, const T& x) ;
void push_back(const T& x) ;
void push_front(const T& x) ;
void pop_back() ;
void pop_front() ;
void swap(list<int>& ls) ;
iterator erase(iterator pos) ;
void clear() ;
size_t size() ;
bool empty() ;
void resize(size_t newsize, const T& data = T());
private:
Node* _head;
void CreateHead() ;
};
}
可见，list的实现需要自定义三个类：
- 结点类：用于保存结点的位置和前后结点的地址；
- 迭代器类：用于定义各种类型的迭代器，以及对操作符的重载，以达到使用上无感的体验；
- list类：通过使用上面两个类以实现各种功能接口；以及保存结点。
所以要实现list，首先需要写好前两个类，然后在list类中吧各种接口写好。
2.1 结点类
list底层是以双链表的形式实现的（slist是单链表），每个结点需要储存的数据有：
-
成员变量：前驱指针，后驱指针，结点数据； -
成员函数：构造函数。
【注意】
- 结点的数据类型可以是任意类型，所以需要用到模板template；
- 这里的构造函数只是在实例化结点时，初始化这个结点中的成员变量，并不是“创建结点”（createNode）。
template<class T>
struct _list_node {
_list_node* _prev;
_list_node* _next;
T val;
_list_node(const T& x = T())
: _prev(nullptr), _next(nullptr), val(x) {}
};
关于为什么要用struct定义结点类，个人认为是历史包袱的原因，因为那时候C++还没有很好地支持一些语法。所以为了和底层统一，这里依然使用struct定义结点类。
这里的成员函数中给参数以缺省值= T()，这在学习vector中有接触过，目的是如果构造结点时未传入数据，那么就会调用T的默认构造函数：1.内置类型自动调用默认构造函数 2.自定义类型需要显式写默认构造函数。
2.2 迭代器类
这里仅实现正向迭代器。STL的接口大同小异，而学习list的迭代器就是本节的重点内容，因为那些操作接口我们在数据结构阶段已经用C语言实现过一遍了。
那为什么在学习string和vector的时候我们不着重学习它们的迭代器呢？
2.2.1 意义
迭代器，说白了就是访问数据结构的工具（index），它就像访问数组的下标。
就其本质而言，迭代器分为两种：
- 原生指针：例如在string类和vector中，使用的迭代器就是原生指针封装的，当然我们可以对迭代器解引用（*），自增或自减等操作。之所以可以用原生指针作为迭代器，是因为它们的内存空间都是连续的，使用指针非常自然；
- 封装：对于list这种内存空间不连续的容器，就不能再使用原生指针作为它的迭代器了。就拿++（自增）来说，如果对空间不连续的容器自增，那么非常有可能会出现野指针问题。以本节内容为例，对当前结点自增，也就是
node = node->next，一样可以达到自增的效果。
迭代器的意义：让使用者不必关系容器的底层实现，只需用简单统一的方式使用迭代器容器内的数据进行访问操作。
就本节而言，对迭代器的++，–，*，都是一个个被封装起来的函数，是对这些运算符进行的重载，使得结点指针的各种行为看起来就像原生指针一样。只是底层需要根据容器的特点而作出改变，各个容器的上层使用依然保持一致，这也是STL的精髓。
迭代器使用struct除了历史包袱的原因，还有就是struct的成员都是公有的，有时会访问成员的需要。
2.2.2 模板参数
首先先看源码中迭代器类的模板参数：
template<class T, class Ref, class Ptr>
再看迭代器类中定义的两个迭代器类型（普通和const）：
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
定义普通和const两种迭代器（iterator）是可以理解的，但是为什么模板参数里有三个参数呢？再看源码迭代器类中定义的部分：
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node;
}
看了下面的定义，我们可以知道迭代器类的模板参数中的Ref和Ptr分别代表引用类型和指针类型。
为什么要有三个模板参数：
我觉得大佬讲解的非常清楚，在第二点，绝不是我想偷懒。
简单地说，迭代器作为一个封装起来的类，不同类型的迭代器实例化出来的迭代器对象的类型也会随之不同（const和普通），如果不定义三个（其实除了T，至少有一个能区分就行）模板参数，那么编译器就没办法区别普通迭代器和const迭代器。
如何能让编译器识别不同的迭代器？
- 定义不同类型的迭代器类，这样虽然解决问题，但是迭代器的内容很多都是一样的；
- 使用多个模板参数控制迭代器类型。
不需要重新写一个const迭代器类，因为返回值的类型不是构成重载的条件。
typedef _list_iterator<T, Ref, Ptr> Self;
typedef Ref reference;
typedef Ptr pointer;
typedef _list_node<T> Node;
2.2.3 结点的定义
typedef _list_node<T> Node;
Node* _node;
2.2.4 迭代器的构造函数
_list_iterator(Node* node)
: _node(node) {}
2.2.5 运算符的重载
!= && ==
bool operator==(const Self& it) const {
return _node == it._node;
}
bool operator!=(const Self& it) const {
return _node != it._node;
}
operator*
reference operator*() {
return _node->val;
}
operator->
pointer operator->() {
return &(operator*());
}
在之前，我们什么时候会用到->操作符？
- 当我们像访问自定义类型成员变量的时候。就像之前我们实现过的Student学生结构体一样。
- 回应刚才的话题，使用结构体定义结点类的一个原因就是它默认所有成员都是公有的，而
->操作符也必须要求成员变量是公有的。
对于->运算符重载，我们只需要返回结点的数据的地址，但其中的细节我们必须知道：
对于operator->，它的返回值是&(operator*())把里面的operator*()替换，也就是&(_node->val)，那么operator->就是&(_node->val)。
举个例子，对于Node结点，通过->访问它里面的结点，那么语句是这样的：Node->val，但是如果把这个->换成上面的内容，就是这样的：Node->&(_node->val)，这里就会多出来一个->。实际上本来就是两个->，只是如果真的这样写的话，可读性不好，编译器优化为一个->。
自增 && 自减
Self& operator++() {
_node = _node->_next;
return *this;
}
Self operator++(int) {
Self ret(*this);
_node = _node->_next;
return ret;
}
Self& operator--() {
_node = _node->_prev;
return *this;
}
Self operator--(int) {
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
- 前置：直接返回下一个结点的地址；
- 后置：先保存当前结点的地址ret，更新结点地址后再返回ret。
2.3 list类
2.3.1 定义结点
template<class T>
class list {
public:
typedef _list_node<T> Node;
private:
Node* _head;
void CreateHead() {
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
};
list类同样要用template模板，以保证能正常定义任何数据类型的结点，而且list类中要使用迭代器的，迭代器的实现也使用了模板。
由于是双向带头循环链表，定义结点指针作为私有成员变量，指向头结点。所以初始化的链表头尾指针都指向自己。这个功能单独封装为CreateHead函数，因为在类的外部不需要访问到CreateHead函数，所以把它作为私有成员函数。
2.3.2 构造函数
无参构造
list() {
CreateHead();
}
批量构造
list(int n, const T& val = T()) {
CreateHead();
for (int i = 0; i < n; ++i)
push_back(val);
}
迭代器区间构造
template<class Iterator>
list(Iterator begin, Iterator end) {
CreateHead();
while (begin != end) {
push_back(*begin);
begin++;
}
}
拷贝构造
首先创建一个头结点，遍历原来的容器中的元素，将每一个元素的值尾插到新容器中。
list(list<T>& ls) {
CreateHead();
list<T> tmp(ls.begin(), ls.end());
swap(tmp);
}
重载operator=
如果不使用引用接收参数，编译器就会自动调用list的拷贝构造函数构造出来一个list对象，然后调用swap函数将原容器与该list对象进行交换。相当于编译器自己帮我们隐式地拷贝了一个临时对象ls（好像老板）。
这个函数被销毁时，ls作为临时对象会调用它的析构函数。
list<T>& operator=(list<T> ls) {
swap(ls);
return *this;
}
2.3.3 析构函数
首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空。
~list() {
clear();
delete _head;
_head = nullptr;
}
- 这里的clear()是批量删除所有元素的接口，稍后会实现。
2.3.4 迭代器相关
begin && end
首先要注意，迭代器区间（begin和end围成的范围）都是左闭右开的。所以begin函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。
那么对于这个双向带头循环链表而言，头结点的上一个结点就是最后一个结点，最后一个结点的下一个结点就是头结点。
iterator begin() {
return iterator(_head->_next);
}
iterator end() {
return iterator(_head);
}
const_iterator begin() const {
return const_iterator(_head->_next);
}
const_iterator end() const {
return const_iterator(_head);
}
- 第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。
2.3.5 访问容器
front && back
返回第一个有效数据和最后一个有效数据的引用。
T& front() {
return _head->val;
}
T& back() {
return _head->_prev->val;
}
const T& front() const {
return _head->val;
}
const T& back() const {
return _head->_prev->val;
}
2.3.6 插入和删除
insert
先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，然后根据所给数据x构造一个待插入结点，之后再建立新结点与cur之间的双向关系，最后建立新结点与prev之间的双向关系。
iterator insert(iterator pos, const T& x) {
assert(pos._node);
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
erase
先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系。
iterator erase(iterator pos) {
Node* delNode = pos._node;
Node* retNode = delNode->_next;
delNode->_prev->_next = delNode->_next;
delNode->_next->_prev = delNode->_prev;
delete delNode;
delNode = nullptr;
return retNode;
}
clear
void clear() {
Node* cur = _head->_next;
while (cur != _head) {
_head->_next = cur->_next;
delete cur;
cur = _head->_next;
}
_head->_next = _head->_prev = _head;
}
push_front && pop_front
- 头插：在第一个有效节点前插入新结点；
- 头删：删除第一个有效结点。
void push_front(const T& x) {
insert(begin(), x);
}
void pop_front() {
erase(begin());
}
push_back && pop_back
- 尾插：在头结点前插入结点；
- 尾删：删除头结点的前一个结点。
void push_back(const T& x) {
insert(end(), x);
}
void pop_back() {
erase(--end());
}
2.3.7 容量相关
empty
bool empty() {
return begin() == end();
}
resize
- 当所给值大于当前的size时，将size扩大到该值，扩大的数据为第二个所给值，若未给出，则默认为容器所存储类型的默认构造函数所构造出来的值；
- 当所给值小于当前的size时，将size缩小到该值。
实现resize函数时，不要直接调用size函数获取当前容器的有效数据个数，因为当调用size函数后就已经遍历了一次容器了，而如果结果是size大于newsize，那么还需要遍历容器，找到第newsize个有效结点并释放之后的结点。
void resize(size_t newsize, const T& data = T()) {
size_t oldsize = size();
if (newsize <= oldsize) {
while (newsize < oldsize) {
pop_back();
oldsize--;
}
}
else {
while (oldsize < newsize) {
push_back(data);
oldsize++;
}
}
}
2.3.8 其他
swap
void swap(list<int>& ls) {
std::swap(ls._head, _head);
}
size
size_t size() {
size_t count = 0;
iterator it = begin();
while (it != end()) {
count++;
it++;
}
return count;
}
PrintList
此函数STL中并没有，只是为了测试方便。但注意参数中的const有测试意义：对应上面迭代器类的中多个模板参数，如果只有一个模板参数，这里加上const后编译器是无法编译成功的。
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
- 引用是为了提高效率，避免深拷贝；
- const是为了防止原来的容器内容被修改。
|