本文目标：

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

---

一、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

使用演示：

代码语言：javascript

代码运行次数：0

运行

AI代码解释

//构造空的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位置

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. 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

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

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

---

二、list模拟实现(牢记)

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

1. 结点类
2. 迭代器类
3. list类

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

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

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

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

实现代码：

代码语言：javascript

代码运行次数：0

运行

AI代码解释

//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结点，用户无需手动操作链表指针。

基本功能实现：

代码语言：javascript

代码运行次数：0

运行

AI代码解释

//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*

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

代码语言：javascript

代码运行次数：0

运行

AI代码解释

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

在list类中这样定义：

代码语言：javascript

代码运行次数：0

运行

AI代码解释

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

迭代器类代码实现：

代码语言：javascript

代码运行次数：0

运行

AI代码解释

//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类

代码语言：javascript

代码运行次数：0

运行

AI代码解释

	//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;
    };