【C++进阶】深入STL之list：模拟实现深入理解List与迭代器

📝个人主页🌹：Eternity._
⏩收录专栏⏪：C++ “ 登神长阶 ”
🤡往期回顾🤡：初步了解 list
🌹🌹期待您的关注 🌹🌹

在这里插入图片描述

❀STL之list

在软件开发中，数据结构和算法的选择与实现是每一个开发者都必须面对的问题。标准模板库（STL）为我们提供了一系列高效且通用的数据结构和算法模板，极大地简化了C++编程中的许多常见任务。然而，了解这些数据结构和算法背后的实现原理，不仅有助于我们更深入地理解STL，还能提升我们的编程能力和解决问题的能力。

前言： 在STL中，list是一种双向链表，它支持在序列的任何位置进行快速插入和删除操作。与此同时，迭代器是STL中非常重要的一个概念，它使得我们能够以统一的方式遍历和访问STL容器中的元素。在深入了解STL的过程中，模拟实现list和迭代器无疑是一个极有价值的学习过程。

本节我们将从基本的链表结构开始，逐步构建出完整的list类，并实现相应的迭代器类。

📒1. list的基本结构

在这里插入图片描述
list是一个个带头双向循环链表，这意味着每个元素（通常称为节点）都有两个指针：一个指向前一个元素，另一个指向后一个元素，因此我们需要单独再定义一个类来表示节点结构，每个节点再串联起来构成list

节点定义（示例）：

template<classT>structlist_node{
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;list_node(const T& x =T()):_data(x),_next(nullptr),_prev(nullptr){}};

而在构建list时，我们成员变量只需要一个头节点。

list定义（示例）：

template<classT>structlist{typedef list_node<T> Node;public:// 构造函数等可能的其他成员函数... private:
    Node* _head;};

📕2. list的模拟实现

**注意：关于
erase
和
insert
这两个函数的模拟我们依然作为补充放在末尾**

🌈构造函数

在拥有一个list我们只需要将它的头节点初始化一下

list构造（示例）：

voidempty_init(){
    _head =new Node;
    _head->_prev = _head;
    _head->_next = _head;}// 无参构造list(){empty_init();}

🌞析构函数

关于析构函数，我们需要的是将所有节点一一释放就ok啦!

**在模拟析构函数之前，不得不先介绍一下

clear

这个函数，因为

clear

可以删除出头节点以外的所有节点，我们可以利用这一点帮助我们优化析构函数**

list析构（示例）：

voidclear(){// 依次清除节点
    itetator it =begin();// 稍后会提到迭代器的模拟while(it !=end()){
        it =erase(it);}}~list(){clear();// 删除出头节点以外的所有节点delete _head;// 单独删除一下头节点
    _head =nullptr;}

🌙拷贝构造函数

在学习list时，我们发现list不会因为空间不够而需要扩容，因此在使用模拟list时，不用考虑是否会发生

浅拷贝

list拷贝构造函数（示例）：

//list(const list<T>& lt)list(list<T>& lt)// 还未实现const迭代器，先使用常规的{empty_init();for(auto e : lt){push_back(e);// push_back的实现其实是复用insert，文末有补充}}

⭐赋值运算符重载

这里我们以让后传统写法和现代写法两种方法

list赋值运算符重载（示例）：

// 传统写法
list<T>&operator=(const list<T>& lt){clear();// 先将原来的list清空for(auto e : lt){push_back(e);}return*this;}// 现代写法voidswap(list<T>& tmp){
    std::swap(_head, tmp._head);}

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

在介绍完list基本的结构后，让我们来看看今天的重点：迭代器

📚3. list的迭代器

**在我们模拟实现

string

，

vector

时，我们认为迭代器就是一个原生指针，但是在

list

中迭代器底层不是简单的指针，因此我们要独立定义一个新的类**

🍂迭代器的基本结构

迭代器定义（示例）：

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

我们将迭代器单独写作一个类，能解决更多的问题，以及避免其他麻烦

🍁迭代器的运算符重载

