C++实现STL迭代器萃取的示例代码

目录
  • 导言
    • 什么是迭代器
    • 为什么需要迭代器萃取
  • value type
  • difference type
  • reference type
  • point type
  • iterator_category
  • 知识点补充
  • 例外

导言

什么是迭代器

迭代器是一种抽象的设计概念,《Design Patterns》一书中对于 iterator 模式的定义如下:提供一种方法,使之能够依序巡访某个聚合物(容器)所含的各个元素,而又无需暴露该聚合物的内部表述方式。

为什么需要迭代器萃取

有时在我们使用迭代器的时候,很可能会用到其相应型别(associated type)。什么是相应型别,迭代器所指之物的型别、所属的类型(随机迭代器、单向双向、只读只写)便是。

如果我们想要以迭代器所指之物型别为类型声明一个变量,该怎么办呢?

一种解决方法是:利用 function template 的参数推倒(argument deducation)机制。

例如:

template <class I, class T>
void func(I iter, T t) {
	T tmp;	// 成功声明了迭代器所指之物类型的变量
}

template <class I>
void func(I iter) {
	func_impl(iter, *iter);
}

int main() {
	int num = 0;
    func(&num);
}

但迭代器的型别不只是迭代器所指对象的型别,而且上述解法并不能用于所有情况,因此需要更加全面的解法。

比如上述解法就无法解决 value type 用于函数返回值的情况,毕竟推导的只是参数,无法推导返回值型别。

声明内嵌类型似乎是个很好的方法,像这样:

template <class T>
struct MyIter {
	typedef T value_type;
    T* ptr;

    MyIter(T* p) {
        ptr = p;
    }
    T& operator*() {
        return *ptr;
    }
};

template <class I>
typename I::valie_type func (I ite) {	// typename I::valie_type 为返回值类型
	return *ite;
}

MyIter<int> ite(new int(1231));
cout << func(ite) << endl;

此处 typename 的作用是告诉编译器这是一个类型,因为 I 是一个模板参数,在它被具现化之前编译器对它一无所知,也就是说编译器不知道 I::valie_type 是个类型或是成员函数等等。

更多关于 typename 的用法可以查看文末补充内容

还有一种情况是上述代码无法解决的,那就是不是所有的迭代器都是 class type,原生指针就不是。如果不是 class type 就无法为它定义内嵌型别,因此我们需要对原生指针作些特殊处理。

例如:

template <class I>
struct iterator_traits {
    typedef typename I::value_type value_type;
};
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;
};

此时,不管是 class type 类型的迭代器还是原生指针都可以处理了。

迭代器萃取,就是为我们榨取出迭代器的相应型别。当然,要使萃取有效的运行,每个迭代器都要自行以内嵌性别定义(nested typedef)的方式定义出相应型别。

最常用的迭代器型别有五种:value type,difference type,pointer,reference,iterator catagoly。

迭代萃取机 traits 会很忠实地将它们榨取出来:

template <class I>
struct iterator_traits {
    typedef typename I::iterator_category     iterator_category;
    typedef typename I::value_type            value_ type;
    typedef typename I::difference_type        difference_type;
    typedef typename I::pointer                pointer;
    typedef typename I::reference            reference;
};

iterator_traits 必须针对传入型别为 point 及 point-to-const 者,设计特化版本。

value type

value type 是指迭代器所指对象的型别。

做法如上文所述。

difference type

difference type 用来表示两个迭代器之间的距离。对于连续空间的容器来说,头尾之间的距离就是最大容量,因此它也可以用来表示一个容器的最大容量。

如果一个泛型算法提供记数功能,例如 STL 的 count(),其返回值就必须使用迭代器的 difference type:

template<class I, class T>
typename iterator_traits<I>::difference_type        // 返回值类型,实际是 I::difference type
    count(I first, I last, const T& value) {
    typename iterator_traits<I>::difference_type ret = 0;
    for (; first != last; ++first) {
        if (*first == value) {
            ret++;
        }
    }
    return ret;
}

针对相应型别 difference type,traits 的两个特化版本,以 C++ 内建的 ptrdiff_t 作为原生指针的 difference type。

template <class I>
struct iterator_traits {
    typedef typename I::difference_type difference_type;
};
template <class T>
struct iterator_traits<T*> {
    typedef ptrdiff_t difference_type;
};
template <class T>
struct iterator_traits<const T*> {
    typedef ptrdiff_t difference_type;
};

