AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

【c++丨STL】list模拟实现（附源码）

2024-12-29 291
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。

前言

       通过之前对list的学习，我们已经基本掌握了其底层结构以及常用接口。今天我们在此基础上，尝试模拟实现list。


       与vector、string不同，由于list的底层是一个双向带头循环链表，所以它的实现上要更加复杂。vector和string的迭代器可以是原生指针，但是list的迭代器需要用一个类模板来实现，并且数据之间都是以节点的指针相连接，我们还需要定义其节点结构。当然，与vector一样，在接下来模拟实现list的过程中，我们也将采用类模板进行定义，并不会将声明和定义分离。



建议大家在掌握了双向带头循环链表以及vector、string的实现之后，再来阅读本文，否则其中部分内容可能较难理解。


一、节点、迭代器以及函数声明

       首先是链表节点、迭代器和我们要实现接口的声明：

#include <iostream>
#include <cassert>
using namespace std;
 
//节点
template<class T>
struct list_node
{
    T _data;//数据域
    list_node<T>* _next;//指向后一个节点
    list_node<T>* _prev;//指向前一个节点
 
    //节点的默认构造
    list_node(const T& x = T());
};
 
//迭代器
template<class T, class Ref, class Ptr>
struct list_iterator
{
    typedef list_node<T> Node;
    typedef list_iterator<T, Ref, Ptr> Self;
 
    Node* ptr;//封装节点的指针
 
    //迭代器构造
    list_iterator(Node* node);
 
    //解引用
    Ref operator*();
    //结构成员间接访问
    Ref operator->();
    //前置++
    &Self operator++();
    //前置--
    &Self operator--();
    //后置++
    Self operator++(int);
    //后置--
    Self operator--(int);
    //不等于
    bool operator!=(const Self& it);
};
 
//容器
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;
 
    //迭代器接口
    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
 
    //空链表的初始化
    void empty_init();
 
    //无参构造
    List();
    //n个val值构造
    List(size_t n, const T& val = T());
    //拷贝构造
    List(const List<T>& l);
    //赋值重载
    List<T>& operator=(List<T> l);
    //析构
    ~List();
 
    //容量接口
    size_t size() const;
 
    //插入和删除
    iterator insert(iterator pos, const T& x);
    iterator erase(iterator pos);
    void push_back(const T& x);
    void push_front(const T& x);
    void pop_back();
    void pop_front();
 
    //清空链表
    void clear();
 
    //交换两个链表
    void swap(List<T> l);
private:
    Node* _head;//头节点的指针
    size_t _size;//节点个数
};
 
//交换两个链表--非成员函数版
template <class T>
void swap(List<T>& l1, List<T>& l2);

接下来，我们开始逐一实现这三个部分。


二、list功能实现

1. 节点

       和传统的双向带头循环链表相同，节点当中有一个数据域用于存放数据；两个指针分别指向前驱节点和后继节点。 我们需要实现节点的默认构造函数，便于容器构造节点。


代码实现：

//节点
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)
    {}
};

可以看到，这里的节点我们也定义成了一个类模板，参数T表示的是传入的数据类型。对于构造函数，如果我们没有显式传参，则数据x就会调用其默认构造函数初始化。


2. 迭代器

       迭代器也是一个类模板，我们模拟实现的迭代器具有三个模板参数：数据类型T，T的引用类型Ref（普通引用或const引用）、T的指针类型Ptr（普通指针或const指针）。 为什么要这样设计呢？其实这样做的目的是为了提高代码复用率。如果我们创建了一个list普通对象和一个const对象，那么使用它们的迭代器时，相对应就会有普通迭代器和const迭代器。这样我们在实现迭代器时，就要将同样的接口写两遍。而当我们定义了三个模板参数后，容器内部就可以通过传参来定义对应的普通迭代器和const迭代器，减少了代码冗余。

//list容器内部定义迭代器
typedef list_iterator<T, T&, T*> iterator;//普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator;//const迭代器

其次，为了简化代码，我们typedef一下节点类型以及迭代器本身类型：

typedef list_node<T> Node;//节点
typedef list_iterator<T, Ref, Ptr> Self;//迭代器本身

除此之外，由于迭代器是将指针进行封装，所以我们要将其成员变量设置为一个指向链表节点的指针：

Node* _ptr;//封装节点的指针

接下来，我们开始实现迭代器的操作函数。


迭代器的默认构造

//迭代器构造
list_iterator(Node* node)
    :_ptr(node)
{}

对于构造函数，我们将传入的指针赋值给成员指针即可。


operator*

