MyTinySTL 简单分析(一)--iterator.h

发布时间:2024年01月16日

MyTinySTL 简单分析

目前在学习STL,看到一个开源的项目MyTinySTL,非常不错。想着照着这个代码自己敲一遍应该也能有些进步。然后就开始了学习过程。

首先分析的是vector

以下是由vector.h关联的所有头文件

其中有几个文件是重复的,例如type_traits.h 等

下面是一一分析每个文件。

  1. type_traits.h

这个文件比较简单,主要定义了两个结构体

m_true_type
m_false_type

这两个都从下面这个结构体继承而来,

struct m_integral_constant
{
???static constexpr T value = v;
};

所以都有一个value值,分别是true,false;

然后还定义了is_pair

2. iterator.h

这个文件是迭代器

下面两个链接讲的比较清楚

MyTinySTL学习之迭代器:iterator.h(一) - 掘金

https://juejin.cn/post/7110201852053946404

首先,迭代器需要associate type(一共五个)

这五个associated type 的作用如下:

这5个iterator的associated?type分别可以回答算法以下5个问题

  • iterator_category:迭代器的类型(决定了迭代器可以怎么走,例如vector的迭代器可以随机访问,而链表的迭代器一次只能走一步)
  • value_type:迭代器所指容器中元素的类型
  • difference_type:迭代器距离范围(即迭代器相减结果的范围)对应的类型,一般是内置类型ptrdiff_t,(eg.如果容器的容量范围是[0,232-1],则可以将difference_type定义为unsigned int)
  • reference:迭代器所指容器中元素的引用类型
  • pointer:迭代器所指容器中元素的指针类型 【NOTE】:每个容器都要实现自己的迭代器,为什么要在iterator.h中定义上面这段代码?
  • 如何获取迭代器的associated type? iterator_traits盛大出场!
  • 由于算法和容器之间是通过iterator来交互的,算法工作的时候需要知道的详细信息就是通过iterator,所以iterator 就定义了公共的接口和类型,
  • 在实际中,不只class可以作为iterator,基本类型如int也可以作为iterator。class iterator 可以定义如上几个associated type,但是基本类型没有,所以这是需要iterator_traits 来统一。

iterator_traits_impl有两个定义,如果第二个模板参数为true时,则定义了五个类型,否则为空。

iterator_traits_helper也有两个定义,如果第一个模板参数Iterator的iterator_category

input_iterator_tag?或 output_iterator_tag?时,则从上面定义了五个iterator_traits_impl继承。否则继承上面空的iterator_traits_impl,也为空

?iterator_traits?继承自iterator_traits_helper,继承时传递的第二个模板参数使用了has_iterator_cat<Iterator::value

has_iterator_cat?的value值是怎么来的呢?

// 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);
    // 如果传进来的T有iterator_category, 则会进入第二个test,返回的是char,则value 为true
};

根据它的定义,它有两个函数,分别返回two体和char,two结构体有两个char,如果传进来的模板参数Iter有iterator_category,则返回char,那么成员变量value则为true,否则为false。

这样一来iterator_traits?传进来的Iterator,如果有category,则会包含上面iterator_traits_impl的五个类型。

另外 iterator_traits?实现了两个偏特化版本。

到此iterator_traits可以完美的在任何情况下都能萃取出不同iterator的五个associated_type

========================

萃取出了迭代器,下面需要判断是哪种类型的迭代器,即

is_input_iteratoris_output_iteratoris_forward_iterator

is_bidirectional_iteratoris_random_access_iterator

这五个都继承自has_iterator_cat_of, 而这个has_iterator_cat_of?继承自m_bool_constant,其中会含有true 或false

has_iterator_cat_of, 根据第三个模板参数,有两个定义,

1)没有第三个模板参数,则继承自m_false_type, 那么value就是false

2)存在第三个模板参数,则正常继承,第一个目标参数的iterator_category 是否可以可以相互转化为第二个模板参数U作为父类m_bool_constant的参数

========================

再后面就是定义了萃取某个迭代器的category, distance_type, value_type,等

===================

再后面定义了计算iterator的距离,让iterator往前后走等

================

最后定义了一个reverse_iterator,主要实现了前进变后退,后退变前进。

=====================

综上,以上便是对iterator.h 的分析

文章来源:https://blog.csdn.net/gengxt2003/article/details/135620716
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。