【c++手撕STL】之迭代器

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

迭代器定义

在C++ STL(Standard Template Library,标准模板库)中,迭代器是一个非常重要的组成部分。迭代器像是一个指针,负责在容器的元素之间移动,并且能够访问到容器的元素。

C++ STL提供了几种类型的迭代器,每种迭代器都有它独特的功能和特性:

  1. 输入迭代器(Input Iterators):只读不写,只能单向移动(自增++)。
  2. 输出迭代器(Output Iterators):只写不读,只能单向移动(自增++)。
  3. 前向迭代器(Forward Iterators):可读写,只能单向移动(自增++)。
  4. 双向迭代器(Bidirectional Iterators):可读写,可以双向移动(自增++,自减–)。
  5. 随机访问迭代器(Random Access Iterators):可读写,支持全部迭代器运算。可以进行任意跳跃的访问。

在使用时,可以像操作指针一样通过*操作符来操作迭代器访问元素,例如*iterSTL中的标准容器像是vectorlistmap等都支持迭代器,你可以创建相应的迭代器来进行遍历操作。

例如:

std::vector<int> vec = {1, 2, 3, 4, 5};
for(std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << std::endl;
}

在这个例子中,vec.begin()返回一个指向vector开始的迭代器,vec.end()返回一个指向vector结尾后一位置的迭代器。这是STL的一种惯用方式,end()迭代器并不指向任何元素,它用来提供一种方便的判断遍历是否结束的条件。

迭代器的种类

输入迭代器 提供对数据的只读访问 支持++、==、!=
输出迭代器 提供对数据的只写访问 支持++
前向迭代器 提供读写操作,并能将迭代器向前推进 支持++、==、!=
双向迭代器 提供读写操作,并能将迭代器向前推进也能向后推进 支持++、–
随机访问迭代器 提供读写操作,并能任意位置访问容器,是功能最强的迭代器 支持++、–、[n]、-n、>、<、>=、<=

手撕代码

类型信息定义

#ifndef __TYPE_TRAITS_HPP__
#define __TYPE_TRAITS_HPP__

// 这个头文件用于提取类型信息

#include <type_traits>
#include <utility>

namespace Stl
{
    template <class T, T v>
    struct m_integral_constant
    {
        static constexpr T value = v;
    };
    template <bool b>
    using m_bool_constant = m_integral_constant<bool, b>;

    typedef m_bool_constant<true> m_true_type;
    typedef m_bool_constant<false> m_false_type;

    // is_pair

    // --- forward declaration end

    template <class T>
    struct is_pair : Stl::m_false_type
    {
    };

    template <class T1, class T2>
    struct is_pair<std::pair<T1, T2>> : Stl::m_true_type
    {
    };
}

#endif /* __TYPE_TRAITS_HPP__ */

迭代器设计

#ifndef __ITERATOR_HPP__
#define __ITERATOR_HPP__

// 这个头文件用于迭代器设计,包含了一些模板结构体与全局函数,

#include <cstddef>
#include "type_traits.hpp"

namespace Stl
{

    // 五种迭代器类型
    // 输入迭代器
    struct input_iterator_tag
    {
    };
    // 输出迭代器
    struct output_iterator_tag
    {
    };
    // 前向迭代器
    struct forward_iterator_tag : public input_iterator_tag
    {
    };
    // 双向迭代器
    struct bidirectional_iterator_tag : public forward_iterator_tag
    {
    };
    // 随机访问迭代器
    struct random_access_iterator_tag : public bidirectional_iterator_tag
    {
    };

    // iterator 模板
    template <class Category, class T, class Distance = ptrdiff_t,
              class Pointer = T *, class Reference = T &>
    struct iterator
    {
        typedef Category iterator_category; // 迭代器类型标签
        typedef T value_type;               // 所指对象类型
        typedef Pointer pointer;            // 指针类型
        typedef Reference reference;        // 引用类型
        typedef Distance difference_type;   // 两个迭代器之间距离的类型,通常是ptrdiff_t
    };

    // iterator traits
    // 检查是否有迭代器类型标签
    template <class T>
    struct has_iterator_cat
    {
    private:
        struct two
        {
            char a;
            char b;
        };
        template <class U>
        static two test(...);
        template <class U>
        static char test(typename U::iterator_category * = 0);

    public:
        static const bool value = sizeof(test<T>(0)) == sizeof(char);
    };

    template <class Iterator, bool>
    struct iterator_traits_impl
    {
    };

    template <class Iterator>
    struct iterator_traits_impl<Iterator, true>
    {
        typedef typename Iterator::iterator_category iterator_category;
        typedef typename Iterator::value_type value_type;
        typedef typename Iterator::pointer pointer;
        typedef typename Iterator::reference reference;
        typedef typename Iterator::difference_type difference_type;
    };

