Posts

【C++ STL应用与实现】18: 如何使用迭代器适配器

28 Dec 2015

本系列文章的目录在这里:目录. 通过目录里可以对STL总体有个大概了解 #前言 本文介绍了STL中的迭代器适配器(iterator adapter)的概念及其使用方法示例。迭代器适配器可以和标准库中的算法配合使用,达到一些特殊的效果。 迭代器适配器分为以下几类:

  • reverse iterator : 反向迭代器
  • insert iterator : 插入型迭代器
  • stream iterator : 流迭代器
  • move iterator : 移动型迭代器
...

阅读全文 ...


【C++ STL应用与实现】16: 迭代器综述

27 Dec 2015

本系列文章的目录在这里:目录. 通过目录里可以对STL总体有个大概了解 #前言 本文介绍了STL中的迭代器的概念和五种类别的迭代器:Output iterator, Input iterator, Forward iterator, Bidirectional iterator, Random-access iterator. 迭代器是为了表示容器中某个元素位置这个概念而产生的,有一般到特殊(“高级”)可以把它分成五类,如下表所示:

iterator分类 能力 由谁提供
Output iterator 输出迭代器 向前写 ostream, inserter
Input Input 输入迭代器 向前读, 每个元素只能读一次 istream
Forward iterator 前向迭代器 向前读 forward_list, unordered containers(无序容器)
Bidirectional iterator双向迭代器 可向前向后两个方向读取 list, set(multiset), map(multimap)
Random-access iterator 随机访问迭代器 随机读取 array, vector, deque, string, C风格数组
STL中的各种算法,包括<algorithm>中的以及各种容器的成员函数,还有各种功能函数,比如迭代器辅助函数(advance, next, prev, distance, iter_swap)等,有很多都是以迭代器作为输入参数的,这些函数中,形参类型越是“一般”,说明其使用范围越大。这里所说的“一般”指的就是上面5类迭代器中“低级”的迭代器,比如Input iterator和Output iterator就比Forward iterator一般,Forward iterator比Bidirectional iterator一般,Bidirectional iterator又比Random-access iterator一般。 假设有两个算法,f和g,f接受Input iterator类型的参数,而g接受Random-access类型的参数,那么f的作用范围就比g大,因为所有的Forward, Bidirectional和Random-access迭代器都可以作为f的参数,而g只能使用Random-access参数。 ...

阅读全文 ...


【C++ STL应用与实现】17: 如何使用迭代器辅助函数

26 Dec 2015

本系列文章的目录在这里:目录. 通过目录里可以对STL总体有个大概了解 #前言 本文介绍了STL中的迭代器辅助函数的用法及注意事项,这些迭代器辅助函数包括:advance, next (since C++11), prev (since C++11), distance, iter_swap. 使用这些辅助函数需要包含头文件:#include <iterator> advance, next, prev, distance这四个辅助函数使得所有迭代器都拥有类似随机访问迭代器的特性,比如advance(iter, n)可以使得前向迭代器直接向前移动n个位置,类似随机迭代器的iter+n操作。

使用迭代器辅助函数来实现独立于迭代器类型的代码

这四个辅助函数提供了一层新的抽象层,使得代码可以独立于迭代器的类型。使用这四个辅助函数来操作迭代器可以让我在更改容器类型和迭代器类型的时候不用修改迭代器访问的代码。如果我不使用这几个辅助函数,比如我对一个随机迭代器的操作,写成newPos = pos + 10, 这就要求只有随机迭代器才会通过编译。而若使用newPos = next(pos, 10), 那么就不会有随机迭代器的限制。即使我中途改变了容器和迭代器的类型,也不用修改这段代码。值得一提的是,使用这几个辅助函数并不会造成性能损失,因为其内部会根据迭代器的iterator traits采取不同的策略来移动迭代器,对随机迭代器调用这些函数是一个常量时间的操作,对前向和双向迭代器则和自己手写循环一样,是个线性时间的操作。

迭代器辅助函数并不检查范围越界,需调用者自行确保迭代器的有效性

因为这些函数只接受一个迭代器参数,无法知晓这个迭代器所在容器的信息,也就无法知道是否迭代器到达了begin()之前,或者到了end(), 它只会傻傻的按照你指定的移动次数一直++iter,或者iter+n。而我们知道,对end()进行++操作是未定义的行为。因此使用这些函数的时候,全靠我们调用者自己控制迭代器的合法性。 ...

阅读全文 ...


【C++ STL应用与实现】7: 如何使用std::forward_list 单链表 (since C++11)

25 Dec 2015

本系列文章的目录在这里:目录. 通过目录里可以对STL总体有个大概了解 #前言 本文介绍了STL中的序列式容器std::forward_list, 从它的名字就能推测出来,它是单向的,只能前进(forward). 确实如此,它其实就是对C语言风格的单链表的封装,仅提供有限的接口,相对于std::list(双向链表,并且定义很多接口)来说它节省了内存,同时又有比list更好的运行时性能;相对于自己实现的C风格的单链表(hand-written c-style linked list)而言,forward_list也有与其不相上下的效率表现. 正如标准库所说的那样:

forward_list设计的目标是, 使用forward_list不会比使用自己手写的C风格单链表有更多的时间和空间的开销, 任何有悖于这个目标的接口和特性都会被标准拒之门外”
...

阅读全文 ...


【C++ STL应用与实现】64: 如何使用shuffle和random_shuffle : 洗牌 (since C++11)

24 Dec 2015

本系列文章的目录在这里:目录. 通过目录里可以对STL总体有个大概了解 #前言 本文介绍了STL中的变序类算法(mutating algorithm)里面的洗牌算法:std::random_shuffle和std::shuffle. random_shuffle算法在C++11之前就已经存在,C++11之后由于右值引用的引入,它的使用范围变大了。 shuffle算法则是从C++11之后才开始出现,可以与随机数和分布库一起使用。 与本系列的其他文章一样,本文介绍该最新的使用方法,比如random_shuffle在C++11以后接收的第三个参数从左值引用改成了右值引用,使得能够传入临时对象和函数,也就是说其使用范围括大了。 ...

阅读全文 ...