reference type

从迭代器所指之物的内容是否允许改变的角度来说,迭代器分为两种:不允许改变所指对象的内容者,称为 constant iterators;允许改变所指对象的内容者,称为 mutable iterators。当我们对允许改变内容的迭代器进行解引用操作时,获得的不应是一个右值,应该是一个左值,因为右值不允许赋值操作。

在 C++ 中,函数如果要传回左值,都是以引用的方式进行。所以当 p 是个 mutable iterators 时,如果其 value type 是 T,那么 *p 的型别不应该是 T,而应是 T&。同样的,如果 p 是一个 constant iterators,其 value type 是 T,那么 *p 的型别不应该是 const T,而应该是 const T&。实现将在下一部分给出。

point type

同样的问题也出现在指针这里,能否改变所指地址的内容,影响着取出的指针类型。

实现如下:

template <class I>
struct iterator_traits {
    typedef typename I::pointer     pointer;
    typedef typename I::reference    reference;
};
template <class T>
struct iterstor_traits<T*> {
    typedef T*     pointer;
    typedef T&     reference;
};
template <class T>
struct iterstor_traits<const T*> {
    typedef const T*    pointer;
    typedef const T&     reference;
};

iterator_category

根据移动特性与施行操作,迭代器被分为五类:

前三种支持 operator++,第四种再加上 oprerator--,最后一种则涵盖所有指针算术能力。

这些迭代器的分类与从属关系,可以用下图表示。直线与箭头并非表示继承关系,而是所谓概念与强化的关系。更类似于,随机迭代器是一个双向迭代器,双向迭代器也是一个单向迭代器的概念。

设计一个算法时,要尽可能针对图中某种迭代器提供一个明确定义,并针对更加强化的某种迭代器提供另一种定义,这样才能在不同情况下提供最大效率。

以 distance() 为例

distance() 函数用来计算两个迭代器之间的距离。针对不同的迭代器类型,它可以用不同的计算方式,带来不同的效率。

template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
    __distance(InputIterator first, InputIterator last,
              input_iterator_tag) {
	iterator_traits<InputIterator>::iteratordifference_type n = 0;
    // 逐一累计距离
    while (first != last) {
		++first;
        ++n;
    }
    return n;
}

template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
    __distance(RandomAccessIterator first, RandomAccessIterator last,
               random_access_iterator_tag) {
    // 直接计算差距
    return last - first;
}

// InputIterator 命名规则:所能接受的最低阶迭代器类型
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last) {
	typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first, last, category());
}

知识点补充

typename 的用法

Usage

typename 主要有两个作用,让我们先来看看标准手册对该关键字的说明。

In the template parameter list of a template declaration, typename can be used as an alternative to class to declare type template parameters.

在模板声明的模板参数列表中,typename 可以用来替换 class 声明模板参数类型

Inside a declaration or a definition of a template, typename can be used to declare that a dependent qualified name is a type.

在模板的声明或定义中,typename 可以用来声明从属名称是一种类型

声明模板参数类型

以下 tempalate 声明式中,class 和 typename 用什么不同?

template <class T>
class Qgw;

​​​​​​​template <typename T>
class Qgw;

答案:完全一样。标准中说 typename 可以用来替换 class 声明模板参数类型,并没有说在此时有什么不同。

声明嵌套从属名称

在了解这个作用前,我们需要先学习两种名称,从属名称(dependent names)和嵌套从属名称(nested dependent name)。

让我们来看这样一段代码,代码本身并没有实际意义。

// C 接收一个 STL 容器类型
// 这份代码并不正确
template <class C>
void Test(C& container) {
    C w;
    C::iterator iter(container.begin());
}

在上述代码中有两个局部变量 w 和 iter。w 的类型是 C,实际是什么取决于 template 参数 C。template 内出现的名称如果依赖于某个 template 参数称之从属名称。如果从属名称在 class 内呈嵌套状,就称为嵌套从属名称,像 iter 的类型为 C::iterator,就是一个嵌套从属名称。

嵌套状的理解:C 是一个 template 参数,在它被编译器具现化之前,编译器并不知道它是什么,也就无从得知 C 里面的 iterator 究竟是个类型还是函数又或是其他东西,因此需要我们用 typename 来指出它是一个类型。

嵌套从属名称有可能导致解析困难,先来看个比较极端的例子:

template <class C>
void Test(C& container) {
    C::iterator* x;
    ...
}

