C++《list》

在本篇当中我们将学习STL中的list，在此list就是我们之前在数据结构学习过的链表，在本篇中我们要来了解list当中的成员函数该如何使用，由于list各个函数的接口和之前学习过的vector类型，因此在学习list的使用就较为轻松。在lis篇章中我们要重点了解的是在下一个篇章当中的list模拟实现中的迭代器实现，由于list底层的物理空间不一定是连续的，因此list迭代器的实现相比之前学习过的容器就复杂多了，在下一篇中将带来细致的讲解。在此之前我们先来了解list该如何使用吧！！

---

1.构造函数

queue - C++ Reference

通过以上的文档所示就可以看出list类提供的构造函数接口和之前我们学习过的vector非常的相识，都实现了迭代器区间构造；n个指定元素的构造；使用initializer_list实现构造;拷贝构造

例如以下实现：

#include<iostream>
#include<list>
#include<string>
using namespace std;int main()
{string a("abcdef");list<int> lt1;list<int> lt2({ 1,2,3,4,5 });list<int> lt3(a.begin(), a.end());list<int> lt4(10, 9);list<int> lt5(lt2);return 0;
}

2.析构函数

queue - C++ Reference

在list类当中也实现了析构函数，在此该函数不需要我们在使用list时显示调用，这是由于析构函数编译器会在list对象销毁时自动调用

3.赋值运算符重载

list::operator= - C++ Reference

在list实现了赋值运算符重载的函数，这就使得将一个已经初始化的list对象赋值给另一个已经初始化的list对象

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1;list<int> lt2({ 1,2,3,4,5 });lt1 = lt2;return 0;
}

4. 容量操作

在list当中由于和之前学习的string、vector不同在存储数据时，每存储一个指定的元素就申请相应的对应合适的内存空间，因此在list就不会提前将空间开好，这就使得list当中容量操作相关的函数只有以下所示：

4.1 size

list::size - C++ Reference

在list提供了用于得到list对象内有效元素个数的成员函数size，到了这里你就可以了解到为什么之前在之前string当中得到有效元素建议使用size而不是length，这就使因为size在其他STL当中也是有提供的，而length只是string特有的，都使用size就利于记忆

4.2 empty

list::empty - C++ Reference

在list也提供用于判断list对象内有效元素是否为空的函数empty，当为空时就返回true，否则就为flase

5. 迭代器

在list类当中由于底层存储数据的内存空间不像string和vector一样物理结构是连续的，因此在list就没有提供下标+[ ]的方式实现对list对象内元素的访问，因此在list就只能使用迭代器来实现

在此list内的迭代器和之前学习过的容器一样也提供了普通迭代器和反向迭代器，并且在这些当中都实现了const和非const版本 

5.1 begin与end

list::begin - C++ Reference

在此list内提供的begin函数还是指向对象的第一个元素，返回值为迭代器

list::end - C++ Reference

在此list内提供的end函数还是指向对象的最后一个元素后一个位置，返回值为迭代器

有了begin()和end()就可以实现对list对象遍历，例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt2({ 1,2,3,4,5 });lt1 = lt2;list<int>::iterator t1 = lt1.begin();while (t1 != lt1.end()){(*t1)++;t1++;}t1 = lt1.begin();while (t1 != lt1.end()){cout << *t1 << " ";t1++;}cout << endl;return 0;
}

6.范围for

在此在list由于实现了迭代器那么就可以使用范围for来对list对象遍历其的元素

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1;lt1 = lt2;for (auto x : lt1){cout << x << " ";}cout << endl;return 0;
}

7.取头尾元素

list::front - C++ Reference

list::back - C++ Reference

在list提供了front函数和back函数来分别实现得到list对象内的首元素与尾元素 

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt2({ 1,2,3,4,5 });cout << "lt2front:" << lt2.front()<<endl;cout << "lt2back:" << lt2.back() << endl;return 0;
}

8.元素修改操作

在list当中提供了以上所示的各种用于修改list对象内元素的函数

8.1 push_front与pop_front

list::push_front - C++ Reference

list::pop_front - C++ Reference

 在list内实现了push_front和pop_front来放分别实现在对象内头插和头删元素
在此要了解到为什么在list会提供该函数而之前学习的string与vector都未实现该函数，这是由于在在链表当中头插和头删元素不需要像顺序表一样在头插和头删时将大量的元素移动，这样就不会出现效率低下的问题

8.2 push_back与pop_back

list::push_back - C++ Reference

 list::pop_back - C++ Reference

 在list内实现了push_back和pop_back来放分别实现在对象内尾插和尾删元素

8.3 insert和erase

list::insert - C++ Reference

list::erase - C++ Reference

在list也提供了inert和erase来实现任意位置的插入和删除，在此实现的接口和vector相识参数都是迭代器或者迭代器区间 

8.4 emplace_front与emplace_back

 list::emplace_front - C++ Reference

