我的编程空间,编程开发者的网络收藏夹
学习永远不晚

C++模拟实现List迭代器详解

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

C++模拟实现List迭代器详解

概念

迭代器是一种抽象的设计概念,其定义为:提供一种方法,使他能够按顺序遍历某个聚合体(容器)所包含的所有元素,但又不需要暴露该容器的内部表现方式。

迭代器是一种行为类似智能指针的对象, 而指针最常见的行为就是内 容提领和成员 访问。 因此迭代器最重要的行为就是对operator*和operator->进行重载。

STL的中心思想在于: 将数据容器和算法分开, 彼此独立设计, 最后再以一贴胶合剂( iterator) 将它们撮合在一起。STL的迭代器是一个可遍历STL容器全部或者部分数据

迭代器使用

我们可以使用迭代器访问修改链表元素

list<int>  lt;
list<int>::iterator it=lt.begin();
while(it!=lt.end())
{
    *it+=2;
    cout<<*it<<" ";
    it++;
}

2.我们有些函数接口需要传迭代器,例如:

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);
​
template <class ForwardIterator, class T>
  void replace (ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value);

迭代器模拟实现

迭代器的大体结构

//链表节点
template<class T>
struct ListNode {
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;
    //构造节点值
    ListNode(const T& data = T())
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(data)
    {}
};
​
///迭代器
//T为list数据类型,Ref为T&,Ptr为T*
template<class T,class Ref,class Ptr>
struct __list_iterator
{
    typedef ListNode<T> Node;
    typedef __list_iterator<T,Ref,Ptr> self;
    Node* _node;//节点指针
    
    //接下来实现的函数都是在这个位置
};

构造函数

一般都会传过来一个节点地址

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

注意迭代器的拷贝构造、赋值重载以及析构函数不需要我们自己实现,编译器实现的完全够用。

  • 拷贝构造与赋值重载:因为list迭代器本身就是一个自定义类型的指针,都是地址的拷贝与赋予。所以浅拷贝就满足使用。
  • 析构函数:因为list迭代器是借助节点指针访问修改链表,节点是链表的,不需要迭代器释放。

解引用重载

解引用重载(*)

解引用本质是根据地址拿到在这个地址的有效数据

Ref operator*()
{
    return _node->_data;
}

重载

->重载

->本质是拿到所求数据的地址

Ptr operator->()
{
    return &_node->_data;
}

自增实现

前置++

++后迭代器指向当前位置的下一个位置,返回指向下一个位置的迭代器

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

后置++

++后迭代器指向当前位置的下一个位置,返回指向之前位置的迭代器,要使用一个临时变量保存++之前的this指针,然后后移_node,返回临时变量。

//这块一定要使用占位符,防止与前置++重命名。
self& operator++(int)
{
    __list_iterator<T> tmp(*this);
    _node=_node->_next;
    return tmp;
}

自减实现

与++基本一样,不做解释。

前置--

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

后置--

self& operator--(int)
{
    __list_iterator<T> tmp(*this);
    _node=_node->_prev;
    return tmp;
}

运算符重载

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

迭代器失效

以vector为例,当我们插入一个元素时它的预分配空间不够时,它会重新申请一段新空间,将原空间上的元素 复制到新的空间上去,然后再把新加入的元素放到新空间的尾部,以满足vector元素要求连续存储的目的。而后原空间会被系统撤销或征做他用,于是指向原 空间的迭代器就成了类似于“野指针”一样的东西,指向了一片非法区域。如果使用了这样的迭代器会导致严重的运行时错误就变得很自然了。这也是许多书上叙 述vector在insert操作后“可能导致所有迭代器实效”的原因。

但是想到这里我不禁想到vector的erase操作的叙述是“会导致指向删除元 素和删除元素之后的迭代器失效” ,这里的删除元素不一定不成功,但一定存在迭代器失效。例:

vector<int> v;//{1,2,3,4,5}
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
    if(*it%2==0)
    {
        v.erase(it);
    }
    it++;
}

所以要避免这种情况,改进代码

vector<int> v;//{1,2,3,4,5}
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
    if(*it%2==0)
    {
        v.erase(it);
    }
    else
        it++;
}

list迭代器失效

list<int> l1;
list<int>::iterator it=l1.begin();
while(it!=l1.end())
{
    if(*it%2==0)
    {
        l1.erase(it);
    }
    else
        ++it;
}

改进代码

list<int> l1;
list<int>::iterator it=l1.begin();
while(it!=l1.end())
{
    if(*it%2==0)
    {
        it=l1.erase(it);
    }
    else
        ++it;
}

归纳迭代器失效的类型

(1)由于容器元素整体“迁移”导致存放原容器元素的空间不再有效,从而使得指向原空间的迭代器失效。

(2)由于删除元素使得某些元素次序发生变化使得原本指向某元素的迭代器不再指向希望指向的元素

模拟List

具体下一章讲

 template<class T>
    class list
    {
        typedef ListNode<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 iterator(_head);
        }
​
        const_iterator begin()const
        {
            return const_iterator(_head->_next);
        }
​
        const_iterator end()const
        {
            return const_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);
            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }
​
        void insert(iterator pos, const T& x)
        {
​
        }
        void erase(iterator pos)
        {
​
        }
    private:
        Node* _head;
    };

到此这篇关于C++模拟实现List迭代器详解的文章就介绍到这了,更多相关C++ List迭代器内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

C++模拟实现List迭代器详解

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

详解C++ STL模拟实现list

这篇文章主要为大家详细介绍了C++如何模拟实现STL容器list,文中的示例代码讲解详细,对我们学习C++有一定帮助,需要的可以参考一下
2023-01-11

C++list的模拟实现

list是数据结构中的链表,在C++的STL中,有list的模板,STL中的list的结构是带头双向循环链表,当然STL中还有一个forward_list的链表,这个链表是一个带头的单链表。为了更好的理解list,我们来对其进行模拟实现。,需要的朋友可以参考
2023-05-16

C++之list容器模拟怎么实现

这篇“C++之list容器模拟怎么实现”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C++之list容器模拟怎么实现”文章吧
2023-07-05

C++之list容器模拟实现方式

这篇文章主要介绍了C++之list容器模拟实现方式,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
2023-02-05

利用C++模拟实现STL容器:list

列表是一种顺序容器,它允许在序列中的任何位置执行常量时间插入和删除操作,并允许在两个方向上进行迭代。本文将利用C++模拟实现list,希望对大家有所帮助
2022-12-08

C#中怎么实现迭代器模式

这篇文章将为大家详细讲解有关C#中怎么实现迭代器模式,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。在我们的应用程序中常常有这样一些数据结构:它们是一个数据的集合,如果你知道它们内部的实现结构
2023-06-17

详解C++STL模拟实现forward_list

forward_list是C++11新增的容器,它支持从容器中的任何位置快速插入和移除元素的容器,不支持快速随机访问。本文将模拟实现forward_list,感兴趣的可以了解一下
2023-01-13

C++模拟实现vector流程详解

这篇文章主要介绍了C++容器Vector的模拟实现,Vector是一个能够存放任意类型的动态数组,有点类似数组,是一个连续地址空间,下文更多详细内容的介绍,需要的小伙伴可以参考一下
2022-11-13

C# 中怎么利用Iterator实现迭代器模式

本篇文章给大家分享的是有关C# 中怎么利用Iterator实现迭代器模式,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。C# Iterator迭代器模式我们在平时的开发中应该经常
2023-06-18

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录