【C++篇】STL中list的奥秘与实现解析

我想吃余

发布于 2025-05-28 08:44:51

1930

前言

上篇文章我们学习了vector，本文开始学习list。 list即为数据结构中的链表，我们在学习初阶数据结构的时候已经学习过他的结构了并用C语言实现了他，。我们知道，链表分为是否带头、是否双向和是否循环，因此有8种链表。而功能最强大的就是带头双向循环链表，因此STL选用了他作为list。STL也有单链表，它是forword_list，但用的很少。【初探数据结构】线性表————链表（一）（单链表的实现）【初探数据结构】线性表——链表（二）带头双向循环链表（详解与实现）

本文目标：

了解list的用法，什么时候用？该怎么用？
可以模拟实现一个简单的list类
- 迭代器实现原理，更深层次地感受封装的艺术
- const迭代器的实现原理，感受模板的化繁为简的艺术

一、list的使用

学习前建议阅读文档：list使用说明 list中一些常见的重要接口：

1. list的构造

构造函数（ (constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

使用演示：

//构造空的list
list<int> lt1;

//构造的list中包含n个值为val的元素
list<int> lt2(5, 8);

//拷贝构造函数
list<int> lt3(lt2);

//用[first, last)区间中的元素构造list
int a[5] = { 0,1,2,3,4 };
list<int> lt4(a, a + 4);

//打印内容
cout << "lt1: ";
for (auto e : lt1)
{
	cout << e << " ";
}
cout << endl;

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

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

2. list iterator的使用

此处，我们暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

【注意】

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

3. list capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

4. list element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

5. list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

6. list operations

函数声明	接口说明
splice	将元素从列表转移到其它列表
remove	删除具有特定值的元素
unique	删除重复值
sort	容器中的元素排序
merge	合并排序列表

【注意】

splice

splice 操作不会进行元素的复制或移动，只是修改指针连接，因此效率较高。
在 splice 操作后，被移动的元素将不再属于原始列表。
splice 操作后，原始列表和插入列表的大小会相应改变。
插入操作的时间复杂度为 O(1)

sort：这个接口其实很鸡肋，因为在数据量较大的时候效率会很低，我们可以利用将数据先存储到vector，再调用库中的sort排序，效率会提升。注：list不能直接调用库中的sort，会报错。

二、list模拟实现(牢记)

我们大致观摩一下stl中的list源码，发现它是分为3个类来实现的：

结点类
迭代器类
list类

它将结点和迭代器都另外封装了起来，而list的成员变量只有一个头结点_head和一个记录链表大小的_size。为什么呢？

1. 结点类（为什么要单独封装结点类？）

封装链表结构的细节
- 链表的基本单位是结点，每个节点需要维护前驱指针_prev、后驱指针_next 和数据_val。将结点独立为类，可以：
  - 隐藏实现细节：用户无需关心链表如何连接，只需通过list的接口（如push_back、insert）操作数据。
  - 集中管理资源：结点的创建、指针调整和销毁逻辑被封装在list内部，避免用户直接操作结点指针导致内存错误。
简化链表操作
- 插入或删除结点时，只需调整相邻结点的指针。

例如，list::insert通过操作prev和next指针即可完成插入，无需暴露底层指针操作给用户。

实现代码：

//list结点类
template<class T>
struct ListNode
{
    ListNode<T>* _prev;
    ListNode<T>* _next;
    T _val;

    //constructor初始化结点
    ListNode(const T& val = T())
        :_prev(nullptr)
        , _next(nullptr)
        , _val(val)
    { }

};

为什么没有写析构？思考一下，list类创建的对象为什么要给其他类给销毁了？那这个类还有什么意义？不合理的。

2. 迭代器类

为什么要将迭代器单独封装？

有人会问：迭代器不是指针吗？为什么不直接用呢？还搁这封装，脱裤子放屁呢？

我们来深入学习迭代器：

迭代器性质（由容器底层结构决定）

性质	操作能力	容器
单向迭代器（Forward Iterator）	只能向前移动 (++)	forword_list、unorder_xxx
双向迭代器（Bidirectional Iterator）	向前/向后移动 (++, --)	list、map、set
随机访问迭代器（Random Access Iterator）	任意跳转 (++、--、+, -, [])	vector、string、deque

它们的性质具有向下兼容性：单向迭代器是双向迭代器的一种、双向迭代器右是随机迭代器的一种。

迭代器的能力取决于容器的物理结构：

连续存储（如数组）→ 随机访问迭代器。
链式存储（如链表、树）→ 双向迭代器。
单链表或哈希表 → 单向迭代器。

很明显，链表是链式存储的，存储空间不连续，所以list的迭代器是一个双向迭代器，只能++和--。

但链表空间是不连续的，++后的空间应该是无效的，怎么办呢？

这就是为什么要封装迭代器的原因：

链表的物理存储是非连续的，迭代器需要模拟“连续访问”的语义（利用重载运算符原理）。通过封装迭代器：
- 统一接口：用户可以使用++、--、*等操作遍历链表，使其与vector等连续存储容器的用法一致。
- 隐藏底层指针操作：例如，++操作实际是跳转到next结点，用户无需手动操作链表指针。

基本功能实现：

//list迭代器类
template<class T>
struct ListIterator
{
    typedef ListNode<T> Node;
    //成员变量
    Node* _node;

    //constructor
    ListIterator(Node* node)
        :_node(node)
    { }

    T& operator*()//参考stl源码实现的
    {
        return _node->_val;
    }
    
    T* operator->()
    {
        return &_node->_val;//引用
    }

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

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

        _node = _node->_next;
        return tmp;
    }

    ListIterator<T>& operator--()
    {
        _node = _node->_prev;
        return *this;
    }

    ListIterator<T>operator--(int)
    {
        self tmp(*this);

        _node = _node->_prev;
        return tmp;
    }

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

注意：严格来说，这样写T* operator->()，我们在使用的时候需要这样写it->->a才符合语法。但为了运算符重载的可读性，编译器进行了优化处理，省略了一个->。

const迭代器的实现

如何再去实现const迭代器呢？直接复制粘贴一下然后加个const？这样会使代码十分冗余。

const与非const迭代器其实也就*和->的重载不同，不同点在于返回值类型：

不同点	iterator	const_iterator
operator*返回值	T&	const T&
operator-> 返回值	T*	const T*

我们可以将这两处不同点设置为模板参数：

template<class T, class Ret, class Ptr>
Ret operator*()
{
    return _node->_val;
}
 
Ptr operator->()
{
    return &_node->_val;//引用
}

在list类中这样定义：

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

迭代器类代码实现：

//list迭代器类
template<class T, class Ret, class Ptr>
struct ListIterator
{
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ret, Ptr> self;
    //成员变量
    Node* _node;

    //constructor
    ListIterator(Node* node)
        :_node(node)
    { }

    Ret operator*()
    {
        return _node->_val;
    }
    
    Ptr operator->()
    {
        return &_node->_val;//引用
    }

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

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

        _node = _node->_next;
        return tmp;
    }

    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }

    self operator--(int)
    {
        self tmp(*this);

        _node = _node->_prev;
        return tmp;
    }

    bool operator!=(const self& lt)
    {
        return _node != lt._node;
    }
    bool operator==(const self& lt)
    {
        return _node == lt._node;
    }
};

