C++ 如何快速实现一个容器的迭代器

这篇具有很好参考价值的文章主要介绍了C++ 如何快速实现一个容器的迭代器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C++ 如何快速实现一个容器的迭代器

引言

C++的标准库中的容器都会提供迭代器,如果一个容器满足forward_range,那么这个容器一般会提供以下成员类型和函数:

  • iterator
  • const_iterator
  • begin
  • end
  • begin
  • cend

如果该容器还满足bidirectional_range,那么该容器还会额外提供以下成员类型和函数:

  • reversed_iterator
  • const_reversed_iterator
  • rbegin
  • rend
  • rcbegin
  • rcend

笔者曾经在网上搜索过如何实现C++迭代器的文章,但是大多数文章都只是实现了一个最普通的迭代器,从学习原理的角度来说是非常好的,但是相比于标准库或者其他工业化的库来说可能是非常不完整的,所以笔者打算在本文中尽可能将容器中的迭代器部分完整地实现出来。

大多数人可能由于种种原因,C++的标准还停留在C++11,所以我们这里分别使用C++11和最新的标准来编写迭代器。


什么是迭代器

我们这里引用cppreference原话:

Iterators are a generalization of pointers that allow a C++ program to work with different data structures (for example, containers and ranges (since C++20)) in a uniform manner.

从定义不难看出,迭代器是一个泛化的指针。


指针

既然迭代器是泛化的指针,那么我们可以通过指针来了解迭代器。我们知道指针共有两个位置可以添加const关键字,共有4种可能,我们将他们对应到迭代器类型:

  • iterator => T *
  • const_iterator => const T *
  • const iterator => T * const
  • const const_iterator => const T * const

对于指针类型,const在前面表示说不可以通过该指针去修改所指的变量,而const在后面则表示该指针只能指向某个变量,不能修改指针本身,但是可以修改变量。我们在实现迭代器成员类型和函数的时候只需要关注前两者即可,后面的可以按照C++正常的写法来,可以加const的地方直接加上即可。


基于C++11的具体实现

由于我们的重点在于迭代器部分,所以我们尽可能地选取一个简单的数据结构来实现容器,这里我们实现一个双链表。同时我们也假设读者阅读过关于迭代器实现的文章,对迭代器的核心实现有一定的了解。

首先定义一下链表基本的实现:

template <typename T>
class LinkList {
    
    struct ListNodeBase {

        ListNodeBase* m_next;
        ListNodeBase* m_prev;

        ListNodeBase() { reset(); }

        void reset() { m_prev = m_next = this; }
    };

    struct ListNode : ListNodeBase {
        T m_value;
    };

    // 循环链表头结点,next指向第一个元素,prev指向最后一个元素
    ListNodeBase m_header;  
}

接下来是实现迭代器部分,对于很多容器来说,iterator和const_iterator是两个不同类,但是实际上这两个类里面的实现几乎是完全一样的,这也许很容易让人想到继承的写法,但是在C++中我们还有一个更好的方法,那就是使用模板,使用模板的代码量也许会少于使用继承。如果读者是一个非常排斥使用模板的人,不妨尝试着去接受一下,毕竟模板是C++中非常重要的一部分,同时作者也相信在注释和自身基本功到位的情况下,模板的编写和维护也不是非常困难的。

template <bool Const>
struct LinkListIterator {
    // ...
};

using iterator = LinkListIterator<false>;
using const_iterator = LinkListIterator<true>;

我们使用一个bool类型的变量(Const)来让LinkListIterator在二者之间进行切换,当该变量为true时,他是const_iterator,否则是iterator。

迭代器一般会定义以下成员类型:

  • value_type
  • reference
  • pointer
  • difference_type
  • iterator_category

value_type在容器的迭代器中一般是当前容器元素的类型。
reference在容器的迭代器中一般是当前容器元素的引用类型。
pointer在容器的迭代器中一般是当前容器元素的指针类型,C++20之后无需定义。
difference_type表示两个迭代器距离的类型,在容器中一般是ptrdiff_t。
iterator_category表示该迭代器的种类。

需要注意的是,容器中的迭代器并不能够代表所有的情况,比如迭代器reference并不一定是引用类型,iterator_category也仅仅只是一个必要条件。

using value_type = typename std::conditional<Const, const T, T>::type;
using reference = value_type&;
using pointer = value_type*;   
using difference_type = std::ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;

然后是定义构造函数:

node_type* m_ptr;

LinkListIterator() = default;

LinkListIterator(const LinkListIterator&) = default;

