0


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

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

1 list 的函数接口

  STL库中的

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list,其底层是一个
  1. 带头双向循环链表

  STL库 的容器都有很强的相似性,我们有了前面

  1. s
  2. t
  3. r
  4. i
  5. n
  6. g
  7. string
  8. string
  9. v
  10. e
  11. c
  12. t
  13. o
  14. r
  15. vector
  16. vector 的基础,再来学习
  17. l
  18. i
  19. s
  20. t
  21. list
  22. list 就会轻松很多。

  我把

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 的函数接口放出来,相信都加看一眼就知道如何使用了。

在这里插入图片描述
成员函数

在这里插入图片描述
迭代器

在这里插入图片描述
容量

在这里插入图片描述
元素访问

在这里插入图片描述
修改

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


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

在这里插入图片描述
操作

2 迭代器

2.1 简单使用 list 的迭代器

  我们先来简单使用一下

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 的迭代器
  1. voidtest1(){
  2. list<int> l1;
  3. l1.push_back(1);
  4. l1.push_back(2);
  5. l1.push_back(3);
  6. l1.push_back(4);
  7. l1.push_back(5);
  8. list<int>::iterator it = l1.begin();while(it != l1.end()){
  9. cout <<*it << endl;++it;}}

运行结果:

在这里插入图片描述

  可以看到,

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 的迭代器访问和
  7. s
  8. t
  9. r
  10. i
  11. n
  12. g
  13. string
  14. string
  15. v
  16. e
  17. c
  18. t
  19. o
  20. r
  21. vector
  22. vector 等是一样的。

  那么

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 的迭代器可不可以使用 + 呢?
  1. l1.insert(l1.begin()+3,10);

不可以的!

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

方法如下:

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

运行结果:

在这里插入图片描述

2.2 迭代器的划分

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

从功能上进行划分

  • iterator
  • reverse_iterator
  • const_iterator
  • const_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 等都是随机迭代器。他们支持++/–/+/-。
  • 决定迭代器的性质的是容器的底层结构。

    1. l
    2. i
    3. s
    4. t
    5. list

    list 的迭代器是一个双向迭代器

在这里插入图片描述

2.3 不同迭代器的使用场景

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

2.3.1 sort

在这里插入图片描述

  用

  1. s
  2. o
  3. r
  4. t
  5. sort
  6. sort 算法进行排序,并不是传什么迭代器都可以的,必须传
  1. 随机迭代器

,否则就会报错。
  为什么呢?因为

  1. s
  2. o
  3. r
  4. t
  5. sort
  6. sort 底层是**快速排序**。快排里面要做类似三数取中的东西,它需要支持随机访问。

2.3.2 reverse

在这里插入图片描述

  1. r
  2. e
  3. v
  4. e
  5. r
  6. s
  7. e
  8. reverse
  9. reverse 是将指定范围内的数据进行翻转。

在这里插入图片描述

  这个算法底层用了

  1. '-'操作符

,因此要传

  1. 双向迭代器

  那

  1. v
  2. e
  3. c
  4. t
  5. o
  6. r
  7. vector
  8. vector
  9. s
  10. t
  11. r
  12. i
  13. n
  14. g
  15. string
  16. string 这些随机迭代器能用逆置算法吗?

  肯定能。因为他们功能上是一个包含的关系,

  1. 双向是一种特殊的单向,随机是一种特殊的双向

2.3.3 find

在这里插入图片描述

  那

  1. f
  2. i
  3. n
  4. d
  5. find
  6. find 算法又需传递什么迭代器呢?
  1. InputIterator

是什么迭代器呢?它不是单向,双向,随机种的任意一种

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

在这里插入图片描述

  库里面对迭代器性质的定义使用了 C++ 中

  1. 继承

的概念,继承就是子类是一个特殊的父类,所以它认为这里的单向、双向、随机是一个

  1. 继承关系

随机是一个特殊的双向 ,双向是一个特殊的单向
  同时,库中引申出了两个不存在的迭代器

  1. 只读和只写迭代器

(严格来说没有容器的迭代器类型对应这两类,是抽象的概念)。

  1. InputIterator

迭代器 意味着单向、双向、随机都是其子类。
  出现

  1. InputIterator

就说明可以给任意类型的迭代器

  这里因为

  1. f
  2. i
  3. n
  4. d
  5. find
  6. find 底层只用了
  1. ++

在这里插入图片描述

3 emplace_back

  现阶段,我们可以认为

  1. push_back

  1. emplace_back

是一样的,都是尾插一个数据

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

运行结果:

在这里插入图片描述

  但是在用法上,如果插入数据的参数是多个的,

  1. emplace_back

效率会高一些

假设我们现在要插入自定义类型 A

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

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

  • 插入有名对象
  • 插入匿名对象
  1. voidtest3(){
  2. list<A> lt;
  3. A aa1(1,1);
  4. lt.push_back(aa1);
  5. lt.push_back(A(2,2));
  6. lt.emplace_back(aa1);
  7. lt.emplace_back(A(3,3));}

  这两种方式

  1. p
  2. u
  3. s
  4. h
  5. push
  6. push*
  7. b
  8. a
  9. c
  10. k
  11. back
  12. back
  13. e
  14. m
  15. p
  16. l
  17. a
  18. c
  19. e
  20. emplace
  21. emplace*
  22. b
  23. a
  24. c
  25. k
  26. back
  27. back 都支持

  但是

  1. emplace_back