    template <class Iterator, bool>
    struct iterator_traits_helper
    {
    };

    template <class Iterator>
    struct iterator_traits_helper<Iterator, true>
        : public iterator_traits_impl<Iterator,
                                      std::is_convertible<typename Iterator::iterator_category, input_iterator_tag>::value ||
                                          std::is_convertible<typename Iterator::iterator_category, output_iterator_tag>::value>
    {
    };

    // 萃取迭代器的特性
    template <class Iterator>
    struct iterator_traits
        : public iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value>
    {
    };

    // 针对原生指针的偏特化版本
    // 辅助函数来访问迭代器的属性
    template <class T>
    struct iterator_traits<T *>
    {
        typedef random_access_iterator_tag iterator_category; // 获取迭代器类型标签
        typedef T value_type;                                 // 获取所指对象类型
        typedef T *pointer;                                   // 获取指针类型
        typedef T &reference;                                 // 获取引用类型
        typedef ptrdiff_t difference_type;                    // 获取距离类型
    };

    template <class T>
    struct iterator_traits<const T *>
    {
        typedef random_access_iterator_tag iterator_category;
        typedef T value_type;
        typedef const T *pointer;
        typedef const T &reference;
        typedef ptrdiff_t difference_type;
    };

    // 检查迭代器类型标签是否匹配
    template <class T, class U, bool = has_iterator_cat<iterator_traits<T>>::value>
    struct has_iterator_cat_of
        : public m_bool_constant<std::is_convertible<
              typename iterator_traits<T>::iterator_category, U>::value>
    {
    };

    // 萃取某种迭代器
    template <class T, class U>
    struct has_iterator_cat_of<T, U, false> : public m_false_type
    {
    };

    // 检查是否为输入迭代器
    template <class Iter>
    struct is_input_iterator : public has_iterator_cat_of<Iter, input_iterator_tag>
    {
    };

    // 检查是否为输出迭代器
    template <class Iter>
    struct is_output_iterator : public has_iterator_cat_of<Iter, output_iterator_tag>
    {
    };

    // 检查是否为前向迭代器
    template <class Iter>
    struct is_forward_iterator : public has_iterator_cat_of<Iter, forward_iterator_tag>
    {
    };

    // 检查是否为双向迭代器
    template <class Iter>
    struct is_bidirectional_iterator : public has_iterator_cat_of<Iter, bidirectional_iterator_tag>
    {
    };

    // 检查是否为随机访问迭代器
    template <class Iter>
    struct is_random_access_iterator : public has_iterator_cat_of<Iter, random_access_iterator_tag>
    {
    };

    // 检查是否为迭代器(输入或输出)
    template <class Iterator>
    struct is_iterator : public m_bool_constant<is_input_iterator<Iterator>::value ||
                                                is_output_iterator<Iterator>::value>
    {
    };

    // 萃取某个迭代器的 category
    template <class Iterator>
    typename iterator_traits<Iterator>::iterator_category
    iterator_category(const Iterator &)
    {
        typedef typename iterator_traits<Iterator>::iterator_category Category;
        return Category();
    }

    // 萃取某个迭代器的 distance_type
    template <class Iterator>
    typename iterator_traits<Iterator>::difference_type *
    distance_type(const Iterator &)
    {
        return static_cast<typename iterator_traits<Iterator>::difference_type *>(0);
    }

    // 萃取某个迭代器的 value_type
    template <class Iterator>
    typename iterator_traits<Iterator>::value_type *
    value_type(const Iterator &)
    {
        return static_cast<typename iterator_traits<Iterator>::value_type *>(0);
    }

    // 以下函数用于计算迭代器间的距离