因为这些函数和前面差不太多，我们简单看看代码，带过了

代码（示例）：

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

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

self operator++(int)// 后置++{
    self tmp(*this);
    _node = _node->_next;return&tmp;}

self operator--(int)// 后置--{
    self tmp(*this);
    _node = _node->_prev;return&tmp;}booloperator!=(const self& tmp){return _node != tmp._node;}booloperator-=(const self& tmp){return _node -= tmp._node;}

**而今天着重要强调以下两个运算符重载，因为

const

和

非const

下这两个是有区别的：**

//可读写
T&operator*(){return _node->_data;}//可读写
T*operator->(){return&_node->_data;}// it.operator->()-> 编译器帮我们省略了一个箭头->  it->

在定义完迭代器类之后，我们可以实现

begin()

和

end()

来实现

list

的

范围for

🌸list的迭代器

迭代器代码（示例）：

template<classT>structlist{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;
    
    iterator begin(){//return iterator(_head->_next); // 匿名对象return _head->next;}
    iterator end(){//return iterator(_head); // 匿名对象return _head;}private:
    Node* _head;};

当然我们这里还没有实现
const迭代器
很多需要调用
const对象
的函数还无法使用，那么接下来让我们来模拟实现
const迭代器
，见证新的神奇

📙4. list的const迭代器

关于这个list的const迭代器其实有两种写法，常规的写法就是在定义一个新的
const迭代器
的类，虽然这样可以解决问题，但是会造成代码的冗余，让操作繁琐。而另一种方法就是在原有的迭代器类上进行修改，让它能具有两个迭代器都能使用的特点

🎩方法一

const迭代器实现（示例）：

template<classT>struct__list_const_iterator{typedef list_node<T> Node;typedef __list_const_iterator<T> self;
    Node* _node;// 构造函数__list_const_iterator(Node* node):_node(node){}//可读不可写const T&operator*(){return _node->_data;}//可读不可写const T*operator->(){return&_node->_data;}// 可能的其他成员函数... };

🎈方法二

**如果我们将这两个差异的内容单独表示出来归于模板中，因为在

const与非const之间

，无非就是

T&，T*上能否读写的区别

，不影响其他的函数实现，因此我们可以在模板上加上两个参数**
模板参数实例化类型RefT&，(const 变量时) const T&PtrT，(const 变量时) const T
const迭代器实现（示例）：

// 用一个模板来解决 const与非consttemplate<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> Node;// 会实例化成最匹配的typedef __list_iterator<T, Ref, Ptr> self;
    Node* _node;// 构造函数__list_iterator(Node* node):_node(node){}
    
    Ref operator*(){return _node->_data;}

    Ptr operator->(){return&_node->_data;}// 可能的其他成员函数... };template<classT>structlist{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_const_iterator<T,const T&,const T*>  const_iterator;
    
    iterator begin(){return _head->next;}
    iterator end(){return _head;}
    const_iterator begin()const{return _head->next;}
    const_iterator end()const{return _head;}private:
    Node* _head;};

关于list的模拟实现我们就讲到这里，让我看看如何以统一的方式遍历和访问STL容器中的元素

📜5. 统一的方式访问STL容器中的元素

在完成对list的模拟实现后，我们试着用来遍历和访问list中的元素

代码实现（示例）：

voidprint_list(const list<int>& lt){// list<T>没有实例化话，就并不能去遍历寻找// 编译器不知道 list<T>::const_iterator 是内嵌类型，还是静态成员变量
    list<int>::const_iterator it = lt.begin();while(it != lt.end()){
        cout <<*it <<" ";++it;}}voidtest_list(){
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);print_list(lt);
    cout << endl;}

**编译器不知道 list::const_iterator 是内嵌类型，还是静态成员变量，但是如果实例化成

int

后，有需要一个成员是

string

的列表这时我们有犯难了，这时我们就要用到

typename

，

typename

就是告诉编译器，这是一个类型，等list实例化之后再去取**

代码实现（示例）：

template<typenameT>voidprint_list(const list<T>& lt){......// typename 就是告诉编译器，这是一个类型，等list实例化之后再去取typenamelist<T>::const_iterator it = lt.begin();......}

**但是更离谱的来了，这时又有人要求我们打印

vector

的值，容器都换了我们该怎么办呢？这时模板的作用又双体现出来了，这也体现了模板的本质，让我们能省的活交给编译器完成**

代码实现（示例）：

// 这里直接搞了一个Container来适配容器template<typenameContainer>voidprint_container(const Container& con){typenameContainer::const_iterator it = con.begin();while(it != con.end()){
        cout <<*it <<" ";++it;}}

