STL中实现 iterator trail 的编程技巧
STL中实现 iterator trail 的编程技巧
《泛型编程和 STL》笔记及思考。
这篇文章主要记录在 STL 中迭代器设计过程中出现的编程技巧,围绕的 STL 主题为 (迭代器特征) Iterator traits 和 相关类型(Associated Types)。
首先介绍 Associated Types
Associated Types
我们知道,Iterator 是一种泛化的指针,我们有时会这样理解它:
指针(广义的)指向某个序列的一个 item,而每个 item 的类型就是我们想要的 Associated Types。
对于 C 中的指针来说,*ptr 就是他的相关类型。
对于我们之前定义的外覆类(C++ 泛型算法 find 那篇)来说,*int_node (即 Node)是他的相关类型。
现在我们有个问题,我们如何使用这个类型?假设有一个 Iterator type P,P 的相关类型为 value_type。我们想要在一些算法中使用这个类型声明一些临时变量(这很常见,比如在计算数值的算法内),然而 ”P 的 value_type “ 并没有告诉我们 C++ 如何表达这样的概念。比如在之前的外覆类中,我们可以通过外覆类的接口获得他的相关类型的具体引用,但是却没办法使用这个类型信息用于外覆类之外的变量的声明。
技巧一 :使用 C++ 的类型推断机制
假设有个泛型函数 f() ,需要一个类型为 P 的参数,而且还需要声明一个类型为 P 的 value_type 的临时变量。我们可以令 f() 成为一个单纯的传递函数,并将所有工作委托给内部函数 f_impl():
template <class P,class T> void f_impl(P iter,T t) { T tmp; ... } template <class T> inline void f(T iter) { f_impl(iter,*iter); }
于是,我们可以在函数 f_impl 之中,声明一个类型为 T 也即 P 的 value_type 类型的临时变量。template 参数的 “type inference” 机制是自动自发的,所以在 f_impl 之中,template 的参数 T 和 *iter 是同义的。
这个技巧的确能够解决我们之前提出的问题,但是,他却解决不了另一个问题,这个方案无法用来声明函数的返回类型。通过类型推导得到的 Associated Type 信息是在 f() 方法内获得的,我们无法将这个 Associated Type 用于函数的返回值。所以我们来看一下技巧二。
技巧二 : 嵌套声明
这种方法的核心思想是在每个迭代器类中将具体的 Associated Type 统一定义为一个新的名为value_type(又一次的隐藏了差异性)的类型。
用上一篇定义的外覆类 int_node 为例,为它增加一个新的类型 value_type:
template <class Node> //Node 是类型参数,可能用 T 更好理解 struct node_wrap { typedef Node value_type; Node *ptr; ... };
这样的话,只要我们知道这个迭代器的类名,便可以访问他的 Associated Type 。并且,在每个定义了 value_type 的迭代器都可以换通过相同的方法访问。
对于声明一个 node_wrap 的 Associated Type 类型的变量,我们可以这样:
typename node_wrap :: value_type tmp;
以这种方式来对变量命名。(typename 是为了向编译器指出这是类型名而不是成员方法名或其他)
声明函数的返回类型:
typename node_wrap:: value_type f(...) { ... }
这样做相当于我们再次将差异性隐藏,向外提供了一个统一的接口。
看起来这种方式解决了我们的问题。但是我们忽略了一些情况。上述成立的前提是迭代器是一个类,所以我们可以在它们内部增加一个新的类型,并从外部访问它。但是 C 中的指针也是一个迭代器,而且我们一直是在以 C 指针的行为来指导迭代器的行为。显然我们无法为 C 指针提供这种操作。为了解决这个问题,为指针也提供合适的操作,我们再次提出了新的方案。
技巧三 : 增加中间层和模板偏特化
我们可以增加一个中间层来解决这个问题。具体的做法是定义一个辅助用的 class,iterator_traits:
template <class Iterator> struct iterator_traits { typedef typename Iterator::value_type value_type; };
这么一来我们就可以以这样的写法来取用 Iterator 的 value_type(以声明变量为例):
typename iterator_traits<node_wrap>::value_type tmp;
这看起来没有任何改进,因为 Iterator_traits 仍然假设它的 template 参数 Iterator 有一个嵌套类型。(指针仍然没有)
不过,现在我们可以使用另一种技术来解决这个问题了。我们将利用 “对某种 template 参数提供另一种定义” 的方法,将 Iterator_traits class 特化。
C++ 中允许 template 的全特化(亦即为某型别如 int* 提供另一种定义)和偏特化(亦即提供另一个定义,其自身仍为模板化的。具体可参考 《C++ primer》)。在这个例子中,我们需要针对每一种指针类型做出另一种定义,因此我们需要偏特化:
template <class T> struct iterator_traits<T*> { typedef T value_type; };
现在,当我们面对普通的指针时,也可以像对待迭代器一样,使用相同的方法来取用它的 Associated Type。
主要的问题已经解决了,但是还有一个细节问题需要提出来讨论一下:constant iterator 的 value_type 是什么?考虑如下例子:
iterator_traits<const int*>::value_type
根据我们之前定义的 Iterator_traits value_type 将会是 const int 而非 int。我们已经针对 T* 的参数将 iterator_traits 特化,但当 T 是 const int 时,const int * 会符合 T* ,这不是我们期待的结果。
我们只需要另外设计一个版本的偏特化,就能轻而易举的解决这个问题:
template<class T> struct iterator_traits<cosnt T*> { typedef T value_type; };
现在我们有了三种不同的 itertaor_traits 版本。一个是针对类型为 T 的参数,一个是 T * ,另一个是 const T * 的参数。当你写下 iterator_traits<const int*> 时,原则上他符合任何一个版本,不会有歧义的情况发生。因为 C++ 编译器总能选出最能明确匹配的版本。
直到到现在,我们有了某种机制,让我们得以使用某个 iterator 的 value_type 来撰写算法。
举个例子,以下的泛型函数用来计算 nonempty range 内的数值总和:
template <class InputIterator> typename iterator_traits<InputIterator>::value_type sum_nonempty(InputIterator first,InputIterator last) { typename iterator_traits<InputIterator>::value_type result = *first; for (;first != last; ++first) result += *first; return result; }
感谢阅读
转载请注明出处
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java 基础 之 数据类型
http://www.verejava.com/?id=1699255932129 /** java 分为4类8种基本数据类型 4类: 1. 整型(byte,short,int,long) 2. 浮点型(float,double) 3. 字符型(char) 4. 布尔型(boolean) */ public class BaseDataType { public static void main(String[] args) { //整型 byte, short, int ,long byte a1=1; //byte 占 1个字节=8位 -2^7~2^7-1(-128~127) short a2=10; //short 占 2个字节=16位 -2^15~2^15-1 int a3=100; //int 占 4个字节=32位 -2^31~2^31-1 long a4=1000; //long 占 8个字节=64位 -2^63~2^63-1 System.out.println(a1); System.out.println(a2); System.out.println(a3); Sy...
- 下一篇
intellij idea tomcat热部署配置
1.设置Debugger-HotSwap 在setting界面,打开Debugger-HotSwap选项,确保勾选了Build project before reloading classes,同时选择Reload classes after compilation为Always。这样我们在编译某个修改了的java文件之后,就会利用HotSwap机制reload class,而Build project before reloading classes就确保了其他修改过的文件一起同步到部署目录。 2.项目设置 在Project Structure视图中,在Project setting --> Articfacts选项中,选择war:Exploded类型的modules,然后设置编译输出项目的路径 将你的构建输出目录直接设置在源程序目录中,然后重定向的docBase直接指向你的web根目录(就是WEB-INF的父目录)。这样,你只要将编译输出目录设置为WEB-INF\classes就行了,而且,修改JSP文件都不要重新构建,唯一要做的就是修改了java文件之后compile一下。...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果