探索C/C++的奥秘之list

list和我们之前讲的东西都一样，list第二个参数是一个空间配置器，是一个内存池， 底层是一个带头双向循环列表。list可以重载[]，但是效率太低了。

list的遍历不能使用下标+[]，因为它的空间不是连续的，可以使用迭代器，也可以使用范围for。 

#include<iostream> #include<list> using namespace std; int main() {     list<int> lt;     lt.push_back(1);     lt.push_back(2);     lt.push_back(3);     lt.push_back(4);     list<int>::iterator it = lt.begin();     while (it != lt.end())     {         cout << *it << " ";         it++;     }     cout << endl;     for (auto e : lt)     {         cout << e << " ";     }     cout << endl;     return 0; }

1. list的介绍及使用

1.1 list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。list的头插和头删复杂度都为O(1)。

从string之后，position都变了，在string的部分都是用下标去插入，现在的位置都是迭代器，但是和vector还是有点区别的。比如下面的在第五个位置插入数据： 

int main() {     list<int> lt;     lt.push_back(1);     lt.push_back(2);     lt.push_back(3);     lt.push_back(4);     lt.push_front(10);     lt.push_front(20);     //如果要在第五个位置插入数据     //下面这种方法是不行的     //lt.insert(lt.begin() + 5, 10);     //因为vector是一个连续的物理空间，是支持+的，但是插入的代价比较大，数据要往后挪动。     //list和vector各有各的优缺点。     //list的物理空间不是连续的，可以支持+，但是代价比较大，库立面没有直接支持。     //只有一种方法     auto it = lt.begin();     for (size_t i = 0; i < 5; i++)     {         ++it;     }     lt.insert(it, 100);     for (auto e : lt)     {         cout << e << " ";     }     cout << endl;     return 0; }

这是vector和list的第一个差别，这种差别是迭代器的差别导致的，list的插入代价是很低的，把前后位置的指向关系改变一下就可以了，排序都写到算法里面去了。

还有一种插入的场景，就是找到一个值，在它的前面插入一个数据。list和vector都没有提供find接口。

对于vector来说用小于没有问题，但对于list来讲，迭代器中end()节点的地址不一定比begin()大， end()的节点是有效数据的下一个位置，也就是哨兵位。

list中的insert接口不存在迭代器失效的问题，比如我要在这个位置插入接点，没有扩容的问题，没有野指针的问题，没有位置改变的问题，因为不需要挪动数据。vector在这个位置插入之前有两大问题，第一大问题就是扩容，第二大问题就是插入这个数据之后，位置往后挪，它的位置意义都变了。

erase节点存在迭代器失效的问题，因为节点都没了。

算法中的find，找到就返回这个节点，找不到就返回end节点。

int main() {     list<int> lt;     lt.push_back(1);     lt.push_back(2);     lt.push_back(3);     lt.push_back(4);     lt.push_front(10);     lt.push_front(20);     auto it = lt.begin();     it = find(lt.begin(), lt.end(), 3);     if (it != lt.end())     {         lt.insert(it, 3);         *it *= 100;     }     for (auto e : lt)     {         cout << e << " ";     }     cout << endl;     it = find(lt.begin(), lt.end(), 3);     if (it != lt.end())     {         lt.insert(it, 30);         *it *= 100;     }     for (auto e : lt)     {         cout << e << " ";     }     cout << endl;     return 0; } 

如果是erase的话，程序就会崩溃：

int main() {     list<int> lt;     lt.push_back(1);     lt.push_back(2);     lt.push_back(3);     lt.push_back(4);     lt.push_front(10);     lt.push_front(20);     auto it = lt.begin();     it = find(lt.begin(), lt.end(), 3);     if (it != lt.end())     {         lt.insert(it, 3);         *it *= 100;     }     for (auto e : lt)     {         cout << e << " ";     }     cout << endl;     it = find(lt.begin(), lt.end(), 3);     if (it != lt.end())     {         lt.erase(it);         *it *= 100;     }     for (auto e : lt)     {         cout << e << " ";     }     cout << endl;     return 0; } 

如果要用erase删除list中的偶数：

int main() {     list<int> lt;     lt.push_back(1);     lt.push_back(2);     lt.push_back(3);     lt.push_back(4);     lt.push_front(10);     lt.push_front(20);     auto it = lt.begin();     //如果要用erase删除list中的偶数：     while (it != lt.end())     {         if (*it % 2 == 0)         {             it = lt.erase(it);         }         else         {             ++it;         }     }     for (auto e : lt)     {         cout << e << " ";     }     cout << endl;     return 0; }

 swap就是两个链表直接交换。

int main() {     list<int> lt1;     lt1.push_back(1);     lt1.push_back(2);     lt1.push_back(3);     lt1.push_back(4);     list<int> lt2;     lt2.push_back(10);     lt2.push_back(20);     lt2.push_back(30);     lt2.push_back(40);     for (auto e : lt1)     {         cout << e << " ";     }     cout << endl;     for (auto e : lt2)     {         cout << e << " ";     }     cout << endl;     lt1.swap(lt2);     for (auto e : lt1)     {         cout << e << " ";     }     cout << endl;     for (auto e : lt2)     {         cout << e << " ";     }     cout << endl;     return 0; }

容器都是通过迭代器区间去访问的，比如这有一个容器，想在这一段查找，给这个容器的区间查找这个val就可以了。

clear就是把我们的节点删掉等等这些情况。

list中sort的价值大不大，库里面也有一个sort，list中也提供了一个sort，有啥意义呢？编译报错了，有时候掉不调到库里面去了，就看这个库是谁的归属，那就是哪儿出错了，sort这个库用这个迭代器我们不能用，因为sort这个库里面用到一个

，就一个点我们就知道了，sort是快排，快排不能用这个东西，因为快排要做过参数取中，参数取中选其中一个值的时候，选中间那个值或者选另外一个值的时候，我直接要选那个位置，快排不适合，就是那个链表没办法适应这个场景。

所以大家仔细再看，如果我们单看算法，这些算法的名字有一些差异，他这个是函数模板，但是他在这个名字上面很有讲究，它的名字就暗示了应该传什么迭代器，这里就要迁移出一个知识讲一讲，然后再结合这这个说，迭代器从他的功能的角度是会分类的，从功能上来说，分为单向、双向、随机。功能上是什么呢？单向就只能++，双向可以++也可以--，随机是可以++、--、也可以+，也可以-。

 谁的迭代器就是典型的单向呢？单链表、哈希表。谁是双向迭代器呢？双向链表，其实也就是我们的list，还有map、set，也就是树。谁是随机迭代器呢？vector、string、双端队列deque。它这的名字就暗示了你用哪种算法，reverse就适合用双向，find就适合用单向，sort就适合用随机。这个地方对迭代器是一个隐式的分类，可以认为它是一个性质进行划分，这个性质跟容器的底层结构有关系。

 谁可以调用这个sort算法呢，这个sort底层是快排，决定了他要用这个随机迭代器，随机是可以吊的，链表就不可以调，链表这里调就报错了，用这个算法就要看容器的迭代器到底是哪一种，能不能适应，我怎么知道我的容器是哪一种呢？这里是有说明的，它的迭代器的内容是什么，vector和string可以用这个逆置，随机迭代器可以认为是一个特殊的双向迭代器，随机迭代器满足双向的要求，满足单向的要求，

，如果写这个，单向、双向、随机都可以用，写随机的就随机可以用，写双向的就双向、随机可以用，写单向的就单向、双向、随机都可以用。

set底层就是更复杂的迭代器，也就是树了，forward_list是单向迭代器，

 排序应该用vector，不应该用list，vector的效率远高于list，

 数据量越大，差距越大一些，list排序终究还是要慢不少。如果我们真的要数据排序，我们不应该用链表，链表访问数据相比vector毕竟还是慢，list底层用的是归并算法。所以说list的sort意义不大。

void test_op() {     srand(time(0));     const int N = 1000000;     vector<int> v;     v.reserve(N);     list<int> lt1;     //list<int> lt2;     for (int i = 0; i < N; ++i)     {         auto e = rand();         v.push_back(e);         lt1.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_op();     return 0; }

list的作用是当排序值比较小的时候，list排序才有价值。

void test_op() {     srand(time(0));     const int N = 100000;     vector<int> v;     v.reserve(N);     list<int> lt1;     list<int> lt2;     for (int i = 0; i < N; ++i)     {         auto e = rand();         lt2.push_back(e);         lt1.push_back(e);     }     // 拷贝到vector排序，排完以后再拷贝回来     int begin1 = clock();     // 先拷贝到vector     for (auto e : lt1)     {         v.push_back(e);     }     // 排序     sort(v.begin(), v.end());     // 拷贝回去     size_t i = 0;     for (auto& e : lt1)     {         e = v[i++];     }     int end1 = clock();     int begin2 = clock();     lt2.sort();     int end2 = clock();     printf("vector sort:%d\n", end1 - begin1);     printf("list sort:%d\n", end2 - begin2); } int main() {     test_op();     return 0; }

我们可以区分迭代器的类型，区分迭代器的类型有点复杂，叫做迭代器的萃取，就可以分辨出迭代器的类型。

merge就是连个链表可以直接进行归并，归并有一个前提就是先有序，两个链表要先sort再merge，这里还有另外一个东西叫仿函数，比较的仿函数的概念，仿函数在优先级队列再讲。

这个接口的本质是去重，去重也是有前提的，也是要先排序， 如果不排序去重的话效率是很低的。

remove就是find加erase，remove就是直接可以删。remove唯一要注意的是如果这个值不存在会不会报错？

void text_x() {     int myints[] = { 17,89,7,14 };     std::list<int> mylist(myints, myints + 4);     mylist.remove(890);     for (auto e : mylist)     {         cout << e << " ";     }     cout << endl; } int main() {     text_x();     return 0; }

相当于find，如果找到就删除了，没找到就啥也不干。 

remove_if 也涉及到一个仿函数的问题。

这个接口可以把一个链表的内容转移到另一个，它的转移是直接把节点拿走，就比如说有一个a链表，有一个b链表，直接把a链表的节点取下来直接插入到b链表，相当于a链表删除了数据，b链表插入了数据，严格来说就是发生了转移。也可以转移到自己身上，但是别把范围区间重叠了。

int main() {     int myints[] = { 17,89,7,14 };     std::list<int> mylist1, mylist2;     std::list<int>::iterator it;     for (int i = 1; i <= 4; ++i)         mylist1.push_back(i);      // mylist1: 1 2 3 4     for (int i = 1; i <= 3; ++i)         mylist2.push_back(i * 10);   // mylist2: 10 20 30     for (auto e : mylist1)     {         cout << e << " ";     }     cout << endl;     for (auto e : mylist2)     {         cout << e << " ";     }     cout << endl << endl;     it = mylist1.begin();     ++it;     // points to 2     //全部转移     //mylist1.splice(it, mylist2);     //转移一个     //mylist1.splice(it, mylist2, ++mylist2.begin());     //部分转移     //mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end());     //把后面的数据转移到第一个的前面     mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());     for (auto e : mylist1)     {         cout << e << " ";     }     cout << endl;     for (auto e : mylist2)     {         cout << e << " ";     }     cout << endl;     return 0; }