list::emplace_back - C++ Reference

在C++11之后实现了以上的两个函数emplace_front和emplace_back,那么这两个函数有什么作用呢？

在此你可以认为emplace_front和emplace_back与push_front和push_back的功能是类似的，功能分别是在list对象头插和尾插指定的数据，但其实这两个函数与push_front和push_back还是有差异的，接下来就来大体的讲解

注：在此emplace_front和emplace_back函数的参数涉及到可变模板参数、右值引用等概念在此不进行讲解，这些要到之后C++11篇章才进行

通过之前的学习我们知道push_front和push_back是可以实现在相应的类对象内插入内置类型的数据，也可以插入自定义类型的数据；并且在此支持隐式类型转换

例如以下示例：

#include<iostream>
#include<list>
using namespace std;class Postion
{
public:Postion(int row,int col):_row(row),_col(col){}private:int _row;int _col;
};int main()
{list<Postion> lt1;Postion p1(1,2);lt1.push_back(p1);//使用匿名对象lt1.push_back(Postion(1, 2));//使用多参数隐式类型转换lt1.push_back({ 1, 2 });return 0;
}

那么以上使用emplace_back不同的参数也可以使用吗

#include<iostream>
#include<list>
using namespace std;class Postion
{
public:Postion(int row,int col):_row(row),_col(col){}private:int _row;int _col;
};int main()
{list<Postion> lt1;Postion p1(1, 2);lt1.emplace_back(p1);lt1.emplace_back(Postion(1, 2));lt1emplace_back({ 1, 2 });return 0;
}

以上代码在VS下就会出现以下的编译报错，这是为什么呢？

 

要解决以上的问题就先了解到emplace_back的形参的类型是根据实参的类型来推导的，那么在以上使用隐式类型转换形参就无法根据实参{ 1, 2 }来推导具体的类型，这里具体的原因就是形参是模板

在此emplace_back和emplace_front最大的特点是支持直接将构造对象的参数直接传emplace_back和emplace_front函数的参数

因此以上代码正确的使用方法是如下所示：

#include<iostream>
#include<list>
using namespace std;class Postion
{
public:Postion(int row,int col):_row(row),_col(col){}
private:int _row;int _col;
};int main()
{list<Postion> lt1;Postion p1(1,2);lt1.push_back(p1);lt1.push_back(Postion(1, 2));lt1.push_back({ 1, 2 });list<Postion> lt1;Postion p1(1, 2);lt1.emplace_back(p1);lt1.emplace_back(Postion(1, 2));//lt.1emplace_back({ 1, 2 });lt1.emplace_back( 1, 2 );return 0;
}

注：在此由于emplace_back是直接构造去初始化节点，而push_back需要通过构造外加拷贝实现的，因此emplace_back相比push_back效率更高

9. list内特有的操作

在list中提供了以上特有的函数来实现逆置、排序等的操作，这些操作是之前我们在string和vector当中没有提供的，那么接下来我们就来了解这些函数的作用以及使用方法，但张这些函数其实在实践当中的使用频率非常少，因此我们只需要了解基本的使用方法即可

9.1 splice

list::splice - C++ Reference

在此splice的作用是将一个list对象的值转移给另一个list的对象，并且转移之后被转移对象会变为空

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> mylist1, mylist2;list<int>::iterator it;// set some initial values: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 30it = mylist1.begin();++it;                         // points to 2mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element)return 0;
}

再来看以下示例：

有一种LRU算法，即最近最少使用算法

在此有一个数组要将使用到的元素位置移到数组的头部，那么该如何实现呢？

在此就可以使用到splice函数来实现

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> a = { 1,2,3,4,5,6,7,8,9 };int x;while (cin >> x){auto found = find(a.begin(), a.end(), x);if (found != a.end()){a.splice(a.begin(), a, found);}for (auto x : a){cout << x << " ";}cout << '\n';}return 0;
}

9.2 remove

list::remove - C++ Reference

在此erase的作用是将list内的值为指定值的元素删除，可以认为remove是find和erase的结合体，在之前使用erase删除指定值的元素时要先使用find查找到相应迭代器的位置，再将相应的迭代器传给erase才能实现，而remove就可以直接实现以上的操作

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{int myints[] = { 17,89,7,14 };list<int> mylist(myints, myints + 4);mylist.remove(89);cout << "mylist contains:";for (auto x : mylist){cout << x << " ";}cout << '\n';return 0;
}

注：在此的remove_if涉及到仿函数，在此先不做讲解，到之后stack和queue再介绍仿函数是什么

9.3  merge

find - C++ Reference

在此在list内提供了merge来实现两个链表的归并，在此要求是两个链表是有序的才能进行归并，并且将一个list对象归并到另一个对象之后，这个list对象就为空了

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1({1,3,5,7,9});list<int> lt2;lt2.push_back(2);lt2.push_back(4);lt2.push_back(6);lt2.push_back(8);lt1.merge(lt2);//(lt2 is now empty)for (auto x : lt2){cout << x << " ";}cout << '\n';for (auto x : lt1){cout << x << " ";}cout << '\n';return 0;
}