//解引用
Ref operator*()
{
    return _ptr->_data;
}

解引用用于访问指针所指对象的数据，所以函数返回迭代器指向节点的数据域。


operator->

//结构成员间接访问
Ref operator->()
{
    return &_ptr->_data;
}

       正常来讲，该函数的作用应该是用于访问指针所指向数据的成员，但是它并没有参数，而且返回值却是数据地址。这是为什么呢？这其实和c++的语法规定有关。当我们使用该运算符重载时，要访问到数据的成员，原本应该这样写：迭代器 ->-> 成员。但是连续两个“->”看起来并不美观，并且难以理解，所以c++语法在这里省略了一个“->”，仅支持 迭代器->成员或迭代器.operator->()->成员 的写法。所以我们在实现该重载时，要返回数据的地址，编译器就会默认根据这个地址找到指定成员（成员名写在->后即可，不传参）。



前置++和--

        由于链表底层结构并非连续，所以不能直接使指针++/--来改变指向，而应该使用类似链表遍历的方式。实现如下：

//前置++
Self& operator++()
{
    _ptr = _ptr->next;
    return *this;
}
//前置--
Self& operator--()
{
    _ptr = _ptr->prev;
    return *this;
}

后置++和--

       后置++/--的实现方法与前置++/--类似。这里创建一个临时迭代器来保存未移动时的指向。

//后置++
Self operator++(int)
{
    Self tmp(*this);
    _ptr = _ptr->next;
    return tmp;
}
//后置--
Self operator--(int)
{
    Self tmp(*this);
    _ptr = _ptr->prev;
    return tmp;
}

operator!=

//不等于
bool operator!=(const Self& it)
{
    return _ptr != it._ptr;
}

这里判断它们的成员指针是否相等即可。


3. 容器

       为了简化代码，还是先typedef一下节点类型：

typedef list_node<T> Node;

       接下来，我们开始实现list容器的常用接口。


交换两个容器的内容

       还是老套路，我们仅需交换它们的成员变量，就可以完成容器的交换。代码实现：

//交换两个链表
void swap(List<T> l)
{
    std::swap(_head, l.head);//交换头节点指针
    std::swap(_size, l._size);//交换size
}
//交换两个链表--非成员函数版
template <class T>
void swap(List<T>& l1, List<T>& l2)
{
    l1.swap(l2);//直接调用成员函数版
}

迭代器接口

        首先是普通迭代器和const迭代器的定义：

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

迭代器接口实现：

//迭代器接口
iterator begin()
{
    return iterator(_head->next);
}
iterator end()
{
    return _head;
}
const_iterator begin() const
{
    return iterator(_head->next);
}
const_iterator end() const
{
    return _head;
}

这里要注意一下它们的返回值：begin的返回值是指向首元素的迭代器，由于我们的链表头部有一个哨兵节点，所以首元素是哨兵节点的下一个节点；end的返回值是指向尾元素的“下一个元素”的迭代器，比较抽象，这里刚好可以定义为哨兵节点。



空链表初始化

       该函数用于创建哨兵节点并且初始化链表的各项属性，便于后续构造函数调用。

//空链表的初始化
void empty_init()
{
    _head = new Node();
    _head->next = _head->prev = _head;
    _size = 0;
}

构造函数

       这里我们实现一下无参构造和n个val值构造：

//无参构造
List()
{
    empty_init();
}
//n个val值构造
List(size_t n, const T& val = T())
{
    empty_init();
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);//循环尾插
    }
}

拷贝构造函数

       拷贝构造函数的逻辑与n个val值构造相同，遍历源链表内容，循环尾插给当前链表即可。

//拷贝构造
List(const List<T>& l)
{
    empty_init();
    for (auto& e : l)
    {
        push_back(e);
    }
}

赋值重载

       这里我们仍然使用新式写法，构造新对象然后交换，完成赋值操作。 代码如下：

//赋值重载
List<T>& operator=(List<T> l)
{
    swap(l);
    return *this;//支持连续赋值
}

析构函数

       对于析构函数，我们首先释放掉所有的节点空间，然后删除哨兵节点。

//析构
~List()
{
    clear();//调用clear函数清空链表
    delete _head;
    _head = nullptr;
}

容量接口size

       容量接口size用于获取链表数据个数。我们在函数当中返回成员变量_size的值。

//容量接口
size_t size() const
{
    return _size;
}

插入和删除

       和之前实现vector时的逻辑相同，我们首先实现insert和erase函数，这两个函数分别用于在任意位置进行插入和删除操作。然后，其他的插入和删除函数可以直接调用它们，能确保代码的高效性和复用性。


