当前位置:首页 » 《资源分享》 » 正文

【C++】—— list 的了解与使用

22 人参与  2024年09月15日 09:21  分类 : 《资源分享》  评论

点击全文阅读


【C++】—— list 的了解与使用

1 list 的函数接口2 迭代器2.1 简单使用 list 的迭代器2.2 迭代器的划分2.3 不同迭代器的使用场景2.3.1 sort2.3.2 reverse2.3.3 find 3 emplace_back4 操作函数4.1 sort4.1.1 list中sort介绍4.1.2 list 中 sort 与算法库中 sort 效率比较 4.2 merge4.3 unique4.4 remove4.5 splice

1 list 的函数接口

  STL库中的 l i s t list list,其底层是一个带头双向循环链表

  STL库 的容器都有很强的相似性,我们有了前面 s t r i n g string string、 v e c t o r vector vector 的基础,再来学习 l i s t list list 就会轻松很多。
  我把 l i s t list list 的函数接口放出来,相信都加看一眼就知道如何使用了。

在这里插入图片描述

成员函数

在这里插入图片描述

迭代器

在这里插入图片描述

容量

在这里插入图片描述

元素访问

在这里插入图片描述

修改

  上述接口我们都很熟悉了,本文就不再一一进行介绍,大家自行查阅文档即可


  但是关于操作的接口我们还比较陌生,等下我们会一一学习

在这里插入图片描述

操作

  
  

2 迭代器

2.1 简单使用 list 的迭代器

  我们先来简单使用一下 l i s t list list 的迭代器

void test1(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << endl;++it;}}

运行结果:

在这里插入图片描述

  可以看到, l i s t list list 的迭代器访问和 s t r i n g string string、 v e c t o r vector vector 等是一样的。

  那么 l i s t list list 的迭代器可不可以使用 + 呢?

l1.insert(l1.begin() + 3, 10);

不可以的!

  那既然不可以直接 +3,我们想在第三个位置之前插入数据怎么办呢?

方法如下:

void test1(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);auto it = l1.begin();int k = 3;while (k--){++it;}l1.insert(it, 10);for (auto e : l1){cout << e << " ";}cout << endl;}

运行结果:

在这里插入图片描述

  
  

2.2 迭代器的划分

  这里,我先来给大家介绍一下迭代器的划分

从功能上进行划分

iteratorreverse_iteratorconst_iteratorconst_reverse_iterator

从性质上进行划分

单向迭代器: f o r w a d forwad forwad l i s t list list / u n o r d e r e d unordered unordered m a p map map / u n o r d e r e d unordered unordered_ s e t set set 等为单向迭代器。他们只支持 ++。双向迭代器: l i s t list list / m a p map map / s e t set set 等都是双向迭代器。他们支持++/–,但不支持+/-。随机迭代器: v e c t o r vector vector / s t r i n g string string / d e q u e deque deque 等都是随机迭代器。他们支持++/–/+/-。 决定迭代器的性质的是容器的底层结构。

   l i s t list list 的迭代器是一个双向迭代器

在这里插入图片描述

  
  

2.3 不同迭代器的使用场景

  决定迭代器的性质的是容器的底层结构。而底层结构也决定了容器可以使用那些算法
  

2.3.1 sort

在这里插入图片描述

  用 s o r t sort sort 算法进行排序,并不是传什么迭代器都可以的,必须传随机迭代器,否则就会报错。
  为什么呢?因为 s o r t sort sort 底层是快速排序。快排里面要做类似三数取中的东西,它需要支持随机访问。
  

2.3.2 reverse

在这里插入图片描述

   r e v e r s e reverse reverse 是将指定范围内的数据进行翻转。

在这里插入图片描述

  这个算法底层用了 '-'操作符,因此要传双向迭代器

  那 v e c t o r vector vector、 s t r i n g string string 这些随机迭代器能用逆置算法吗?
  肯定能。因为他们功能上是一个包含的关系,双向是一种特殊的单向,随机是一种特殊的双向
  

2.3.3 find

在这里插入图片描述

  那 f i n d find find 算法又需传递什么迭代器呢?
  InputIterator 是什么迭代器呢?它不是单向,双向,随机种的任意一种

这里我们再简单介绍一下:

在这里插入图片描述

  库里面对迭代器性质的定义使用了 C++ 中继承的概念,继承就是子类是一个特殊的父类,所以它认为这里的单向、双向、随机是一个继承关系随机是一个特殊的双向 ,双向是一个特殊的单向
  同时,库中引申出了两个不存在的迭代器只读和只写迭代器(严格来说没有容器的迭代器类型对应这两类,是抽象的概念)。InputIterator迭代器 意味着单向、双向、随机都是其子类。
  出现InputIterator就说明可以给任意类型的迭代器
  
  这里因为 f i n d find find 底层只用了 ++

在这里插入图片描述

  
  

3 emplace_back

  现阶段,我们可以认为 push_backemplace_back 是一样的,都是尾插一个数据

void test2(){list<int> l1;l1.emplace_back(1);l1.emplace_back(2);l1.emplace_back(3);l1.emplace_back(4);l1.emplace_back(5);list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << endl;++it;}}

运行结果:

在这里插入图片描述

  但是在用法上,如果插入数据的参数是多个的,emplace_back效率会高一些
  
假设我们现在要插入自定义类型 A

struct A{A(int a1 = 1, int a2 = 1):_a1(a1),_a2(a2){}int _a1;int _a2;};

  

对应插入自定义类型 A 有两种常见的方法

插入有名对象插入匿名对象
void test3(){list<A> lt;A aa1(1, 1);lt.push_back(aa1);lt.push_back(A(2, 2));lt.emplace_back(aa1);lt.emplace_back(A(3, 3));}

  这两种方式 p u s h push push b a c k back back 和 e m p l a c e emplace emplace b a c k back back 都支持
  
  但是 emplace_back 还支持这样写:

void test4(){list<A> lt;lt.emplace_back(3, 3);}

   e m p l a c e emplace emplace_ b a c k back back 支持直接传构造 A 的参数。
  这里不是隐式类型转换,现阶段我们先不管其底层,学会用法即可。
  
  

4 操作函数

4.1 sort

4.1.1 list中sort介绍

在这里插入图片描述

  我们前面看到,算法库中的 sort 要求是随机迭代器, l i s t list list 的迭代器并不符合,因此它自己实现了一个排序算法。和算法库中的 s o r t sort sort 一样, l i s t list list 中的 s o r t sort sort 排序默认排的是升序,如果要排降序则要用到仿函数(后面会讲)。
   l i s t list list 实现的 s o r t sort sort 底层用的是归并排序,而算法库中的 s o r t sort sort 底层用的是快速排序

void test5(){list<int> lt;lt.push_back(3);lt.push_back(5);lt.push_back(4);lt.push_back(1);lt.push_back(2);lt.sort();for (auto e : lt){cout << e << " ";}cout << endl;lt.sort(greater<int>());for (auto e : lt){cout << e << " ";}cout << endl;}

运行结果:

在这里插入图片描述

  

4.1.2 list 中 sort 与算法库中 sort 效率比较

  虽然 l i s t list list 中实现了 s o r t sort sort 排序算法,但是它的排序效率很低,尽量不要用它来排序。

  我们将他与算法库中的 s o r t sort sort 进行性能对比

我们产生 1000000 个相同的数,放进 v e c t o r vector vector 和 l i s t list list 中,再分别用算法库中 s o r t sort sort,和 l i s t list list 中 s o r t sort sort 排序,看运行时间
void test10(){srand(time(0));const int N = 1000000;list<int> lt1;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);}

运行结果:

在这里插入图片描述

  差距 2 倍多

这一次我们用两个链表进行排序:一个链表将数据拷贝进 v e c t o r vector vector,用库中的 s o r t sort sort 排序,后再拷贝回来;另一个直接调用 l i s t list list 中的 s o r t sort sort
void test11(){srand(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();// 拷贝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);}

  


  上述代码用了 l i s t list list 中的 a s s i g n assign assign 接口,我们简单介绍一下

在这里插入图片描述

   a s s g i n assgin assgin 功能是用一段迭代器区间对调用函数的 l i s t list list 对象进行拷贝,任何容器的迭代器都可以。像 v e c t o r vector vector 等都有 a s s g i n assgin assgin 接口

运行结果:

在这里插入图片描述

  可以看到,即使多了两次拷贝,依然是算法库中的 sort 效率更高。同时这也说明了拷贝的代价其实是很低的
  

4.2 merge

在这里插入图片描述

   m e r g e merge merge 接口的功能是:将两个链表合并。合并的前提是两个链表是有序的。

void test6(){std::list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);first.sort();second.sort();first.merge(second);for (auto e : first){cout << e << endl;}}

运行结果:

在这里插入图片描述

  需要注意:合并会让其中一个链表空掉。
  其底层是创建一个新链表,依次去两个链表中小的尾插,最后再将新链表与first链表进行交换。

  

4.3 unique

在这里插入图片描述

   u n i q u e unique unique 是一个去重接口,但它要求数据必须是有序的

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

运行结果:

在这里插入图片描述

  

4.4 remove

在这里插入图片描述

   r e m o v e remove remove 接口是对一个值进行删除,他和 e r a s e erase erase 有点像。不同的是 e r a s e erase erase 是传一个迭代器; r e m o v e remove remove 是传一个,我找到了我就删,没找到也不会报错

  

4.5 splice

在这里插入图片描述

   s p l i c e splice splice 是粘贴的意思,但这函数接口功能更像剪切
   s p l i c e splice splice 的功能本质是一种转移:将 x x x 链表中的元素转移到调用该函数的 p o s i t i o n position position 位置之前(是转移不是粘贴)
  
实例:将 m y l i s t 2 mylist2 mylist2 数据转移到 m y l i s t 1 mylist1 mylist1 中 2 的前面

void test8(){std::list<int> mylist1, mylist2;std::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)cout << "mylist1:";for (auto e : mylist1){cout << e << " ";}cout << endl;cout << "mylist2:";for (auto e : mylist2){cout << e << " ";}cout << endl;}

运行结果:

在这里插入图片描述

  
   s p l i c e splice splice 还有以下用法:调整当前链表节点的顺序
  比如我想将第一个链表中的 5 放在第一个,怎么做呢

void test9(){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);}

  第一种方法就是将 5 这个节点删除,再进行头插。但这一来一去又是删除又是 n e w new new 的,效率较低。
  我们还有一种方法:运用 splice 接口。 s p l i c e splice splice 允许自己转移给自己。

void test9(){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);list<int>::iterator it = find(lt.begin(), lt.end(), 5);if (it != lt.end()){lt.splice(lt.begin(), lt, it);}for (auto e : lt){cout << e << " ";}cout << endl;}

运行结果:

在这里插入图片描述

  
  不仅如此,我们函转移一段范围

list<int>::iterator it = find(lt.begin(), lt.end(), 4);if (it != lt.end()){lt.splice(++lt.begin(), lt, it, lt.end());}

运行结果:

在这里插入图片描述

  
  
  
  
  


  好啦,本期关于 l i s t list list 的知识就介绍到这里啦,希望本期博客能对你有所帮助。同时,如果有错误的地方请多多指正,让我们在 C++ 的学习路上一起进步!


点击全文阅读


本文链接:http://zhangshiyu.com/post/160138.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1