LinkListIterator(node_type* ptr) : m_ptr(ptr) { }

// 我们可以使用一个int* 来初始化一个const int*
// 同理,我们可以使用iterator来初始化一个const_iterator
template <bool IsConst, typename = typename std::enable_if<(Const && !IsConst)>::type>
LinkListIterator(const LinkListIterator<IsConst>& other) 
    : m_ptr(other.m_ptr) { }

C++迭代器的操作一般是基于运算符的,所以我们需要对相应的运算符进行重载。bidirectional_iterator需要重载以下操作符。

// C++11
bool operator==(const LinkListIterator& other) const {
    return m_ptr == other.m_ptr;
}

bool operator!=(const LinkListIterator& other) const {
    return !this->operator==(other);
}

reference operator*() const { return m_ptr->m_value; }

pointer operator->() const { return &this->operator*(); }

LinkListIterator& operator++() {
    m_ptr = m_ptr->m_next;
    return *this;
}

// it++
LinkListIterator operator++(int) {
    auto old = *this;
    ++*this;
    return old;
}

// --it
LinkListIterator& operator--() {
    m_ptr = m_ptr->m_prev;
    return *this;
}

// it--
LinkListIterator operator--(int) {
    auto old = *this;
    --*this;
    return old;
}

到此为止,一个双链表的迭代器就全部实现完毕了,至于reversed_iterator,标准库为我们提供了std::reverse_iterator,我们只需要将我们的迭代器传给它即可。

using iterator = LinkListIterator<false>;
using const_iterator = LinkListIterator<true>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

最后我们提供一下相关的成员函数:

iterator begin() { return m_header.m_next; }
iterator end() { return &m_header; }

const_iterator begin() const { return const_cast<LinkList&>(*this).begin(); }
const_iterator end() const { return const_cast<LinkList&>(*this).end(); }

const_iterator cbegin() const { return begin(); }
const_iterator cend() const { return end(); }

reverse_iterator rbegin() { return end(); }
reverse_iterator rend() { return begin(); }

const_reverse_iterator rbegin() const { return end(); }
const_reverse_iterator rend() const { return begin(); }

const_reverse_iterator rcbegin() const { return end(); }
const_reverse_iterator rcend() const { return begin(); }

由于const版本的重载实现和non-const版本是完全一致的,并且我们也提供了构造函数使得iterator可以转化为const_iterator,所以我们直接使用const_cast实现了const版本的重载。


基于C++23的具体实现

随着技术的不断进步,很多时候我们不必再使用以往繁琐的方式来实现我们想要的东西。既然reverse_iterator可以直接使用标准库的组件完成,那么const_iterator是否也可以使用类似的方法来实现呢?毕竟看起来我们只需要对iterator进行简单封装就可以把它变成一个const_iterator。

答案是肯定的,那就是std::const_iterator。当然这个东西涉及的细节还是非常多的,不是看起来那么简单,读者有兴趣的话可以自行阅读相关文献。

我们来尝试简化一下上述代码:

// template <bool Const>
struct LinkListIterator {
    using value_type = T;
    using reference = value_type&;
    // using pointer = value_type*;
    using difference_type = ptrdiff_t;
    using iterator_category = std::bidirectional_iterator_tag;

    // 我们可以使用一个int* 来初始化一个const int*
    // 同理,我们可以使用iterator来初始化一个const_iterator
    // template <bool IsConst, typename = typename std::enable_if<(Const && !IsConst)>::type>
    // LinkListIterator(const LinkListIterator<IsConst>& other) 
    //     : m_ptr(other.m_ptr) { }

};

using iterator = LinkListIterator;
using const_iterator = std::const_iterator<iterator>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

我们只需要实现一个普通的iterator即可,因为标准库已经为我们提供了新的组件,同时额外的构造函数也自然不再需要。

pointer这一成员类型也是不必要的,std::iterator_traits会自动帮我们推导。没有pointer之后我们可以直接使用auto来完成->运算符重载。

auto operator->() const { return &this->operator*(); }

同时对于==这一运算符,许多实现无非就是简单比较每一个成员字段是否相等,而!=等于运算符往往也是等价于==运算结果取反。

bool operator==(const LinkListIterator& other) const = default;

// 不写则自动生成
// bool operator!=(const LinkListIterator& other) const { ... } 

默认生成的==运算符的,有如下规则:

