【C++】list容器的基本使用

一、list是什么

list的底层结构是带头双向循环链表。

相较于 vector 的连续线性空间，list 就显得复杂很多，它是由一个个结点构成，每个结点申请的空间并不是连续的，它的好处是每次插入或删除一个数据，就配置或释放一个元素空间，我们不用在意扩容问题了，也不用单独写扩容函数了，list对于任何位置的元素进行插入或者元素移除，时间复杂度都是O(1)。

二、list容器的基本使用

1、构造函数

这里的allocator是空间配置器，我们这里先不用管它(认为它不存在)，等到后面的篇章会具体讲解它的作用。其中，(1)是默认构造 (2)是n个val构造 (3)是迭代器区间构造 (4)是拷贝构造。

2、析构函数

释放每个结点申请的空间资源。

3、赋值重载

它的操作数是两个已有的list对象。

4、迭代器

(1)使用

list的迭代器和vector的迭代器在用法上一模一样。

使用迭代器可以进行遍历：

#include <iostream>
#include <list>
using namespace std;void test_list1()
{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 it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}int main()
{test_list1();return 0;
}

运行结果：

支持迭代器，就支持范围for，因为范围for的底层就是迭代器。

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout << e << " ";}cout << endl;
}int main()
{test_list1();return 0;
}

运行结果：

(2)分类

迭代器从功能上进行分类，分为iterator、const_iterator、reverse_iterator、const_reverse_iterator这四类，它还可以从性质上进行分类，分为单向迭代器、双向迭代器、随机迭代器。

单向迭代器包括(forward)：forward_list / unordered_map... 它只支持++

双向迭代器(bidirectional)包括：list / map / set... 它只支持++ / --

随机迭代器(random access)包括：vector / string / deque... 它支持++ / -- / + / -

它们的底层结构决定它们的性质，它们的底层结构也决定它们可以使用哪些算法。

比如：

C++标准库中sort的模板参数是RandomAccessIterator，从它的名字中可以看出它只接收随机迭代器，如果传一个单向迭代器，它也可以接收，但运行时会发生错误即程序不能正常运行。

C++标准库中reverse的模板参数是BidirectionalIterator，从它的名字中可以看出它只接收双向迭代器，如果传一个单向迭代器，它也可以接收，但运行时会发生错误即程序不能正常运行。如果传一个随机迭代器，也可以正常使用，因为随机迭代器的范围更广，凡是支持单向迭代器或者双向迭代器的都支持随即迭代器。

出现InputIterator，说明单向/双向/随机迭代器都可以使用这个函数。

5、成员函数

(1)empty()

判断容器内节点个数是否为空，若为空返回true，否则返回false。

(2)size()

返回容器内节点个数。

(3)front()

reference 就是list<T>中的T，T是模板参数。front就是用来返回第一个结点的值。

(4)back()

返回最后一个结点的值。

(5)assign()

用于赋值。(1)是用一段迭代区间赋值 (2)是用n个val赋值

(6)push_front()

头插，头部插入一个新结点。

(7)pop_front()

头删，删除头部的结点。

(8)push_back()

尾插，尾部插入一个新结点。

(9)pop_back()

尾删，删除尾部的结点。

(10)emplace_back()

它的功能和push_back()差不多，但有不同之处，现阶段我们就把它当作push_back()使用。

struct AA
{AA(int a1, int a2):_a1(a1), _a2(a2){}
private:int _a1;int _a2;
};void test_list2()
{list<AA> lt;AA aa1(1, 1);lt.push_back(aa1);lt.push_back(AA(2,2));//lt.push_back(3,3); //err，这里会报错lt.emplace_back(aa1);lt.emplace_back(AA(2,2));lt.emplace_back(3,3); //ok,与push_back()的不同之处，它支持直接传构造A对象的参数
}int main()
{test_list2();return 0;
}

(10)insert()

(1)是在pos位置前插入val (2)是在pos位置前插入n个val (3)是在pos位置前插入一段迭代区间。

void test_list3()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;//在第3个位置前(整体位置是从0开始编号的)插入30//lt.insert(lt.begin() + 3, 30); //list容器不支持+,所以这行代码会报错list<int>::iterator it = lt.begin();int k = 3;while (k--){++it;//list容器支持++,所以这行代码会报错}lt.insert(it, 30);  //(1)for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list3();return 0;
}

运行结果：

(11)erase()

(1)删除pos位置上的值 (2)删除一段迭代区间

void test_list4()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;int x;cin >> x;list<int>::iterator it = find(lt.begin(),lt.end(),x);if (it != lt.end()) //找到了lt.erase(it); //(1)elsecout << "不存在:" << x << endl;for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list4();return 0;
}

输入4，运行结果：

(12)clear()

清空所有结点数据。

(13)resize()

将结点个数更新到n，假设原先节点个数为k。

1、k > n

释放k - n个结点

2、k < n