insert和erase

       insert的逻辑和我们c语言实现双向链表时大体相同（在pos位置之前插入），注意插入元素后，pos指向的不再是原本需要插入的位置，迭代器失效，所以函数要返回新插入的节点的迭代器。

//插入
iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._ptr;
    Node* newnode = new Node(x);
    newnode->_next = cur;
    newnode->_prev = cur->_prev;
    cur->_prev->_next = newnode;
    cur->_prev = newnode;
    _size++;
    return iterator(newnode);
}

       erase负责删除pos指向的节点。注意删除节点之后，该节点的迭代器会失效，所以函数返回指向被删除节点的后一个节点的迭代器。

iterator erase(iterator pos)
{
    assert(pos != end());//避免删除哨兵节点
    Node* del = pos._ptr;
    Node* next = del->_next;
    Node* prev = del->_prev;
    next->_prev = del->_prev;
    prev->_next = del->_next;
    delete del;
    _size--;
    return iterator(next);
}

push_back、push_front、pop_back、pop_front

尾插、头插、尾删、头删直接调用insert和erase函数即可。注意尾删节点时，end指向的前一个位置才是尾节点。

void push_back(const T& x)
{
    insert(end(), x);
}
void push_front(const T& x)
{
    insert(begin(), x);
}
void pop_back()
{
    erase(--end());
}
void pop_front()
{
    erase(begin());
}


清空链表

       清空链表的操作类似于我们c语言实现的销毁链表，这里循环调用erase函数来完成数据的清除。注意不要删除哨兵节点。

//清空链表
void clear()
{
    auto it = begin();//从首元素开始，一个个删除
    while (it != end())
    {
        it = erase(it);
    }
}

三、程序全部代码

       关于list模拟实现的全部代码如下：

#include <iostream>
#include <cassert>
using namespace std;
 
//节点
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 Ref, class Ptr>
struct list_iterator
{
    typedef list_node<T> Node;
    typedef list_iterator<T, Ref, Ptr> Self;
 
    Node* _ptr;//封装节点的指针
 
    //迭代器构造
    list_iterator(Node* node)
        :_ptr(node)
    {}
 
    //解引用
    Ref operator*()
    {
        return _ptr->_data;
    }
    //结构成员间接访问
    Ref operator->()
    {
        return &_ptr->_data;
    }
    //前置++
    Self& operator++()
    {
        _ptr = _ptr->next;
        return *this;
    }
    //前置--
    Self& operator--()
    {
        _ptr = _ptr->prev;
        return *this;
    }
    //后置++
    Self operator++(int)
    {
        Self tmp(*this);
        _ptr = _ptr->next;
        return tmp;
    }
    //后置--
    Self operator--(int)
    {
        Self tmp(*this);
        _ptr = _ptr->prev;
        return tmp;
    }
    //不等于
    bool operator!=(const Self& it)
    {
        return _ptr != it._ptr;
    }
};
 
//容器
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;
 
    //迭代器接口
    iterator begin()
    {
        return iterator(_head->next);
    }
    iterator end()
    {
        return _head;
    }
    const_iterator begin() const
    {
        return iterator(_head->next);
    }
    const_iterator end() const
    {
        return _head;
    }
 
    //空链表的初始化
    void empty_init()
    {
        _head = new Node();
        _head->next = _head->prev = _head;
        _size = 0;
    }
 
    //无参构造
    List()
    {
        empty_init();
    }
    //n个val值构造
    List(size_t n, const T& val = T())
    {
        empty_init();
        for (size_t i = 0; i < n; i++)
        {
            push_back(val);//循环尾插
        }
    }
    //拷贝构造
    List(const List<T>& l)
    {
        empty_init();
        for (auto& e : l)
        {
            push_back(e);
        }
    }
    //赋值重载
    List<T>& operator=(List<T> l)
    {
        swap(l);
        return *this;//支持连续赋值
    }
    //析构
    ~List()
    {
        clear();//调用clear函数清空链表
        delete _head;
        _head = nullptr;
    }
 
    //容量接口
    size_t size() const
    {
        return _size;
    }
 
    //插入和删除
    iterator insert(iterator pos, const T& x)
    {
        Node* cur = pos._ptr;
        Node* newnode = new Node(x);
        newnode->_next = cur;
        newnode->_prev = cur->_prev;
        cur->_prev->_next = newnode;
        cur->_prev = newnode;
        _size++;
        return iterator(newnode);
    }
    iterator erase(iterator pos)
    {
        assert(pos != end());//避免删除哨兵节点
        Node* del = pos._ptr;
        Node* next = del->_next;
        Node* prev = del->_prev;
        next->_prev = del->_prev;
        prev->_next = del->_next;
        delete del;
        _size--;
        return iterator(next);
    }
    void push_back(const T& x)
    {
        insert(end(), x);
    }
    void push_front(const T& x)
    {
        insert(begin(), x);
    }
    void pop_back()
    {
        erase(--end());
    }
    void pop_front()
    {
        erase(begin());
    }
 
    //清空链表
    void clear()
    {
        auto it = begin();//从首元素开始，一个个删除
        while (it != end())
        {
            it = erase(it);
        }
    }
 
    //交换两个链表
    void swap(List<T> l)
    {
        std::swap(_head, l.head);//交换头节点指针
        std::swap(_size, l._size);//交换size
    }