A class can define operator== as defaulted, with a return value of bool. This will generate an equality comparison of each base class and member subobject, in their declaration order. Two objects are equal if the values of their base classes and members are equal. The test will short-circuit if an inequality is found in members or base classes earlier in declaration order.

需要注意的是,数组类型的比较是按照range的规则来的,即比较数组中每一个元素是否相等,而非将数组看成一个指针进行比较:

struct F
{
    int data[2];
    constexpr F(int a, int b) : data{a, b} { }
    constexpr bool operator==(const F&) const = default;
};

constexpr F f1(1, 2), f2(3, 4), f3(1, 2);

static_assert(f1 != f2);
static_assert(f1 == f3);

我们的简化过程到此为止就结束了,剩下的部分保持不变即可。关于简化之后的代码,读者可以点击这里获取。文章来源地址https://www.toymoban.com/news/detail-450654.html

到了这里,关于C++ 如何快速实现一个容器的迭代器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深入探究C++中的STL:容器、迭代器与算法全解析

    Standard Template Library:标准模板库 是一个基于泛型的C++类模板库由Alexander Stepanov于1994年开发 其目的是为了提供一致通用和高效的数据结构和算法,同时不限制用户所处理的数据类型和编程范式。STL的原型最初由Andrew Koenig和其它C++专家小组进行设计并在1995年C++标准委员会的推

    2024年02月05日
    浏览(72)
  • C++,如何快速的求一个正整数的所有因数的个数?

          首先,让我们看看什么是因数,       定义 :因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数,我们就说b是a的因数。      好,接下来是问题: 题目描述       给定一个整数n(1n10^9),求出n的因子的个数。      首先我们先看一看 数据范围 。  

    2024年02月12日
    浏览(43)
  • java八股文面试[Spring]——如何实现一个IOC容器

            IOC不是一种技术,只是一种思想,一个重要的面向对象编程的法则,它能指导我们如何设计出 松耦合 ,更优良的程序。传统应用程序都是由我们在类内部主动创建依赖对象,从而导致类与类之间高耦合,难于测试;有了IOC容器后,把 创建和查找依赖对象 的控制

    2024年02月10日
    浏览(48)
  • Autofac高级应用,一个接口多个实现类如何注册到容器并获取实例

      当使用Autofac处理一个接口有多个实现的情况时, 通常会使用键(key)进行区分 或者 通过IIndex索引注入 ,也可以 通过IEnumerable集合获取所有实例 ,以下是一个具体的例子,演示如何在Autofac中注册多个实现,并通过构造函数注入获取指定实现。 首先,确保你已经安装了A

    2024年02月05日
    浏览(50)
  • 如何快速搭建一个大模型?简单的UI实现

    🔥博客主页: 是dream 🚀系列专栏: 深度学习环境搭建、环境配置问题解决、自然语言处理、语音信号处理、项目开发 💘每日语录:相信自己,一路风景一路歌,人生之美,正在于此。 🎉感谢大家点赞👍收藏⭐指正✍️ 前言:本文章纯属是自己无聊,调用了星火认知大模

    2024年02月05日
    浏览(56)
  • rust里如何快速实现一个LRU 本地缓存?

    LRU是Least Recently Used(最近最少使用)的缩写,是一种常见的缓存淘汰算法。LRU算法的基本思想是,当缓存空间已满时,优先淘汰最近最少使用的数据,以保留最常用的数据。 在计算机系统中,LRU算法常用于缓存系统、页面置换算法等场景,以提高数据访问的效率和性能。 要

    2024年02月13日
    浏览(42)
  • 【C++庖丁解牛】STL之vector容器的介绍及使用 | vector迭代器的使用 | vector空间增长问题

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 vector的文档介绍 vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存

    2024年03月14日
    浏览(79)
  • 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 什么是迭代器(iterator) 迭代器(iterator)的定义: 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(50)
  • C++之深入解析如何实现一个线程池

    当进行并行的任务作业操作时,线程的建立与销毁的开销是,阻碍性能进步的关键,因此线程池,由此产生。使用多个线程,无限制循环等待队列,进行计算和操作,帮助快速降低和减少性能损耗。 线程池的组成: 线程池管理器:初始化和创建线程,启动和停止线程,调配

    2024年02月02日
    浏览(34)
  • 【c++迭代器模拟实现】

    打怪升级:第52天 什么是STL STL(standard template libaray-标准模板库):是C++标准库的重要组成部分,不仅是一个可复用的组件库,而且是一个包罗数据结构与算法的软件框架。 STL的版本 原始版本 Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本,本着开源精神,他们声明允许

    2024年02月02日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包