【C++】list的使用及底层实现原理

本篇文章对list的使用进行了举例讲解。同时也对底层实现进行了讲解。底层的实现关键在于迭代器的实现。希望本篇文章会对你有所帮助。

🙋‍♂️ 作者：@Ggggggtm 🙋‍♂️

👀 专栏：C++ 👀

💥 标题：list****讲解💥

** ❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️**

一、list的使用

1、1 list的介绍

C++中的标准模板库（STL）提供了许多容器类来处理不同类型的数据，其中之一就是list。list是一个双向链表容器，它可以在其内部存储各种类型的元素，并且支持动态地添加、删除和修改元素。

以下是list的几个主要特点：

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素）。

list的特点主要是基于list底层实现是双向带头循环链表。

1、2 list的使用

1、2、1 list的常规使用

使用list容器时，可以使用其公共接口提供的各种方法来执行常见的操作，如插入、删除、访问等。常用的成员函数包括：

• push_back(element)：将element添加到列表的末尾。

• push_front(element)：将element添加到列表的开始位置。

• pop_back()：从列表的末尾删除元素。

• pop_front()：从列表的开始位置删除元素。

• insert(position, element)：在指定位置插入element。

• erase(position)：删除指定位置上的元素。

• size()：返回列表中的元素数量。

• empty()：检查列表是否为空。

• clear()：清空列表中的所有元素。

• sort()：对列表元素排序。

  除了以上常用函数外，list还提供了许多其他功能，如合并、翻转等。下面我们结合实际例子来理解以下上述的list的使用。

具体代码如下：

void test_list()
{
    // 创建一个列表
    list<int> numbers;

    // 添加元素到列表末尾
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);
    numbers.push_back(4);
    numbers.push_back(5);

    //打印链表中的元素
    list<int>::iterator it = numbers.begin();
    while (it != numbers.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //添加元素到列表头部
    numbers.push_front(10);
    numbers.push_front(20);
    numbers.push_front(30);
    numbers.push_front(40);
    
    //删除链表尾部元素
    numbers.pop_back();

    for (auto e : numbers)
    {
        cout << e << " ";
    }
    cout << endl;

    // 插入元素到指定位置
    auto pos = find(numbers.begin(), numbers.end(), 3);
    if (pos != numbers.end())
    {
        // pos是否会失效？不会
        numbers.insert(pos, 30); 
    }

    for (auto e : numbers)
    {
        cout << e << " ";
    }
    cout << endl;

    //删除指定位置元素
    pos = find(numbers.begin(), numbers.end(), 4);
    if (pos != numbers.end())
    {
        // pos是否会失效？会 删除后pos位置直接会被释放
        numbers.erase(pos);
        // cout << *pos << endl;
    }

    for (auto e : numbers)
    {
        cout << e << " ";
    }
    cout << endl;

    // 对列表进行升序排序
    numbers.sort();

    // 输出列表元素
    for (int number : numbers) {
        cout << number << " ";
    }
    cout << endl;

}
int main()
{
    test_list();
    return 0;
}

我们再看一下实际的运行结果：

如上结果可以对应着代码一起看，对list的使用理解会容易一点。

1、2、2 list的sort讲解

list容器内部自己提供了sort函数。为什么呢？我们知道，STL中有一个重要组件就是算法，其中提供了sort函数，那这两者又有什么区别呢？

首先STL中的算法库中提供的sort函数底层使用的是快排。list中的迭代器并不支持随机访问迭代器，所以不能使用STL算法库中提供的sort。list容器中的sort函数底层使用的是归并排序。两者是有所区别的。

我们先来测试一下两者的效率，看看是否属于一个级别的。测试代码如下：

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();
        //v.push_back(e);
        lt1.push_back(e);
        lt2.push_back(e);
    }

    // 拷贝到vector排序，排完以后再拷贝回来
    int begin1 = clock();
    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();
    // sort(lt.begin(), lt.end());
    lt2.sort();
    int end2 = clock();

    printf("copy vector sort:%d\n", end1 - begin1);
    printf("list sort:%d\n", end2 - begin2);
}
int main()
{
    test_op();
    return 0;
}

针对上述代码，讲解一下比较的思路。首先我们创建两个链表。随机生成一百万个元素加入到链表中。一个链表用于把元素拷贝到vector排序，然后调用STL算法库中的sort函数，排完以后再拷贝回来，计算此过程的时间。另一个链表直接调用自己容器内的sort进行排序，计算排序时间。我们看一下时间对比：

我们发现，在debug版本下调试，差距基本上不大。但是在release版本下调试，还是有一定差距的。发现在release版本下，拷贝到vector中排序更快。数据量越大，效果会越明显。所以，当数据量大的时候，我们尽量去使用拷贝到vector中，调用STL算法库中的sort函数去排序。

二、list的底层实现

2、1 初构list底层模型

