专栏首页光城(guangcity)​C++ STL源码剖析之知其然,知其所以然,源码面前了无秘密!

​C++ STL源码剖析之知其然,知其所以然,源码面前了无秘密!

C++ STL源码剖析之实现一个简单的iterator_category

0.导语

本节使用上节Traits特性,研究iterator源码,来实现一个简单的iterator_category,同时对iterator的源码结构进行分析。

知其然,知其所以然,源码面前了无秘密!

1.利用萃取机实现一个简单的iterator_category识别

上一节指出了迭代器的作用,依旧如下图所示:

迭代器是指向序列元素的指针的一种抽象。通过使用迭代器,我们可以访问序列中的某个元素、改变序列中的某个元素的值、使迭代器向前或向后行走等等。

迭代器有常见有五种类型: value_type, difference_type, reference_type, pointer_type都比较容易在 traits 和相应偏特化中提取。

但是,iterator_category一般也有5个,这个相应型别会引发较大规模的写代码工程。

  • 单向移动只读迭代器 Input Iterator
  • 单向移动只写迭代器 Output Iterator
  • 单向移动读写迭代器 Forward Iterator
  • 双向移动读写迭代器 Bidirectional Iterator

例如:我们实现了 advanceII, advanceBI, advanceRAI 分别代表迭代器类型是Input Iterator,Bidirectional Iterator和Random Access Iterator的对应实现。

template<class Iterator>
void advance(Iterator& i) {
    if (is_random_access_iterator(i))
        advanceRAI(i,n);
    if (is_bidirectional_iterator(i))
        advanceBI(i,n);
    else
        advanceII(i,n);
}

但这样在执行时期才决定使用哪一个版本,会影响程序效率。最好能够在编译期就选择正确的版本。

重载这个函数机制可以达成这个目标。

而对于advanceXX()都有两个函数参数,型别都未定(因为都是模板参数)。为了令其同名,形成重载函数,我们必须加上一个型别已确定的函数参数,使函数重载机制得以有效运作起来。

设计如下:如果traits有能力萃取出迭代器的种类,我们便可利用这个"迭代器类型"相应型别作为advancexx的第三个参数,而这个相应型别必须是一个class type,不能只是数值号码类的东西,因为编译器需依赖它来进行重载决议

下面来进行实现,首先给出一个总体结构图:

定义出下面tag:

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 {};
// 继承的好处就是,当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag,它会沿继承向上找,知道符合条件

声明了一些列 tag 之后,我们就可以重载 advance函数,我们把这些函数用下滑线来定义,表示在内部使用,外部不可见。

// 继承的好处就是,当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag,它会沿继承向上找,知道符合条件
// input iterator
template<class inputIterator, class distance>
inline void __advance(inputIterator&i, distance n,
                      input_iterator_tag) {
    std::cout << "input tag" << std::endl;
}
// output iterator
template<class outputIterator, class distance>
inline void __advance(outputIterator&i, distance n,
                      output_iterator_tag) {
    std::cout << "output tag" << std::endl;
}

// forward iterator
template<class ForwardIterator, class Distance>
inline void __advance(ForwardIterator &i, Distance n,
                      forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline void __advance(BidiectionalIterator &i, Distance n,
                      bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;

}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator &i, Distance n,
                      random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;

}

定义萃取机:

// traits 型别
template<class I>
struct Iterator_traits {
    typedef typename I::iterator_category iterator_category;
};

// 针对原生指针设计的"偏特化版"
template<class I>
struct Iterator_traits<I *> {
    typedef random_access_iterator_tag iterator_category;
};
template<class I>
struct Iterator_traits<const I *> {
    typedef random_access_iterator_tag iterator_category;
};

对外暴露接口:

// 对外接口
template<class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    __advance(i, n, category()); // 各型别的重载
}

定义class type:

// class type
template<class Category>
struct iterator {
    typedef Category iterator_category;
};

开始测试,我们使用上述定义的class type与原生指针来测试,分别进入萃取机的普通萃取机与偏特化萃取机,看看是否得到相应的Tag。

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    advance(input, 10);
    advance(output, 10);
    advance(forward, 10);
    advance(bidect, 10);
    advance(random, 10);
    int *p=NULL;
    advance(p,10);
    return 0;
}

输出结果:

input tag
output tag
forward tag
bidrectional tag
randomaccess tag
randomaccess tag

一切如我们预期一样,通过萃取机,我们获得了每个迭代器的tag,以及原生指针的tag。

我们再想得复杂一些,如果我们想知道advance的返回类型,那如何做呢?

首先修改advance返回:

// 对外接口
template<class InputIterator, class Distance>
inline typename Iterator_traits<InputIterator>::iterator_category
advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    return __advance(i, n, category()); // 各型别的重载
}

紧接着修改__advance返回:

// input iterator
template<class inputIterator, class distance>
inline typename Iterator_traits<inputIterator>::iterator_category
__advance(inputIterator &i, distance n,
          input_iterator_tag) {
    std::cout << "input tag" << std::endl;
    return input_iterator_tag();
}

// output iterator
template<class outputIterator, class distance>
inline typename Iterator_traits<outputIterator>::iterator_category
__advance(outputIterator &i, distance n,
          output_iterator_tag) {
    std::cout << "output tag" << std::endl;
    return output_iterator_tag();
}