private:
    Node* _head;//头节点的指针
    size_t _size;//节点个数
};
 
//交换两个链表--非成员函数版
template <class T>
void swap(List<T>& l1, List<T>& l2)
{
    l1.swap(l2);//直接调用成员函数版
}


总结

       本篇文章，我们在掌握list使用方法及其底层原理的基础上，模拟实现出了list容器。由于底层数据内存的非连续性，它的迭代器实现与vector、string有较大差异。之后博主会和大家一起开始stack和queue的学习。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

文章标签：
C++
容器
C语言
编译器
关键词：
C++ stl
C++源码
C++ stl源码
C++ list
C++ list源码
ephemerals__
目录
相关文章
蒋星熠Jaxonic
|
3月前
|
C++
基本二叉树与排序二叉树（C++源码）
本程序实现二叉树基本操作与二叉排序树应用。支持前序建树、四种遍历、求深度、叶子数、第K层节点数及查找功能；并实现二叉排序树的构建、中序输出与查找比较次数统计，分析不同插入顺序对树形态和查找效率的影响。
蒋星熠Jaxonic
343 6
蒋星熠Jaxonic
|
3月前
|
缓存 算法 程序员
C++STL底层原理：探秘标准模板库的内部机制
🌟蒋星熠Jaxonic带你深入STL底层：从容器内存管理到红黑树、哈希表，剖析迭代器、算法与分配器核心机制，揭秘C++标准库的高效设计哲学与性能优化实践。
蒋星熠Jaxonic
462 3
C++STL底层原理：探秘标准模板库的内部机制
ephemerals__
|
10月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map（附源码）
本文基于红黑树的实现，模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改，实现了两种容器的功能。主要步骤包括：1) 修改红黑树节点结构以支持不同数据类型；2) 使用仿函数适配键值比较逻辑；3) 实现双向迭代器支持遍历操作；4) 封装`insert`、`find`等接口，并为`map`实现`operator[]`。最终，通过测试代码验证了功能的正确性。此实现减少了代码冗余，展示了模板与仿函数的强大灵活性。
ephemerals__
294 2
ephemerals__
|
10月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现，内部元素按键自动升序排列，存储键值对，支持通过键访问或修改值；而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能，并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别，强调了`map`在处理键值关系时的优势。
ephemerals__
584 73
ephemerals__
|
10月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器，二者均为关联式容器，底层基于红黑树实现。`set`支持唯一性元素存储并自动排序，适用于高效查找场景；`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作（如`insert`、`erase`）、查找统计（如`find`、`count`）及`multiset`特有的区间操作（如`lower_bound`、`upper_bound`、`equal_range`）。最后预告了`map`容器的学习，其作为键值对存储的关联式容器，同样基于红黑树，具有高效操作特性。
ephemerals__
463 3
ephemerals__
|
11月前
|
存储 算法 C++
【c++丨STL】priority_queue（优先级队列）的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`（优先级队列）。`priority_queue`根据严格的弱排序标准设计，确保其第一个元素始终是最大元素。它底层使用堆结构实现，支持大堆和小堆，默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`，通过仿函数控制堆的类型，并调用封装容器的接口实现功能。最后，感谢大家的支持与关注。
ephemerals__
725 1
平凡程序猿~
|
11月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
289 0
ephemerals__
|
9月前
|
编译器 C++ 容器
【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）
C++11为C++带来了革命性变化，引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式，initializer_list简化了容器多元素初始化；右值引用和移动语义优化了资源管理，减少拷贝开销；类新增移动构造和移动赋值函数提升性能；lambda表达式提供匿名函数对象，增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展，提升了开发效率与程序性能。
ephemerals__
391 12
hahaha无
|
7月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
210 0
hahaha无
|
7月前
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
333 0