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

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

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 的迭代器

voidtest1(){
    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，我们想在第三个位置之前插入数据怎么办呢？

方法如下：

voidtest1(){
    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 迭代器的划分

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

从功能上进行划分

• 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 等都是随机迭代器。他们支持++/–/+/-。

• 决定迭代器的性质的是容器的底层结构。

     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_back

与

emplace_back

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

voidtest2(){
    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

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

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

• 插入有名对象
• 插入匿名对象

voidtest3(){
    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

还支持这样写：

voidtest4(){
    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 底层用的是

快速排序

voidtest5(){
    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 排序，看运行时间

voidtest10(){srand(time(0));constint 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

voidtest11(){srand(time(0));constint 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
    vector<int>v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2
    lt2.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 接口的功能是：将两个链表合并。合并的前提是两个链表是

有序

的。

voidtest6(){
    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 是一个去重接口，但它要求数据必须是有序的

voidtest7(){
    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 的前面

voidtest8(){
    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 30

    it = mylist1.begin();++it;// points to 2

    mylist1.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 放在第一个，怎么做呢

voidtest9(){
    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 允许自己转移给自己。

voidtest9(){
    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++ 的学习路上一起进步！*