9.4 unique

list::unique - C++ Reference

在此list提供了unique来实现去重，将list对象内重复的元素只保留一个其他重复的去除掉，在此前提list内的数据是有序的才能去去重

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1({ 1,2,3,3,3,5,7,8,9 });lt1.unique();for (auto x : lt1){cout << x << " ";}cout << '\n';return 0;
}

9.5 sort

list::sort - C++ Reference

在list还提供了对对象内元素进行排序的函数sort，在此sort默认排的是升序

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1;lt1.push_back(9);lt1.push_back(-2);lt1.push_back(3);lt1.push_back(-10);for (auto x : lt1){cout << x << " ";}cout << '\n';lt1.sort();for (auto x : lt1){cout << x << " ";}cout << '\n';return 0;
}

以上sort默认能实现升序是因为形象的缺省值默认是less，在此less是一个仿函数, 在此我们只要先了解到仿函数是一个类就可以了，能实现比较是由于在类内部实现了()的运算符重载，在之后的stack与queue章节将会详细讲解

在此使用sort时要实现降序就要使用另外的一个仿函数greater

例如以上示例要排成降序：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1;lt1.push_back(9);lt1.push_back(-2);lt1.push_back(3);lt1.push_back(-10);for (auto x : lt1){cout << x << " ";}cout << '\n';//使用匿名对象创建一个greater类型的对象作为sort的实参lt1.sort(greater<int>());for (auto x : lt1){cout << x << " ";}cout << '\n';return 0;
}

在此你可以会有一个疑惑，之前在vector当中要进行排序调用算法库内的sort就可以实现了，那么为什么在list内要单独实现一个sort，不是直接调用算法库内的就好了吗？

在此我们要了解的是之前是按照使用修改的角度将迭代器分为普通迭代器、const迭代器、反向迭代器、const反向迭代器，其实迭代器还可以从功能的角度分为单向迭代器、双向迭代器、随机迭代器

在此单向迭代器的特点是只支持++，双向迭代器的特点是只支持++和--，随机迭代器的特点是支持++、--还有+和-。经典的单向迭代器有一个叫做forward_list的容器，经典的双向迭代器有list，经典的随机迭代器有之前我们学习过的string、vector

在此提供算法库内的sort文档就可以看出该sort要传随机迭代器，这是由于算法库内的sort的底层是快速排序，这就需要支持随机访问，因此由于list不是随机迭代器因此就无法使用算法库内的sort

在此我们还要了解到的是以上的三种迭代器其实是继承的关系，由于我们还没有学习到C++中的继承也可以认为三种迭代器是以下所示的集合关系

那么在了解了以上的知识之后接下来看看list内的sort相比算法库内的sort效率如何呢？

在此我们通过以下两段代码来测试

先来看以下这段代码

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;void test_op1()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;vector<int> v;for (int i = 0; i < N; ++i){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();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}int main()
{test_op1();return 0;
}

以上代码输出结果如下所示：
在以上代码当中我们使用rand生成100万的整型数据分别存储在vector对象和list对象内，之后vector对象调用算法库内的sort进行排序，list使用其内部的成员函数sort进行排序，之后通过输出的结果就可以看出这两个sort的效率有什么差别

 通过输出结果就可以看出算法库内的sort要快不少

再来看以下代码：

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;void test_op2()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();// 拷贝vectorvector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}int main()
{test_op2();return 0;
}

你可能觉得第一段代码的结果还不够直观，那么就再来看以上的第二段代码，以上代码先比第一段代码的区别是一开始生成的100万个随机数是先存放在list对象内之后再拷贝给vector对象，再调用算法库内的sort进行排序。那么这种情况下是不是直接使用list内的sort效率会比拷贝再使用算法库内的sort效率要高呢？

接下来来看以上代码的输出结果：

通过以上的输出结果就可以看出先拷贝再使用算法库内的sort都比直接使用list内的sort效率要高，这就可以说明算法库内的sort是要比list内的sort要高效不少的。因此再之后要使用到大量数据的排序时最好使用vector

9.6 reverse

list::reverse - C++ Reference

 在list还提供了逆置list对象元素函数reverse

例如以下示例：

#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1;lt1.push_back(9);lt1.push_back(-2);lt1.push_back(3);lt1.push_back(-10);for (auto x : lt1){cout << x << " ";}cout << '\n';//lt1.sort(greater<int>());lt1.reverse();for (auto x : lt1){cout << x << " ";}cout << '\n';return 0;
}

以上就是本篇的全部内容了，接下来在下一篇当中将带来list的模拟实现，在模拟实现中我们将感受到list内的迭代器和之前学习的容器的具体不同，未完待续……