还支持这样写:

  1. voidtest4(){
  2. list<A> lt;
  3. lt.emplace_back(3,3);}
  1. e
  2. m
  3. p
  4. l
  5. a
  6. c
  7. e
  8. emplace
  9. emplace_
  10. b
  11. a
  12. c
  13. k
  14. back
  15. back
  1. 支持直接传构造 A 的参数。

  这里不是隐式类型转换,现阶段我们先不管其底层,学会用法即可。

4 操作函数

4.1 sort

4.1.1 list中sort介绍

在这里插入图片描述

  我们前面看到,算法库中的

  1. sort

要求是

  1. 随机迭代器

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 的迭代器并不符合,因此它自己实现了一个排序算法。和算法库中的
  7. s
  8. o
  9. r
  10. t
  11. sort
  12. sort 一样,
  13. l
  14. i
  15. s
  16. t
  17. list
  18. list 中的
  19. s
  20. o
  21. r
  22. t
  23. sort
  24. sort 排序默认排的是
  1. 升序

,如果要排降序则要用到仿函数(后面会讲)。

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 实现的
  7. s
  8. o
  9. r
  10. t
  11. sort
  12. sort 底层用的是
  1. 归并排序

,而算法库中的

  1. s
  2. o
  3. r
  4. t
  5. sort
  6. sort 底层用的是
  1. 快速排序
  1. voidtest5(){
  2. list<int> lt;
  3. lt.push_back(3);
  4. lt.push_back(5);
  5. lt.push_back(4);
  6. lt.push_back(1);
  7. lt.push_back(2);
  8. lt.sort();for(auto e : lt){
  9. cout << e <<" ";}
  10. cout << endl;
  11. lt.sort(greater<int>());for(auto e : lt){
  12. cout << e <<" ";}
  13. cout << endl;}

运行结果:

在这里插入图片描述

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

  虽然

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 中实现了
  7. s
  8. o
  9. r
  10. t
  11. sort
  12. sort 排序算法,但是它的
  1. 排序效率很低

,尽量不要用它来排序。

  我们将他与算法库中的

  1. s
  2. o
  3. r
  4. t
  5. sort
  6. 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 排序,看运行时间
  1. voidtest10(){srand(time(0));constint N =1000000;
  2. list<int> lt1;
  3. vector<int> v;for(int i =0; i < N;++i){auto e =rand()+ i;
  4. lt1.push_back(e);
  5. v.push_back(e);}int begin1 =clock();// 排序sort(v.begin(), v.end());int end1 =clock();int begin2 =clock();
  6. 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
  1. voidtest11(){srand(time(0));constint N =1000000;
  2. list<int> lt1;
  3. list<int> lt2;for(int i =0; i < N;++i){auto e =rand()+ i;
  4. lt1.push_back(e);
  5. lt2.push_back(e);}int begin1 =clock();// 拷贝vector
  6. vector<int>v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2
  7. lt2.assign(v.begin(), v.end());int end1 =clock();int begin2 =clock();
  8. lt1.sort();int end2 =clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);}

  上述代码用了

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 中的
  7. a
  8. s
  9. s
  10. i
  11. g
  12. n
  13. assign
  14. assign 接口,我们简单介绍一下

在这里插入图片描述

  1. a
  2. s
  3. s
  4. g
  5. i
  6. n
  7. assgin
  8. assgin 功能是用一段迭代器区间对调用函数的
  9. l
  10. i
  11. s
  12. t
  13. list
  14. list 对象进行拷贝,任何容器的迭代器都可以。像
  15. v
  16. e
  17. c
  18. t
  19. o
  20. r
  21. vector
  22. vector 等都有
  23. a
  24. s
  25. s
  26. g
  27. i
  28. n
  29. assgin
  30. assgin 接口

运行结果:

在这里插入图片描述

  可以看到,即使多了两次拷贝,依然是

  1. 算法库中的 sort 效率更高

。同时这也说明了

  1. 拷贝的代价其实是很低的

4.2 merge

在这里插入图片描述

  1. m
  2. e
  3. r
  4. g
  5. e
  6. merge
  7. merge 接口的功能是:将两个链表合并。合并的前提是两个链表是
  1. 有序

的。

  1. voidtest6(){
  2. std::list<double> first, second;
  3. first.push_back(3.1);
  4. first.push_back(2.2);
  5. first.push_back(2.9);
  6. second.push_back(3.7);
  7. second.push_back(7.1);
  8. second.push_back(1.4);
  9. first.sort();
  10. second.sort();
  11. first.merge(second);for(auto e : first){
  12. cout << e << endl;}}

运行结果:

在这里插入图片描述

  需要注意:

  1. 合并会让其中一个链表空掉。

  其底层是创建一个新链表,依次去两个链表中小的尾插,最后再将新链表与first链表进行交换。

4.3 unique