它使得我们能够以统一的方式遍历和访问STL容器中的元素

📔6. list与vector的对比

**我们可以发现list与之前学的竟然有那么多的差异，我们结合上节学的

vector

来分析一下它们的差异：

vector

与

list

都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同**
vectorlist底层结构动态顺序表，一段连续空间带头结点的双向循环链表随机访问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)插入和删除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低迭代器插入删除时触发条件会导致迭代器失效删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

📖7. 总结补充

💧补充：insert和erase的模拟实现

代码实现（示例）：

// insert会返回插入位置的一个迭代器
iterator insert(iterator pos,const T& x){
    Node* newnode =newNode(x);
    Node* cur = pos._node;
    Node* prev = cur->_prev;

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

    cur->_prev = newnode;
    newnode->_next = cur;returniterator(newnode);// 匿名对象}// erase会返回删除位置的next节点的迭代器
iterator erase(iterator pos){
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;delete cur;
    prev->_next = next->_prev;
    next->_prev = prev->_next;returniterator(next);// 匿名对象}// erase和insert的复用voidpush_back(const T& x)// 尾插{insert(end(), x);}voidpush_front(const T& x)// 头插{insert(begin(), x);}voidpop_back()// 尾删{erase(end());}voidpop_front()// 头删{erase(begin());}

🔥总结

通过本次对STL中list和迭代器模拟实现的探索，我们深入了解了双向链表的基本结构、操作原理以及迭代器在遍历和访问链表元素中的重要作用。模拟实现的过程不仅让我们对STL中的list容器有了更深刻的理解，也锻炼了我们的编程能力和解决问题的能力

在模拟实现的过程中，我们学习了如何设计并实现一个双向链表结构，包括节点的定义、链表的插入、删除和遍历等操作。同时，我们也掌握了迭代器的基本概念和实现方法，理解了如何通过迭代器来统一访问和遍历不同的容器类型。

模拟实现STL中的list和迭代器是一个既有趣又富有挑战性的过程。它让我们更加深入地理解了数据结构和算法的基本原理，也为我们日后在实际项目中高效应用STL容器打下了坚实的基础。

最后，感谢大家的耐心阅读和学习。希望本次介绍能够为大家在STL学习和编程实践中提供一些帮助和启示。在未来的学习和工作中，让我们继续深入探索STL的奥秘，不断提升自己的编程能力和解决问题的能力
在这里插入图片描述

谢谢大家支持本篇到这里就结束了，祝大家天天开心！
在这里插入图片描述

标签： c++ list 开发语言

本文转载自: https://blog.csdn.net/EterNity_TiMe_/article/details/139532139
版权归原作者 Eternity._ 所有，如有侵权，请联系我们删除。

【C++进阶】深入STL之list：模拟实现深入理解List与迭代器

❀STL之list

📒1. list的基本结构

📕2. list的模拟实现

🌈构造函数

🌞析构函数

🌙拷贝构造函数

⭐赋值运算符重载

📚3. list的迭代器

🍂迭代器的基本结构

🍁迭代器的运算符重载

🌸list的迭代器

📙4. list的const迭代器

🎩方法一

🎈方法二

📜5. 统一的方式访问STL容器中的元素

📔6. list与vector的对比

📖7. 总结补充

💧补充：insert和erase的模拟实现

🔥总结

发表评论

“【C++进阶】深入STL之list：模拟实现深入理解List与迭代器”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航