上述代码我们声明了一个局部变量 x,它是个指针,指向一个 C::iterator。但它之所以被这么认为,是因为我们已经知道 C::iterator 是个类型。如果 C::iterator 不是个类型呢?如果 C 有个 static 成员变量而又刚好叫 iterator,或者 x 是个全局变量呢?那样的话上述代码不再是声明一个局部变量,而是一个相乘动作。

在我们知道 C 是什么之前,没有任何办法可以知道 C::iterator 是否是一个类型。C++ 有个规则可以解析这一歧义状态:如果解析器在 template 中遇到一个嵌套从属名称,它便假设这名称不是一个类型,除非你明确指出它是一个类型。所以缺省情况下嵌套从属名称不是类型,有两个例外会在下面指出。

我们可以用 typename 来明确指出嵌套从属名称是一个类型,标准中写到 typename 可以用来声明从属名称是一种类型。于是我们可以这样修改代码:

template <class C>
void Test(C& container) {
    C w;
    typename C::iterator iter(container.begin());
    typename C::iterator* x;
}

一个简单的规则:任何时候当你想在 template 中指涉一个嵌套从属名称,就必须在它的前一个位置放上关键字 typename。

typename 只能被用来验明嵌套从属名称,其他名称不该有它存在。

template <class C>
void Test(const C& container,             // 不允许使用 typename,vs 下没报错,g++ 报错了
          typename C::iterator iter);    // 一定要使用 typename

例外

typename 不可以出现在 base classes list 内嵌套从属名称之前,也不可以在 member initialization list(成员初始化列表)中作为 base class 修饰符。例如:

temalate <class T>
class Derived : public Base<T>::Nested {// base classes list 中不允许 typename
public:
    Derived (int x)
        : Base<T>::Nested(x) {            // mem.init.list 中不允许 typename
        typename Base<T>::Nested temp;    // 既不在 base classes list 也不在 mem.init.list 需要加 typename
    }
}

到此这篇关于C++实现STL迭代器萃取的示例代码的文章就介绍到这了,更多相关C++ STL迭代器萃取内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们

(0)