我们知道list底层是带头双向循环列表后，我们可大概构建一个模型。如下：

    template<class T>
    struct list_node
    {
        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;

        list_node(const T& x = T())
            :_data(x)
            , _next(nullptr)
            , _prev(nullptr)
        {}
    };

    template<class T>
    class list
    {
        typedef list_node<T> Node;
    public:
        list()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        void push_back(const T& x)
        {
            Node* tail = _head->_prev;
            Node* newnode = new Node(x);

            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }
    private:
        Node* _head;
    };

上述代码中，也实现了尾插。尾插来说相对简单，这里就不再做过解释。关键是list的迭代器的底层实现。

2、2 迭代器的实现

2、2、1 普通迭代器

我们先想一下vector和string的迭代器。 vector和string的迭代器底层无非就是指针，该指针指向元素内容。支持++、--、解引用等操作。

list的迭代器底层能直接是Node* 指针吗？假如是Node* 指针，我们 ++ 和 -- 操作，是不能够找到下一个元素的。因为链表本身每个节点的地址不是连续的。其次，我们解引用操作并不是找到节点所存储的值，而是找到的是该节点。

综上主要原因，为了解决上述情况，C++ list 的底层迭代器采用了把 Node* 封装成了一个类。在该类中重载运算符，以达到我们想要的效果。我们可结合如下代码理解一下：

    template<class T>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        Node* _node;
        
        // 构造函数
        __list_iterator(Node* node)
            :_node(node)
        {}

        // 解引用操作，返回节点所存储的值
        T& operator*()
        {
            return _node->_val;
        }

        // 前置++
        __list_iterator<T>& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        // 后置++ 返回 ++前的结果
        __list_iterator<T> operator++(int)
        {
            __list_iterator<T> tmp(*this);

            _node = _node->_next;

            return tmp;
        }
        
        // 比较的节点的地址是够相同
        bool operator!=(const __list_iterator<T>& it)
        {
            return _node != it._node;
        }

        bool operator==(const __list_iterator<T>& it)
        {
            return _node == it._node;
        }
    };

我们再把封装后的迭代器类融入到 list 类中。为什么还要融入到 list 类中呢？融入到 list 中又该怎么使用呢？我们先看如下代码：

        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();

我们定义 list 迭代器时，是根据 list 对象 lt，通过调用该类的成员函数 begin（）或者end（）来创建的。那我们自己实现时，在list中提供这两个成员函数即可。代码如下：

    template<class T>
    struct list_node
    {
        list_node<T>* _next;
        list_node<T>* _prev;
        T _val;

        list_node(const T& val = T())
            :_next(nullptr)
            , _prev(nullptr)
            , _val(val)
        {}
    };

    template<class T>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        Node* _node;

        __list_iterator(Node* node)
            :_node(node)
        {}

        T& operator*()
        {
            return _node->_val;
        }

        __list_iterator<T>& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        __list_iterator<T> operator++(int)
        {
            __list_iterator<T> tmp(*this);

            _node = _node->_next;

            return tmp;
        }

        bool operator!=(const __list_iterator<T>& it)
        {
            return _node != it._node;
        }

        bool operator==(const __list_iterator<T>& it)
        {
            return _node == it._node;
        }
    };


    template<class T>
    class list
    {
        typedef list_node<T> Node;

    public:
        typedef __list_iterator<T> iterator;


        iterator begin()
        {
            //单参数的构造函数支持隐式类型转换
            //  Node* 会进行隐式类型转换，中间会生成一个匿名对象作为临时变量
            //return _head->_next;
         
            return iterator(_head->_next);
        }

        iterator end()
        {
            return _head;
            //return iterator(_head);
        }

        list()
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
        }


        void push_back(const T& x)
        {
            Node* tail = _head->_prev;
            Node* newnode = new Node(x);

            tail->_next = newnode;
            newnode->_prev = tail;

            newnode->_next = _head;
            _head->_prev = newnode;
        }

    private:
        Node* _head;
    };

2、2、2 const 迭代器

我们实现的普通的迭代器，那const 修饰的迭代器，不就是在普通的迭代器上加上一个指针就可以了。代码如下：

// const 迭代器
const __list_iterator<T> 
typedef const __list_iterator<T> const_iterator;

注意：上述的 const 修饰的是这个类型，这个类型是自定义类型，并不是我们之前学的指针。我们也可结合如下代码理解：

//const __list_iterator<T> 
//typedef const __list_iterator<T> const_iterator;

    const list<int> numbers;

    // 添加元素到列表末尾
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);
    numbers.push_back(4);
    numbers.push_back(5);

    list<int>::const_iterator cit=numbers.begin();
    // const int a = 10;

上述的 const 是修饰的迭代器本身，并不是迭代器指向的内容。这样修饰只是迭代器本身不能修改。而我们想要是迭代器指向的内容不能被修改。也就是解引用返回的值不能被修改。当然，我们可以再封装一个const迭代器类，代码如下：

    template<class T>
    struct __list_const_iterator
    {
        typedef list_node<T> Node;
        Node* _node;

        __list_const_iterator(Node* node)
            :_node(node)
        {}

        const T& operator*()
        {
            return _node->_val;
        }

        __list_const_iterator<T>& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        __list_const_iterator<T> operator++(int)
        {
            __list_const_iterator<T> tmp(*this);

            _node = _node->_next;

            return tmp;
        }

        bool operator!=(const __list_const_iterator<T>& it)
        {
            return _node != it._node;
        }

        bool operator==(const __list_const_iterator<T>& it)
        {
            return _node == it._node;
        }
    };