    // distance 的 input_iterator_tag 的版本
    template <class InputIterator>
    typename iterator_traits<InputIterator>::difference_type
    distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag)
    {
        typename iterator_traits<InputIterator>::difference_type n = 0;
        while (first != last)
        {
            ++first;
            ++n;
        }
        return n;
    }

    // distance 的 random_access_iterator_tag 的版本
    template <class RandomIter>
    typename iterator_traits<RandomIter>::difference_type
    distance_dispatch(RandomIter first, RandomIter last,
                      random_access_iterator_tag)
    {
        return last - first;
    }

    // 计算两个迭代器之间的距离
    template <class InputIterator>
    typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last)
    {
        return distance_dispatch(first, last, iterator_category(first));
    }

    // 以下函数用于让迭代器前进 n 个距离

    // advance 的 input_iterator_tag 的版本
    template <class InputIterator, class Distance>
    void advance_dispatch(InputIterator &i, Distance n, input_iterator_tag)
    {
        while (n--)
            ++i;
    }

    // advance 的 bidirectional_iterator_tag 的版本
    template <class BidirectionalIterator, class Distance>
    void advance_dispatch(BidirectionalIterator &i, Distance n, bidirectional_iterator_tag)
    {
        if (n >= 0)
            while (n--)
                ++i;
        else
            while (n++)
                --i;
    }

    // advance 的 random_access_iterator_tag 的版本
    template <class RandomIter, class Distance>
    void advance_dispatch(RandomIter &i, Distance n, random_access_iterator_tag)
    {
        i += n;
    }

    // 将迭代器前进指定步数
    template <class InputIterator, class Distance>
    void advance(InputIterator &i, Distance n)
    {
        advance_dispatch(i, n, iterator_category(i));
    }

    /*****************************************************************************************/

    // 模板类 : reverse_iterator
    // 代表反向迭代器,使前进为后退,后退为前进
    template <class Iterator>
    class reverse_iterator
    {
    private:
        Iterator current; // 记录对应的正向迭代器

    public:
        // 反向迭代器的五种相应型别
        typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
        typedef typename iterator_traits<Iterator>::value_type value_type;
        typedef typename iterator_traits<Iterator>::difference_type difference_type;
        typedef typename iterator_traits<Iterator>::pointer pointer;
        typedef typename iterator_traits<Iterator>::reference reference;

        typedef Iterator iterator_type;
        typedef reverse_iterator<Iterator> self;

    public:
        // 构造函数
        reverse_iterator() {}
        explicit reverse_iterator(iterator_type i) : current(i) {}
        reverse_iterator(const self &rhs) : current(rhs.current) {}

    public:
        // 取出对应的正向迭代器
        iterator_type base() const
        {
            return current;
        }

        // 重载操作符
        reference operator*() const
        { // 实际对应正向迭代器的前一个位置
            auto tmp = current;
            return *--tmp;
        }
        pointer operator->() const
        {
            return &(operator*());
        }

        // 前进(++)变为后退(--)
        self &operator++()
        {
            --current;
            return *this;
        }
        self operator++(int)
        {
            self tmp = *this;
            --current;
            return tmp;
        }
        // 后退(--)变为前进(++)
        self &operator--()
        {
            ++current;
            return *this;
        }
        self operator--(int)
        {
            self tmp = *this;
            ++current;
            return tmp;
        }

        self &operator+=(difference_type n)
        {
            current -= n;
            return *this;
        }
        self operator+(difference_type n) const
        {
            return self(current - n);
        }
        self &operator-=(difference_type n)
        {
            current += n;
            return *this;
        }
        self operator-(difference_type n) const
        {
            return self(current + n);
        }

        reference operator[](difference_type n) const
        {
            return *(*this + n);
        }
    };

    // 重载 operator-
    template <class Iterator>
    typename reverse_iterator<Iterator>::difference_type
    operator-(const reverse_iterator<Iterator> &lhs,
              const reverse_iterator<Iterator> &rhs)
    {
        return rhs.base() - lhs.base();
    }

    // 重载比较操作符
    template <class Iterator>
    bool operator==(const reverse_iterator<Iterator> &lhs,
                    const reverse_iterator<Iterator> &rhs)
    {
        return lhs.base() == rhs.base();
    }

    template <class Iterator>
    bool operator<(const reverse_iterator<Iterator> &lhs,
                   const reverse_iterator<Iterator> &rhs)
    {
        return rhs.base() < lhs.base();
    }

    template <class Iterator>
    bool operator!=(const reverse_iterator<Iterator> &lhs,
                    const reverse_iterator<Iterator> &rhs)
    {
        return !(lhs == rhs);
    }

    template <class Iterator>
    bool operator>(const reverse_iterator<Iterator> &lhs,
                   const reverse_iterator<Iterator> &rhs)
    {
        return rhs < lhs;
    }

    template <class Iterator>
    bool operator<=(const reverse_iterator<Iterator> &lhs,
                    const reverse_iterator<Iterator> &rhs)
    {
        return !(rhs < lhs);
    }

    template <class Iterator>
    bool operator>=(const reverse_iterator<Iterator> &lhs,
                    const reverse_iterator<Iterator> &rhs)
    {
        return !(lhs < rhs);
    }

} // namespace mystl

#endif /* __ITERATOR_HPP__ */

源码解析 :

定义了五个迭代器标签类:

  • input_iterator_tag:输入迭代器

  • output_iterator_tag:输出迭代器

  • forward_iterator_tag:前向迭代器,继承自输入迭代器

  • bidirectional_iterator_tag:双向迭代器,继承自前向迭代器

  • random_access_iterator_tag:随机访问迭代器, 继承自双向迭代器

定义了一个迭代器模板类 iterator,其中包含以下类型别名:

  • iterator_category:迭代器类型标签

  • value_type:所指对象类型

  • pointer:指针类型

  • reference:引用类型

  • difference_type:两个迭代器之间距离的类型,通常是 ptrdiff_t