相关推荐

  • 浅谈c++ stl迭代器失效的问题

    之前看<C++ Primier>的时候,也解到在顺序型窗口里insert/erase会涉及到迭代器失效的问题,并没有深究.今天写程序的时候遇到了这个问题. 1 莫名其妙的Erase 最初我的程序是酱紫的,别说话,我知道这样是有问题的,可这样是最直观的想法 int arr[]={0,1,2,3,4,5,6,7,8,9,10}; vector<int> a(arr,arr+sizeof(arr)/sizeof(*arr));for (auto it = a.begin(); it !=

  • C++浅析STL 迭代器 容器的使用

    目录 STL定义 STL六大组件 vector vector嵌套容器 STL定义 STL(Standard Template Library 标准模板库) STL从广义上分为:容器(container) 算法(algorithm) 迭代器(iterator) 容器和算法之间通过迭代器进行无缝连接 STL几乎所有的代码都采用了模板类或者模板函数 STL六大组件 STL大体分为六大组件,分别是: 容器.算法.迭代器.仿函数.适配器.空间配置器 1.容器: 各种数据结构,如vector.list.de

  • 详解C++ 的STL迭代器原理和实现

    1. 迭代器简介 为了提高C++编程的效率,STL(Standard Template Library)中提供了许多容器,包括vector.list.map.set等.然而有些容器(vector)可以通过下标索引的方式访问容器里面的数据,但是大部分的容器(list.map.set)不能使用这种方式访问容器中的元素.为了统一访问不同容器时的访问方式,STL为每种容器在实现的时候设计了一个内嵌的iterator类,不同的容器有自己专属的迭代器(专属迭代器负责实现对应容器访问元素的具体细节),使用迭代

  • C++ STL反向迭代器的实现

    反向迭代器其实就行对正向迭代器进行封装,源生迭代器,为了实现运算符的结果不同,正向迭代器也对源生迭代器进行了封装. 反向迭代器的适配器,就是 Iterator是哪个容器的迭代器,reverse_iterator < Iterator >就可以 适配出哪个容器的反向迭代器.复用的体现. 反向迭代器适配器结构: template <class Iterator, class Ref, class Ptr> class reverse_iterator { typedef reverse

  • C++实现STL迭代器萃取的示例代码

    目录 导言 什么是迭代器 为什么需要迭代器萃取 value type difference type reference type point type iterator_category 知识点补充 例外 导言 什么是迭代器 迭代器是一种抽象的设计概念,<Design Patterns>一书中对于 iterator 模式的定义如下:提供一种方法,使之能够依序巡访某个聚合物(容器)所含的各个元素,而又无需暴露该聚合物的内部表述方式. 为什么需要迭代器萃取 有时在我们使用迭代器的时候,很可能会用

  • Python 微信公众号文章爬取的示例代码

    一.思路 我们通过网页版的微信公众平台的图文消息中的超链接获取到我们需要的接口 从接口中我们可以得到对应的微信公众号和对应的所有微信公众号文章. 二.接口分析 获取微信公众号的接口: https://mp.weixin.qq.com/cgi-bin/searchbiz? 参数: action=search_biz begin=0 count=5 query=公众号名称 token=每个账号对应的token值 lang=zh_CN f=json ajax=1 请求方式: GET 所以这个接口中我们

  • Node.js实现简单的爬取的示例代码

    学习[node.js]也有几天时间了,所以打算写着练练手:索然我作为一个后端的选手,写起来还有那么一丝熟悉的感觉.emmm~~ '货'不多讲 ,开搞........ 首先是依赖选择: 代码块如下: //引入依赖 //https请求 const https = require('https'); //简称node版的jquery const cheerio = require('cheerio'); //解决防止出现乱码 const iconv = require('iconv-lite') //

  • Python函数的迭代器与生成器的示例代码

    函数的迭代器 函数的强大功能叫做迭代器,Python里面最具威力的功能之一.迭代器我们听起来会感觉非常陌生,在list.tuple都有用到它,我们是使用for和in取列表中的每一个元素,对每个元素依次处理,这种方法就叫做迭代,实现这种方法的函数叫做迭代器.迭代器中有两个基本的函数,这个函数叫做方法,这个是面向对象编程称呼的一个方法,这两个方法叫做iter()和next(). 1.什么是迭代?迭代是一个重复的过程,并且每次重复都是基于上一次的结果而来 2.要想了解迭代器到底是什么?必须先了解一个概

  • js动态添加删除,后台取数据(示例代码)

    环境描述:就像你一般在论坛上发表文章,可能带附件,附件的数量是你手动添加删除的!!/*************************************************************************** 添加审批表单模板************************************************************************/// 增长的索引var itemIndex = 1000;// 数量var counter = 0;/

  • 从c++标准库指针萃取器谈一下traits技法(推荐)

    本篇文章基于gcc中标准库源码剖析一下标准库中的模板类pointer_traits,并且以此为例理解一下traits技法. 说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的. 还是先看一下思维导图,如下: 1. 指针萃取器pointer_traits说明 首先说明一下哈,官方并没有指针萃取器这个名称,其实pointer_traits是类模板,它是c++11以后引入的,可以通过传入的重绑定模板类型得到相应的指针类型,比较官方的描述是:pointer_traits 类模板提供标准

  • C++常见的stl容器与相关操作 示例解析

    目录 sort排序 vector map unordered_map set queue stack 创建容器时指定排序规则 sort排序 针对含有迭代器的容器,可以用#include<algorithm>中的sort函数进行排序. 默认排序是从小到大,可以自己写仿函数,也可以用greater<int>()或者less<int>(). #include <vector> #include <algorithm> #include <iost

  • C++ STL容器与函数谓词示例分析讲解

    目录 1.C++ vector向量 2.C++ stack 栈 3.C++ queue 队列 4.优先级队列 5.C++ list 6.c++ set 集合 7.C++ map函数 8.C++ multimap容器 9.C++ 谓词 10.C++内置预定义函数 C++ STL(Standard Template Library标准模板库),相当于java的集合模块, STL 有很多的容器. 1.C++ vector向量 (内部:封装动态大小数组作为容器,能够存放任意的动态数组) #include

  • C++模拟实现STL容器vector的示例代码

    目录 一.vector迭代器失效问题 二.模拟实现构造函数调用不明确 1.问题描述 2.解决调用不明确的方法 三.reserve中的深浅拷贝问题 1.reserve中浅拷贝发生原因 2.浅拷贝发生的图解 3.解决方法 四.模拟实现vector整体代码 一.vector迭代器失效问题 1.Visual Studio和g++对迭代器失效问题的表现 int main(){ std::vector<int>v{1,2,3,4}; std::vector<int>::iterator it

随机推荐