这样我们发现会不会设计的代码优点冗余了。C++ STL中，list底层实现也并非如此，而是通过增加模板参数选择复用代码。如下图：

我们可以通过增加模板参数（第三个模板参数我们后面也会讲到），来控制解引用返回的是否是用const修饰的引用。代码如下：

    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        typedef __list_iterator<T, Ref, Ptr> iterator;

        Node* _node;

        // 休息到17：02继续
        __list_iterator(Node* node)
            :_node(node)
        {}

        bool operator!=(const iterator& it) const
        {
            return _node != it._node;
        }

        bool operator==(const iterator& it) const
        {
            return _node == it._node;
        }

        // *it  it.operator*()
        // const T& operator*()
        // T& operator*()
        Ref operator*()
        {
            return _node->_data;
        }


        // ++it
        iterator& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        
        // it++
        iterator operator++(int)
        {
            iterator tmp(*this);
            _node = _node->_next;
            return tmp;
        }

    };
    template<class T>
    class list
    {
        typedef list_node<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;

        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }

        const_iterator end() const
        {
            return const_iterator(_head);
        }

        iterator begin()
        {
            return iterator(_head->_next);
        }

        iterator end()
        {
            return iterator(_head);
        }

        list()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        void push_back(const T& x)
        {
            //Node* tail = _head->_prev;
            //Node* newnode = new Node(x);

             _head          tail  newnode
            //tail->_next = newnode;
            //newnode->_prev = tail;
            //newnode->_next = _head;
            //_head->_prev = newnode;

            insert(end(), x);
        }

    private:
        Node* _head;
    };

我们在 list 类中添加 const 迭代器的返回即可。当我们定义const对象时，会自动调用const修饰的迭代器。当调用const修饰的迭代器时，__list_iterator的模板参数就会实例化为const T&。实际上在实例化时，const和非const修饰的还是两个不同类，只不过是实例化的代码工作交给了编译器处理了。

以上就是迭代器的底层实现。list底层中，关键重点就是迭代器的实现。其他部分相对来说简单。接下来我们完善剩余的底层实现部分。

2、3 完善其他底层实现

我们上述代码中有尾插，再把常用接口和拷贝构造、赋值重载实现即可。代码如下：

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

        iterator insert(iterator pos, const T& x)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;

            Node* newnode = new Node(x);

            // prev newnode cur
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;

            return iterator(newnode);
        }

        iterator erase(iterator pos)
        {
            assert(pos != end());

            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            prev->_next = next;
            next->_prev = prev;
            delete cur;

            return iterator(next);
        }

        void pop_back()
        {
            erase(--end());
        }

        void pop_front()
        {
            erase(begin());
        }

        void empty_init()
        {
            // 创建并初始化哨兵位头结点
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        template <class InputIterator>  
        list(InputIterator first, InputIterator last)
        {
            empty_init();

            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        list()
        {
            empty_init();
        }

        void swap(list<T>& x)
        //void swap(list& x)
        {
            std::swap(_head, x._head);
        }

        // lt2(lt1)
        list(const list<T>& lt)
        {
            empty_init();
            list<T> tmp(lt.begin(), lt.end());
            swap(tmp);
        }

        // lt1 = lt3
        list<T>& operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }

上述代码，把初始化的代码再次封装了一个函数。list初始化构造也可用一段区间来初始化，这个区间可以是vector迭代器区间，或者数组的指针区间等等。其他实现均较为简单。

三、总结

我们之前是由顺序表和链表的对比，现在我们再对比一下vector和list的优缺点。如下：
vector****list
**底 **

**层 **

**结 **

构

**动态顺序表，一段连续空间 **

带头结点的双向循环链表

**随 **

**机 **

**访 **

**问 **

支持随机访问，访问某个元素效率O(1)

不支持随机访问，访问某个元素效率O(N)

**插 **

**入 **

**和 **

**删 **

除

**任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 **

**任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 **

O(1）

**空 **

**间 **

**利 **

**用 **

**率 **

底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高

底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低

**迭 **

**代 **

**器 **

原生态指针

对原生态指针(节点指针)进行封装

**迭 **

**代 **

**器 **

**失 **

**效 **

**在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 **

插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

**使 **

**用 **

**场 **

**景 **

需要高效存储，支持随机访问，不关心插入删除效率

大量插入和删除操作，不关心随机访问

list底层实现关键是迭代器的实现。我们要清楚的是， list的迭代器底层就是一个对节点进行封装的类。初学可能会感觉有点难以理解。但是，应多看几遍理解整体结构就很容易清楚了。本篇文章的讲解就到这里，感谢观看ovo~