定义了一个迭代器 traits 模板类 iterator_traits,它提供一些辅助函数来访问迭代器的属性,例如:

  • iterator_category:获取迭代器类型标签

  • value_type:获取所指对象类型

  • pointer:获取指针类型

  • reference:获取引用类型

  • difference_type:获取距离类型

定义了一些类型判断模板类:

  • has_iterator_cat:检查是否有迭代器类型标签

  • has_iterator_cat_of:检查迭代器类型标签是否匹配

  • is_input_iterator:检查是否为输入迭代器

  • is_output_iterator:检查是否为输出迭代器

  • is_forward_iterator:检查是否为前向迭代器

  • is_bidirectional_iterator:检查是否为双向迭代器

  • is_random_access_iterator:检查是否为随机访问迭代器

  • is_iterator:检查是否为迭代器(输入或输出)

定义了一些迭代器操作函数:

  • distance:计算两个迭代器之间的距离

  • advance:将迭代器前进指定步数

  • reverse_iterator:一个反向迭代器模板类,可以通过它来实现反向遍历文章来源地址https://www.toymoban.com/news/detail-518597.html

到了这里,关于【c++手撕STL】之迭代器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++ stl迭代器的理解

    首先,stl采用了泛型编程,分成了容器和算法,容器和算法之间的桥梁是迭代器,迭代器的作用是可以让算法不区分容器来作用在数据上。 迭代器本质上是指针,原有类型(比如int,double等)的指针也可以是迭代器,那如何让代码区分开他们呢? 我们可以把自定义的迭代器包

    2024年02月15日
    浏览(51)
  • C++ STL学习之【反向迭代器】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 A year from now you may wish you had started today. 明年今日,你会希望此时此刻的自己已经开始行动了。 适配器模式是 STL 中的重要组成部分,在上一篇文章中我们学习了 容器适配器 的相关知识,即 stack 与 queu

    2023年04月25日
    浏览(48)
  • 【C++】STL反向迭代器模拟实现,迭代器适配器,迭代器类型简单介绍

    本篇主要讲反向迭代器的模拟实现。 能够加深各位对泛型的理解。 前面我那篇string介绍里面已经提到过反向迭代器是啥了,如果点进来的同学还不知道,可以看看:[string介绍](https://blog.csdn.net/m0_62782700/article/details/130796914? spm=1001.2014.3001.5501) 迭代器,可以在不暴露底层实现细

    2024年02月16日
    浏览(46)
  • 【C++】STL——反向迭代器的模拟实现:迭代器适配器

    反向迭代器的使用相信大家都已经比较熟悉了,那我们这篇文章具体讲什么呢? 🆗,这篇文章我们重点来讲一下 反向迭代器的模拟实现 。 那为什么我们之前不和正向迭代器放在一块讲呢?为什么要等到我们讲完了容器适配器再来讲反向迭代器的模拟实现呢? 那这个问题我

    2024年02月08日
    浏览(41)
  • [ C++ ] STL---反向迭代器的模拟实现

    目录 前言: 反向迭代器简介 list反向迭代器的模拟实现  反向迭代器的模拟实现(适配器模式) SGI版本STL反向迭代器源码 STL库中解引用操作与出口设计 适配list的反向迭代器 适配vector的反向迭代器 反向迭代器 是一种特殊类型的迭代器,它可以 逆向遍历容器中的元素 ,与正向

    2024年04月15日
    浏览(39)
  • 10.1 C++ STL 模板适配与迭代器

    STL(Standard Template Library)标准模板库提供了模板适配器和迭代器等重要概念,为开发者提供了高效、灵活和方便的编程工具。模板适配器是指一组模板类或函数,它们提供一种适配机制,使得现有的模板能够适应新的需求。而迭代器则是STL中的令一种重要的概念,它是一个抽

    2024年02月12日
    浏览(44)
  • [C++] STL_vector 迭代器失效问题

    **迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装, 比如: string的迭代器就是原生指针char ,vector的迭代器就是原生态指针T 。 因此 迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块

    2024年02月11日
    浏览(44)
  • 深入探究C++中的STL:容器、迭代器与算法全解析

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

    2024年02月05日
    浏览(72)
  • 【C++进阶(三)】STL大法--vector迭代器失效&深浅拷贝问题剖析

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 在阅读本篇文章前,一定要先看前集: vector深度剖析(上) 本章重点: 本章会重点讲解vector迭代器失效问题 以及vector中的深浅拷贝问题 并且简

    2024年02月11日
    浏览(41)
  • 【C++进阶(四)】STL大法--list深度剖析&list迭代器问题探讨

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 本质重点: 本章重点讲解list的接口函数的熟悉 并且讲解list迭代器失效的特性 最后讲解迭代器的功能分类以及 算法库函数中谁能用谁不能

    2024年02月09日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包