C++ list容器-54-链表存取和反转和排序

Bertha 。 2022-11-25 13:28 121阅读 0赞

继续学习list容器相关常见的API，这边学习三点，分别是list容器的存取操作，和list容器反转，这个反转经常在面试的时候被问到，最后来看看list容器的排序操作。

**1.list的存取**

注意：list容器没有和其他容器那样，根据\[\]和at函数获取某个位置的元素。原因是和list双端链表的数据结构有关系，由于不是连续存储，所以这里索引去查找元素就行不通。

在list容器中两个api，我们可能需要经常使用，获取头部和尾部的元素，front()和back()

#include <iostream>
    #include <string>
    #include <list>
    using namespace std;
    
    
    void printList(const list<int>& l)
    {
        for(list<int>::const_iterator it = l.begin(); it != l.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    
    }
    
    void test01()
    {
        // list 大小
        list<int> li;   // 默认构造函数
    
        // 尾部加数据
        li.push_back(10);
        li.push_back(20);
        li.push_back(30);
        li.push_back(30);
        li.push_back(40);
        printList(li);
    
        // 获取头部元素
        cout << "Head of list: " << li.front() << endl;
    
        // 获取尾部元素
        cout << "end of list: " << li.back() << endl;
    
    }
    
    
    int main()
    {
        test01();
        system("pause");
        return 0;
    }

运行结果

![20200809201303278.png][]

**2.list的反转**

反转函数reverse()，这个函数在多门开发语言都是存在的，至少java是有这个API。通过这个API, 可以把链表反转过来。

下面来代码测试一下。

#include <iostream>
    #include <string>
    #include <list>
    using namespace std;
    
    
    void printList(const list<int>& l)
    {
        for(list<int>::const_iterator it = l.begin(); it != l.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    
    }
    
    void test01()
    {
        // list 大小
        list<int> li;   // 默认构造函数
    
        // 尾部加数据
        li.push_back(10);
        li.push_back(20);
        li.push_back(30);
        li.push_back(30);
        li.push_back(40);
        printList(li);
    
        // 反转操作
        li.reverse();
        cout << "after reverse :" << endl;
        printList(li);
    
    }
    
    
    int main()
    {
        test01();
        system("pause");
        return 0;
    }

测试结果

![20200809220536131.png][]

**3.list的排序**

这个sort()排序也是前面学习过的，默认升序。

#include <iostream>
    #include <string>
    #include <list>
    using namespace std;
    
    
    void printList(const list<int>& l)
    {
        for(list<int>::const_iterator it = l.begin(); it != l.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    
    }
    
    void test01()
    {
        // list 大小
        list<int> li;   // 默认构造函数
    
        // 尾部加数据
        li.push_back(50);
        li.push_back(20);
        li.push_back(10);
        li.push_back(30);
        li.push_back(40);
        printList(li);
    
        // 排序操作
        li.sort();
        cout << "after sort :" << endl;
        printList(li);
    
    }
    
    
    int main()
    {
        test01();
        system("pause");
        return 0;
    }

注意，由于list不支持随机访问，所以不支持前面学习的全局函数sort(li.begin(), li.end())这样的排序算法，一般来说，如果不支持全局算法，容器本身会提供类似的算法。这里li.sort(),就是链表容器本身提供的排序算法。

测试结果

![20200809220743246.png][]

这回如果要实现降序，怎么做，就用用到sort()第二个重载函数，里面参数传入的是一个函数名称，这个函数是我们自己实现。

#include <iostream>
    #include <string>
    #include <list>
    using namespace std;
    
    
    void printList(const list<int>& l)
    {
        for(list<int>::const_iterator it = l.begin(); it != l.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    
    }
    
    
    bool myCompare(int v1, int v2)
    {
        // 降序，只需要v1 > v2
        return v1 > v2;
    }
    
    void test01()
    {
        // list 大小
        list<int> li;   // 默认构造函数
    
        // 尾部加数据
        li.push_back(50);
        li.push_back(20);
        li.push_back(10);
        li.push_back(30);
        li.push_back(40);
        printList(li);
    
        // 排序操作
        li.sort(myCompare);
        cout << "after sort :" << endl;
        printList(li);
    
    }
    
    int main()
    {
        test01();
        system("pause");
        return 0;
    }

测试结果

![20200809221636567.png][]

[20200809201303278.png]: /images/20221124/f8036af0d0da416e858c7edff591298e.png
[20200809220536131.png]: /images/20221124/040bb59af8864718a12dd651c9d20e9f.png
[20200809220743246.png]: /images/20221124/d904a166e91344eea3dc8551aade093e.png
[20200809221636567.png]: /images/20221124/a8c3cf74759e434eb10adc53a67d3eda.png