在这里插入图片描述

  1. u
  2. n
  3. i
  4. q
  5. u
  6. e
  7. unique
  8. unique 是一个去重接口,但它要求数据必须是有序的
  1. voidtest7(){
  2. std::list<int> lt;
  3. lt.push_back(3);
  4. lt.push_back(3);
  5. lt.push_back(1);
  6. lt.push_back(2);
  7. lt.push_back(4);
  8. lt.push_back(4);
  9. lt.push_back(5);
  10. lt.push_back(5);
  11. lt.push_back(1);
  12. lt.push_back(5);
  13. lt.push_back(2);for(auto e : lt){
  14. cout << e <<" ";}
  15. cout << endl;
  16. lt.sort();
  17. lt.unique();for(auto e : lt){
  18. cout << e <<" ";}
  19. cout << endl;}

运行结果:

在这里插入图片描述

4.4 remove

在这里插入图片描述

  1. r
  2. e
  3. m
  4. o
  5. v
  6. e
  7. remove
  8. remove 接口是
  1. 对一个值进行删除

,他和

  1. e
  2. r
  3. a
  4. s
  5. e
  6. erase
  7. erase 有点像。不同的是
  8. e
  9. r
  10. a
  11. s
  12. e
  13. erase
  14. erase 是传一个
  1. 迭代器

  1. r
  2. e
  3. m
  4. o
  5. v
  6. e
  7. remove
  8. remove 是传一个

,我找到了我就删,没找到也不会报错

4.5 splice

在这里插入图片描述

  1. s
  2. p
  3. l
  4. i
  5. c
  6. e
  7. splice
  8. splice 是粘贴的意思,但这函数接口功能更像
  1. 剪切
  1. s
  2. p
  3. l
  4. i
  5. c
  6. e
  7. splice
  8. splice 的功能本质是一种转移:**将
  9. x
  10. x
  11. x 链表中的元素转移到调用该函数的
  12. p
  13. o
  14. s
  15. i
  16. t
  17. i
  18. o
  19. n
  20. position
  21. position 位置之前(是转移不是粘贴)**

实例:将

  1. m
  2. y
  3. l
  4. i
  5. s
  6. t
  7. 2
  8. mylist2
  9. mylist2 数据转移到
  10. m
  11. y
  12. l
  13. i
  14. s
  15. t
  16. 1
  17. mylist1
  18. mylist1 2 的前面
  1. voidtest8(){
  2. std::list<int> mylist1, mylist2;
  3. std::list<int>::iterator it;// set some initial values:for(int i =1; i <=4;++i)
  4. mylist1.push_back(i);// mylist1: 1 2 3 4for(int i =1; i <=3;++i)
  5. mylist2.push_back(i *10);// mylist2: 10 20 30
  6. it = mylist1.begin();++it;// points to 2
  7. mylist1.splice(it, mylist2);// mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element)
  8. cout <<"mylist1:";for(auto e : mylist1){
  9. cout << e <<" ";}
  10. cout << endl;
  11. cout <<"mylist2:";for(auto e : mylist2){
  12. cout << e <<" ";}
  13. cout << endl;}

运行结果:

在这里插入图片描述

  1. s
  2. p
  3. l
  4. i
  5. c
  6. e
  7. splice
  8. splice 还有以下用法:
  1. 调整当前链表节点的顺序

  比如我想将第一个链表中的 5 放在第一个,怎么做呢

  1. voidtest9(){
  2. list<int> lt;
  3. lt.push_back(1);
  4. lt.push_back(2);
  5. lt.push_back(3);
  6. lt.push_back(4);
  7. lt.push_back(5);
  8. lt.push_back(6);}

  第一种方法就是将 5 这个节点删除,再进行头插。但这一来一去又是删除又是

  1. n
  2. e
  3. w
  4. new
  5. new 的,效率较低。

  我们还有一种方法:

  1. 运用 splice 接口

  1. s
  2. p
  3. l
  4. i
  5. c
  6. e
  7. splice
  8. splice 允许自己转移给自己。
  1. voidtest9(){
  2. list<int> lt;
  3. lt.push_back(1);
  4. lt.push_back(2);
  5. lt.push_back(3);
  6. lt.push_back(4);
  7. lt.push_back(5);
  8. lt.push_back(6);
  9. list<int>::iterator it =find(lt.begin(), lt.end(),5);if(it != lt.end()){
  10. lt.splice(lt.begin(), lt, it);}for(auto e : lt){
  11. cout << e <<" ";}
  12. cout << endl;}

运行结果:

在这里插入图片描述

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

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

运行结果:

在这里插入图片描述


*好啦,本期关于

  1. l
  2. i
  3. s
  4. t
  5. list
  6. list 的知识就介绍到这里啦,希望本期博客能对你有所帮助。同时,如果有错误的地方请多多指正,让我们在 C++ 的学习路上一起进步!*
标签: c++ list windows

本文转载自: https://blog.csdn.net/yusjushd/article/details/142001053
版权归原作者 9毫米的幻想 所有, 如有侵权,请联系我们删除。

“【C++】—— list 的了解与使用”的评论:

还没有评论