本文重难点到这就概述完了，剩余的list类可以自主去实现一下，下面我会给出我的list实现源码：

3. list类

	//list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;

    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;

        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            _size = 0;
        }
        // constructor,destructor and operator=
        list()
        {
            empty_init();
        }
        list(int n, const T& value = T())
        {
            empty_init();

            for (size_t i = 0; i < n; ++i)
            {
                push_back(value);
            }
        }


        list(const list<T>& lt)
        {
            empty_init();

            for (auto& e : lt)
            {
                push_back(e);
            }
        }

        list<T>& operator=(list<T> lt)
        {
            swap(lt);

            return *this;
        }

        ~list()
        {
            clear();

            delete _head;
            _head = nullptr;
        }

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

        iterator end()
        {
            return _head;
        }

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

        const_iterator end()const
        {
            return _head;
        }

        // List Capacity
        size_t size()const
        {
            return _size;
        }

        bool empty()const
        {
            return _size == 0;
        }

        // List Access
        T& front()
        {
            return _head->_next->_val;
        }

        const T& front()const
        {
            return _head->_next->_val;
        }

        T& back()
        {
            return _head->_prev->_val;
        }

        const T& back()const
        {
            return _head->_prev->_val;
        }

        // List Modify
        void push_back(const T& val) 
        {
            insert(end(), val);
        }

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

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

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

        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* newnode = new Node(val);

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

            cur->_prev->_next = newnode;
            cur->_prev = newnode;
            ++_size;

            return newnode;
        }

        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            assert(pos != end());
            Node* cur = pos._node;

            cur->_prev->_next = cur->_next;
            cur->_next->_prev = cur->_prev;

            Node* ret = cur->_next;
            delete cur;

            --_size;

            return ret;
        }

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

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

    private:
        Node* _head;
        size_t _size;
    };

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除

c++