// forward iterator
template<class ForwardIterator, class Distance>
inline typename Iterator_traits<ForwardIterator>::iterator_category
__advance(ForwardIterator &i, Distance n,
          forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
    return forward_iterator_tag();
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline typename Iterator_traits<BidiectionalIterator>::iterator_category
__advance(BidiectionalIterator &i, Distance n,
          bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;
    return bidiectional_iterator_tag();
}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline typename Iterator_traits<RandomAccessIterator>::iterator_category
__advance(RandomAccessIterator &i, Distance n,
          random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;
    return random_access_iterator_tag();
}

只需要把void修改为相应的萃取机即可。

最后测试修改,添加上返回:

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    input_iterator_tag inputIteratorTag = advance(input, 10);
    output_iterator_tag outputIteratorTag = advance(output, 10);
    forward_iterator_tag forwardIteratorTag = advance(forward, 10);
    bidiectional_iterator_tag bidiectionalIteratorTag = advance(bidect, 10);
    random_access_iterator_tag randomAccessIteratorTag = advance(random, 10);
    int *p = NULL;
    random_access_iterator_tag v = advance(p, 10);
    return 0;
}

至此,一个简单的迭代器类型在编译器判别实现完毕。

2.STL源码剖析Iterator

bits/stl_iterator_base_types.h中也是如上述所示(实际上,上面就是STL源码的简单版,很接近),来我们一起来看。

(1)tag

 ///  Marking input iterators.
  struct input_iterator_tag { };

  ///  Marking output iterators.
  struct output_iterator_tag { };

  /// Forward iterators support a superset of input iterator operations.
  struct forward_iterator_tag : public input_iterator_tag { };

  /// Bidirectional iterators support a superset of forward iterator
  /// operations.
  struct bidirectional_iterator_tag : public forward_iterator_tag { };

  /// Random-access iterators support a superset of bidirectional
  /// iterator operations.
  struct random_access_iterator_tag : public bidirectional_iterator_tag { };

与我上面用的一样。

(2)iterator_traits萃取机,里面包含五种,而上面只是实现其中的一种:iterator_category。所以在STL中容器与算法之间的桥梁iterator必须包含下面五种 typedef。

template<typename _Iterator>
struct iterator_traits
{
  typedef typename _Iterator::iterator_category iterator_category;
  typedef typename _Iterator::value_type        value_type;
  typedef typename _Iterator::difference_type   difference_type;
  typedef typename _Iterator::pointer           pointer;
  typedef typename _Iterator::reference         reference;
};

(3)iterator

上面提到的class type为下面的简单版,对比一下,没有啥区别,就是模板参数多了一些,typedef多了。

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
       typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
  /// One of the @link iterator_tags tag types@endlink.
  typedef _Category  iterator_category;
  /// The type "pointed to" by the iterator.
  typedef _Tp        value_type;
  /// Distance between iterators is represented as this type.
  typedef _Distance  difference_type;
  /// This type represents a pointer-to-value_type.
  typedef _Pointer   pointer;
  /// This type represents a reference-to-value_type.
  typedef _Reference reference;
};

至此,iterator与traits特性分析完毕。欢迎与我共同探讨STL源码奥秘,如侯捷老师所说:源码面前了无秘密。

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 中秋节快乐,剖析STL源码,明白typename

    STL底层源码有下面几行,typedef与typename联用,这几个看着好复杂,究竟啥意思,我们今天一起来剖析!

    公众号guangcity
  • C++ STL源码剖析之Traits编程技法

    在 STL 编程中,容器和算法是独立设计的,即数据结构和算法是独立设计的,连接容器和算法的桥梁就是迭代器了,迭代器使其独立设计成为可能。如下图所示:

    公众号guangcity
  • MySQL实战七:你不知道的外键与约束使用!

    MySQL学习仓库Up-Up-MySQL,这是一个学习MySQL从入门实战到理论完善,再到精通的一个仓库,后面会把MySQL的学习资料上传上去!欢迎大家star...

    公众号guangcity
  • 20120918-双向链表类定义《数据结构与算法分析》

    将新的节点插入双向链表的时候: iterator insert(iterator itr,const Object & x)//向双向链表中插入一个x节点 { ...

    用户1154259
  • 轻松学Pytorch-使用卷积神经网络实现图像分类

    大家好,本篇教程的贡献者来自社区投稿作者【陨星落云】,使用CIFAR-10数据集进行图像分类。该数据集中的图像是彩色小图像,其中被分为了十类。一些示例图像,如下...

    OpenCV学堂
  • 虚拟内存探究 -- 第三篇:一步一步画虚拟内存图

    这是虚拟内存系列文章的第三篇。 前面我们提到在进程的虚拟内存中可以找到哪些东西,以及在哪里去找。 本文我们将通过打印程序中不同元素内存地址的方式,一步一步细...

    coderhuo
  • PDF转图片,在线PDF转JPG/PNG

    使用pdf.js预览图片,pdf.js将pdf通过canvas将每一页渲染出来,然后我们通过canvas的toDataURL方法保存为jpg或png格式。

    vivec
  • 微信小程序之支付详解(填坑) 原

    首先,你采用什么语言选择对应的sdk,记住:微信sdk默认签名是HMACSHA256,因为小程序只支持MD5,故你这里即使获取了prepay_id,在小程序发起...

    南郭先生
  • Newbe.Claptrap 框架入门,第二步 —— 简单业务,清空购物车

    接上一篇 Newbe.Claptrap 框架入门,第一步 —— 创建项目,实现简易购物车 ,我们继续要了解一下如何使用 Newbe.Claptrap 框架开发业...

    newbe36524
  • Python内置方法实现基于秘钥的信息加解密

    在实际编程开发中,我们会使用到各类的加密算法来对数据和信息进行加密。比如密码中比较常见的MD5加密,以及AES加密等等。

    州的先生

扫码关注云+社区

领取腾讯云代金券