增加n - k个节点，结点中的内容自己可以传，也可以不传，用默认的缺省值。

因为list的底层是链表，所以没有扩容这一说法。

(14)reverse()

逆置结点的顺序。

void test_list5()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;lt.reverse();for (auto e : lt)cout << e << " ";cout << endl;//reverse(lt.begin(),lt.end()); //这里的算法库中的reverse也支持list容器的逆置
}int main()
{test_list5();return 0;
}

运行结果：

(15)sort()

由于算法库中的sort不支持list容器的迭代器，所以这里它自己实现了一个。

void test_list6()
{list<int> lt;lt.push_back(20);lt.push_back(40);lt.push_back(50);lt.push_back(30);lt.push_back(10);for (auto e : lt)cout << e << " ";cout << endl;//默认排升序lt.sort(); //(1)for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list6();return 0;
}

运行结果：

如果想要排降序，就要借助仿函数：

void test_list6()
{list<int> lt;lt.push_back(20);lt.push_back(40);lt.push_back(50);lt.push_back(30);lt.push_back(10);for (auto e : lt)cout << e << " ";cout << endl;//排降序greater<int> gt;lt.sort(gt);for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list6();return 0;
}

运行结果：

(16)merge()

合并两个链表，前提是这两个链表需要有序。

void test_list7()
{list<int> first, second;first.push_back(3);first.push_back(6);first.push_back(1);second.push_back(2);second.push_back(5);second.push_back(4);first.sort();second.sort();first.merge(second); //合并后，second这个链表就空了，相当于将它移到first上了for (auto e : first)cout << e << " ";cout << endl;cout << "----------" << endl;for (auto e : second) //second中已经没有数据了cout << e << " ";cout << endl;cout << "----------" << endl;
}int main()
{test_list7();return 0;
}

运行结果：

(17)unique()

去重，删除容器中与val值一样的结点，只保留第一个。删除时要保证重复的数据紧挨着，否则会删不干净，建议删除前先排序。

void test_list8()
{list<int> lt;lt.push_back(5);lt.push_back(1);lt.push_back(4);lt.push_back(2);lt.push_back(4);lt.push_back(3);lt.push_back(3);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;lt.sort();lt.unique();for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list8();return 0;
}

运行结果：

(18)remove()

对val进行查找，如果找到就删除，否则什么也不做。

(19)remove_if()

给定一个条件，如果满足就删除，否则什么也不做。

(20)splice()

(1)是将x中全部结点转移到当前容器中的pos位置之前的位置处 (2)是将x中i位置的结点转移到当前容器中的pos位置之前的位置处 (3)是将x中的一段迭代区间上的结点转移到当前容器中的pos位置之前的位置处

//将一个链表的结点转移给另一个链表
void test_list9()
{list<int> mylist1, mylist2;list<int>::iterator it;//先插入一些值for (int i = 1; i <= 4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10);   // mylist2: 10 20 30cout << "初始值：" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;it = mylist1.begin();++it;                     mylist1.splice(it, mylist2); //(1)// mylist1: 1 10 20 30 2 3 4// mylist2中的数据已经没有了// "it" 仍然指向2 cout << "第一次调用splice后：" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;mylist2.splice(mylist2.begin(), mylist1, it); //(2)// mylist1: 1 10 20 30 3 4// mylist2: 2// "it"现在是无效的cout << "第二次调用splice后：" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;
}int main()
{test_list9();return 0;
}

运行结果：

根据它的功能，我们还可以调整当前链表的结点顺序：

//调整当前链表结点的顺序
void test_list10()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);cout << "转移前:" << endl;for (auto e : lt)cout << e << " ";cout << endl;//现要求将6这个结点转移到1这个结点的前面去lt.splice(lt.begin(), lt, --lt.end());cout << "转移后:" << endl;for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list10();return 0;
}

三、排序效率

这里我们将list容器中的sort与算法库中的sort进行效率对比，看看哪个更优。

(1)对比一

#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;void test_op1()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;vector<int> v;for (int i = 0;i < N;++i) //随机生成100万个数据{auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();cout << "vector sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op1();return 0;
}

在Debug环境下的运行结果：

可以看到list排序优势更大，那是因为在Debug环境下，优化不是很大，运行结果不具有参考价值，在release环境下，双方优化都是最大的，这才公平。

在Realse环境下运行结果：

实际上，算法库中的sort效率是更好的。

(2)对比二

#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;void test_op2()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0;i < N;++i){auto e = rand() + i;lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();vector<int> v(lt2.begin(), lt2.end()); //迭代器区间构造sort(v.begin(), v.end()); //用算法库中的sort进行排序lt2.assign(v.begin(), v.end()); //再拷贝回lt2int end1 = clock();int begin2 = clock();lt1.sort(); //直接调用list中的sort进行排序int end2 = clock();cout << "list copy vector sort copy list sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op2();return 0;
}

在Release环境下运行结果：