泛型指标（Iterators）与 Traits 技术 侯捷 [email protected] http://www.jjhou.com 第一次发表於 Run!PC 杂志 March, 2000 1. 大局观：泛型程式设计与 STL 2000.02 => 2. 泛型指标（Iterators）与 Traits 技术 2000.03 3. 泛型容器（Containers）的应用与实作 2000.04 4. 泛型演算法（Generic Algorithms）的应用与实作 2000.05 5. Adaptor 与 Function Object 的应用与实作 2000.06 ------------------------------------------------------------ Iterators（泛型指标）的中心观点就是：如何让资料结构和演算法两者 之间能够彼此不互知地发展，而最後又能够没有间隙地胶合在一起。 注1：本文对 iterator 来龙去脉的说明，大量得助於 [Austern99]。 该书颇多笔误，本文已修正，并附上一个完整范例程式。 注2：本文所描述的 traits 技术，大量运用 struct。C++ 的 struct 几乎 等同於 class，唯一差别在於其内的存取层级预设为 public，而 class 内的存取层级预设为 private。 ●一个简易的例子 试看以下例子。假设有一个搜寻演算法 find()， 以线性搜寻的方式寻找指定的某个元素。这个任务可轻易以 function tempalte 完成： template <class I, class T> Iterator find(I first, I last, const T& value) { while (first != last && *first != value) ++first; return first; } 其中 template 参数 I 代表一个「类似指标」的东西，T 代表搜寻标的物的型别。 由於我们要求 I 具备类似指标的性质，所以它应有提领（dereference）、 累进（increment）的能力。这个 function template find() 是一个具备 泛型概念的演算法。 现在，假设有一个原本就已发展出来的资料结构 int_node： struct int_node { int val; int_node* next; }; 如何将这个资料结构套用在上述的 find() 演算法当中呢？我们需要 加上一层外包装。事实上，这种「加一层间接性」以解决问题的作法， 层出不穷地出现在电算领域中。 我们希望写出一个 wrapper class，权充 int_node 的指标。 当我们对它做提领（dereference）动作时，传回的是标的物 int_node； 当我们对它做累进（increment）动作时，则造成它指向（代表） 下一个 int_node object。 为了让这个 wrapper 适用於任何型别的 node（而不只限於 int_node）， 可以将它设计为一个 class template。以下就是我们的 node_wrap： template <class Node> struct node_wrap { Node* ptr; node_wrap(Node* p = 0) : ptr(p) { } // default ctor Node& operator*() const { return *ptr; } Node& operator->() const { return ptr; } // pre-increment operator node_wrap& operator++() { ptr = ptr->next; return *this; } // post-increment operator node_wrap& operator++(int) { node_wrap tmp = *this; ++*this; return tmp; } bool operator==(const node_wrap& i) const { return ptr == i.ptr; } bool operator!=(const node_wrap& i) const { return ptr != i.ptr; } }; 现在，我们可以这样子将它们搭配起来： void main() { int_node *list_head, *list_tail; int_node *in = new(int_node); in->val = 100; in->next = 0; list_head = list_tail = in; // list 头尾 for (int i=0; i<10;++i) { int_node* in = new(int_node); in->val = i; in->next = 0; list_tail->next = in; // list 串接 list_tail = in; } // 此时的 list 内容为 100,0,1,2,3,4,5,6,7,8,9 node_wrap<int_node> r; // VC6[o] CB4[x] G++[o] r = find(node_wrap<int_node>(list_head), node_wrap<int_node>(), 10); if (r != node_wrap<int_node>()) std::cout << (*r).val << std::endl; // output: none r = find(node_wrap<int_node>(list_head), node_wrap<int_node>(), 3); if (r != node_wrap<int_node>()) std::cout << (*r).val << std::endl; // output: 3 } 我们可否在上述 list_head 和 list_tail 指出的串列形成之後， 直接以 find(list_head, null, 5) 来搜寻 '5' 这个元素呢？如果这 能够成功，也就不需要大费周张地写一个 node_wrap 了。是的， 答案当然是不行，因为 find() 之中对於 iterator 的累进（++）动作， list_node 无法了解，无法提供对应的服务。 ●Iterator 相关型别（associated type） 上述的 node_wrap，提供了一个 iterator 雏形。如果将思绪拉得更远 更宏大一些，我们会发现，演算法之中用到 Iterator 时，很可能会 使用其相关型别（associated type）。什麽是相关型别？ 例如「iterator 所指标的物」的型别便是。当你有需要在演算法中 宣告一个以「iterator 所指标的物之型别」为型别的变数，如何是好？ 毕竟 C++ 并未支援 typeof(*iterator) 这样的指令！ 有一个解决办法：利用 function template 的引数推导。例如： // VC6 [o], BCB4 [o], G++ [o] template <class I, class T> void func_impl(I iter, T t) { T tmp; // ... }; template <class I> inline void func(I iter) { func_impl(iter, *iter); } int main() { int i; func(&i); } 我们以 func() 为对外介面，实际动作则全部设计在 func_impl() 中。 由於 func_impl() 是一个 function template，呼叫它时编译器会自动 进行 template 引数推导。於是推导出上例的 T type。顺利解决了问题。 template 引数推导机制（arguments deduction），在 STL 中占非常重要的角色。 Alexander Stepanov（STL 的创造者）在与 Dr. Dobb's Journal 进行 的访谈中说道：『1992 我重回 generic-library 的开发工作。 这时候 C++ 有了 template。我发现 Bjarne 完成了一个非常美妙的设计。 之前我在 Bell Lab 曾参与数次 template 的相关设计讨论，并且 非常粗暴地要求 Bjarne 应该将 C++ template 设计得尽可能像 Ada generics 那样。 我想由於我的争辩是如此地粗暴，他决定反对。我了解到在 C++ 中除了 拥有 template classes 之外还拥有 template functions 的重要性。 然而我认为 template function 应该像 Ada generics 一样，也就是说 它们应该是 explicit instantiated。Bjarne 没有听进我的话， 他设计了一个 template function 机制，其中的 template 是 以一个多载化机制（overloading mechanism）来进行 implicitly instantiated。 这项特殊的技术对我的工作具有关键性的影响，因为我发现它使我 得以完成 Ada 不可能完成的许多动作。我非常高兴 Bjarne 当初 没有听我的意见。』（请参考 DDJ 1995 年三月号） ●之一：value type Iterator 所指标的物之型别，我们称之为该 iterator 的 value type。 上述所谓的 "type inference trick"（型别推论技巧）虽然可用，却非 全面可用：万一 value type 必须用於函式的传回值，就没辄了，毕竟 函式的回返型别并不在 template 引数推导的参考范围内。 我们需要其他方法。使用巢状式的型别宣告似乎是个好主意。这次的作法 有点像先前所提的 node_wrap： // VC6 [o], BCB4 [o], G++ [o] #include <iostream> template <class T> struct MyIter { typedef T value_type; // nested type（巢状式的型别宣告） T* ptr; MyIter(T* p=0) { ptr = p; } ~MyIter() { delete ptr; } }; template <class T> typename MyIter<T>::value_type // 这是 func 的回返型别 func(MyIter<T> ite) { return *(ite.ptr); }; void main() { MyIter<int> ite(new int(8)); std::cout << func(ite) << std::endl; // 8 } 当我们把型别为 MyIter<T> 的 ite 传入函式时，函式便可以使用 typename MyIter<T>::value_type 做为型别；至於 ite 的指标性质则以 ite.ptr 来遂行。 这看起来不错。但是有个陷阱存在。并不是所有的 iterator 都是 class 或 struct。 原生指标就不是！但是 STL 必须接受原生指标做为一种 iterator。所以 上面这样还是不够。有没有什麽办法可以让上述的泛型概念针对特定的 某些情况做特殊的设计呢？ 有，利用 partial specialization 就可以做到。 任何完整的 C++ 书籍对於 partial specialization 均有说明。 大致的意思是：如果 class template 拥有一个以上的 template 参数， 我们可以针对某一个（或某一组）template 参数（而非针对所有的 tempalte 参数） 进行特殊化。也就是说，可以供应一个 template 版本，符合一般化条件， 但其中某些 template 参数已经被实际型别或数值取代。这可以被用来 定义一个比泛型版本更专属或是更有效率的实作品。 如果有一个 class template 如下： template<typename U, typename V, typename T> class C { ... }; 上述对 partial specialization 的定义，容易误导我们以为所谓 「局部性特制版本」一定是对 template 参数 U 或 V 或 T（或其任意组合） 指定特定引数值。事实不然，[Austern99] 对於 partial specialization 的定义使我们得以跳脱这样的框框。他说： 『所谓 partial specialization 的意思是提供另一份 template 定义式， 而其本身仍为 templatized』。 由此，面对以下的 class template： template<typename T> class C { ... }; // 这个泛型版本适用於任何型别的 template 引数 我们便容易接受它有一个型式如下的 partial specialization： template<typename T> class C<T*> { ... }; // 这个特殊版本适用於 template 引数为指标者 有了这项利器，我们可以解决前述「巢状式型别宣告」未能解决的问题。 先前的问题是，原生指标不是 class，因此无法为它们定义巢状型别。 现在，我们可以为指标型别的 template 引数设计 partial specialization。 假设我有一个 class template 如下： template <class Iterator> struct iterator_traits { // traits 是「特性」的意义 typedef typename Iterator::value_type value_type; }; 它有两个 partial specializations： template <class T> struct iterator_traits<T*> { // 针对「template 引数为指标型别」的特殊版本 typedef T value_type; }; template <class T> struct iterator_traits<const T*> { // 针对「template 引数为 const 指标型别」的特 殊版本 typedef T value_type; // 注意，型别为 T 而非 const T }; 於是当我们在 template function 中需要 I 的 value type 时，便可以这麽写： typename iterator_traits<I>::value_type; 不论 I 是任何型式的 iterator，甚至是原生指标，上行都成立。 这样的型别可以运用做为 algorithms 的函式回返型别，於是解决了先前的问题。 ●之二：difference type 另一个与 iterator 相关的型别是其 difference type，用来表示 两个 iterator 间的距离。也可以用来表示一个容器的最大容量。 这个问题仍然可利用前述的 traits 技术解决。至於原生指标， 我们可以设计对应的 partial specializations，在其中使用 C++ 语言内建的 ptrdiff_t（定义於 <cstddef> 表头档中）： template <class Iterator> struct iterator_traits { typedef typename Iterator::value_type value_type; typedef typename Iterator::difference_type difference_type; }; // partial specialization for regular pointers template <class T> struct iterator_traits<T*> { typedef T value_type; typedef ptrdiff_t difference_type; }; // partial specialization for regular const pointers template <class T> struct iterator_traits<const T*> { typedef T value_type; typedef ptrdiff_t difference_type; }; 於是当我们在 template function 中需要 I 的 difference type 时，便可以这麽写： typename iterator_traits<I>::difference_type; ●之三：reference type 从「iterator 所指标的物之内容是否允许改变」的角度观之，iterators 分 为两种：const（常数的）iterators 和 mutable（可变的）iterators。 当我们面对 mutable（可变的）iterators 做提领（dereference) 动作时， 获得的不应该是个 rvalue，必须是个 lvalue。C++ 函式如要传回 lvalue， 都是以 by reference 的方式传回，所以当 p 是一个 mutable iterators 时， 如果其 value type 是 T，那麽 *p 的型别不应该是 T，而应该是 T&。 以此道理扩充到 const iterators p 身上，如果其 value type 是 T， 那麽 *p 的型别不应该是 const T，而应该是 const T&。 换句话说 *p 的型别不应该是 p 的 value type，而应该是所谓 的 reference type。 ●之四：pointer type pointers 和 references 在 C++ 中有非常密切的关连。如果「传回一个 lvalue，代表 p 所指之标的物」是可能的，那麽「传回一个 lvalue， 代表 p 所指之标的物的位址」也一定是可能的。 也就是说，我们一定（必须）能够传回一个 pointer，指向该 object。 事实上这些 types 已经出现在本文一开始的 node_wrap class 中。 该 class 的 operator* 传回一个 Node&，operator-> 传回一个 Node*。 前者便是其 reference type，後者便是其 pointer type。 现在我们把两个新的 iterator associated types 加入 traits 内： template <class Iterator> struct iterator_traits { typedef typename Iterator::value_type value_type; typedef typename Iterator::difference_type difference_type; typedef typename Iterator::pointer pointer; typedef typename Iterator::reference reference; }; // partial specialization for regular pointers template <class T> struct iterator_traits<T*> { typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; }; // partial specialization for regular const pointers template <class T> struct iterator_traits<const T*> { typedef T value_type; typedef ptrdiff_t difference_type; typedef const T* pointer; typedef const T& reference; }; ●concept Iterator 的分类 最後一个 iterator associated type 会引发比较大的写码工程。 在那之前，我必须先讨论 Iterator 的分类。 Iterators 是一个 concept，而指标是其中一个 model。Iterators 并非 只是单一的 concept，它是一大家族，共有五个不同的 concepts： 1. Input Iterator - 不允许外界改变 iterator 所指物件。唯读（read only）性质。 2. Output Iterator -- 唯写（write only）性质。 3. Forward Iterator -- 允许「写入型」algorithms 使用同一个范围做读/写动作。 这样的 algorithms 例如 replace()。 4. Bidirectional Iterator -- 支援双向移动。某些 algorithms 需要 逆向巡访某个范围，例如逆向拷贝某范围内的元素，就可以使用 这种 Bidirectional Iterators。 5. Random Access Iterator -- 先前四种 iterator concepts 都只供应 一小组指标算术运算能力（(1),(2),(3) 允许 operator++， (4) 允许 operator--），Random Access Iterator 则涵盖其余 所有指标算术运算能力，包括 p+n, p-n, p[n], p1-p2, p1<p2。 此一 concept Iterators 的分类与从属关系，可以图一表示。 直线与箭头代表的并非 C++ 的继承关系，而是 concept 与 refinement 的关系。 图一/ concept iterators 的分类与从属关系 figure2.1 ●之五：iterator tags 通常，设计 algorithms 时，我们会令一个 algorithm 对 某种 iterator concept 提供一个明确的定义， 而针对该 concept 的 refinement 提供另一种定义。例如我们有个 algorithm 适用 Forward Iterator，那麽当然你以 Random Access Iterators 喂给他， 他也会接受，因为 Random Access Iterators 必然是 Forward Iterator（见图一）。 但是可用（usable）并不代表最佳（optimal）。 以 advance() 为例。这是其他 algorithms 内部常用的一个函式。 此函式有两个参数，iterator p 和数值 n；函式内部 将 p 累进 n 次（前进 n 距离）。下面有三种不同的 定义，一是针对 Input Iterator， 一是针对 Bidirectional Iterator， 一是针对 Random Access Iterator。并没有特别针对 ForwardIterator 而设计的版本，因为其动作和 InputIterator 版全无二致。 template <class InputIterator, class Distance> void advance_II(InputIterator& i, Distance n) { for ( ; n > 0; --n, ++i ); // 单向，逐一前进 } template <class BidirectionalIterator, class Distance> void advance_BI(BidirectionalIterator& i, Distance n) { if (n >= 0) // 双向，逐一前进 for ( ; n > 0; --n, ++i ) { } else for ( ; n < 0; ++n, --i ) { } } template <class RandomAccessIterator, class Distance> void advance_RAI(RandomAccessIterator& i, Distance n) { i += n; // 双向，跳跃前进 } 现在，当程式呼叫 advance()，应该使用上述哪一个定义呢？ 如果选择 advance_II，对 Random Access Iterator 而言 就极度缺乏效率，原本 O(1) 的操作竟成为 O(N)。如果选择 advance_RAI， 则它无法接受 Input Iterator。我们需要将三者合一。你可以想像成这样： template <class InputIterator, class Distance> void advance(InputIterator& i, Distance n) { if (is_random_access_iterator(i)) advance_RAI(i, n); else if (is_bidirectional_iterator(i)) advance_BI(i, n); else advance_II(i, n); } 但是在执行时期才决定哪一个版本，会影响程式效率。 最好是在编译期就选择正确的版本。多载化函式机制可以达成这个目标。 目前这三个 advance() 版本的两个函式参数，其型别都是 template 参数， 我们有必须加上第三个 non-template type（型别已确定的）函式参数， 使函式多载化机制能够有效运作。 设计考量是这样的：如果能够在 traits 内增加一个 iterator associated type， 使其得以独一无二地辨识出不同的 Iterator concept，我们便可以利用这个 类似 ID 的东西做为 advanced() 的第三个函式参数。这个类似 ID 的东西 绝不能只是个常数 ID，因为编译器要仰赖其型别来决定执行哪一个多载化函式。 那麽，最佳（也是唯一）的选择就是把它们设计为 classes（至於为什麽用到继承， 稍後再解释）： // 五个 tag types 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 { }; 然後将 advance() 重新设计如下： template <class InputIterator, class Distance> void advance(InputIterator& i, Distance n, input_iterator_tag) { for ( ; n > 0; --n, ++i ); // 单向，逐一前进 } // 一个单纯的转呼叫函式（trivial forwarding function） template <class ForwardIterator, class Distance> void advance(ForwardIterator& i, Distance n, forward_iterator_tag) { advance(i, n, input_iterator_tag()); // 单纯地转呼叫（forwarding） } template <class BidiectionalIterator, class Distance> void advance(BidiectionalIterator& i, Distance n, bidirectional_iterator_tag) { if (n >= 0) // 双向，逐一前进 for ( ; n > 0; --n, ++i ) { } else for ( ; n < 0; ++n, --i ) { } } template <class RandomAccessIterator, class Distance> void advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) { i += n; // 双向，跳跃前进 } 注意上述语法，每个 advance() 的最後一个函式参数都只宣告其型别，没有 指定参数名称 -- 因为函式中根本不会用到该参数。 最後我们还需写一个上层函式，呼叫上述的多载化 advance()。此一上层函式 只需两个参数，函式内自行加上第三个引数（五个 tag types 之一）後， 呼叫上述的 advance()。因此，上层函式必须有能力从它所获得的 iterator 中 推导（取出）其 tag type： template <class Iterator, class Distance> inline void advance(Iterator& i, Distance n) { advance(i, n, iterator_traits<Iterator>::iterator_category()); } 注意上述语法。iterator_traits<Iterator>::iterator_category() 产生 一个暂时性物件，那当然会是前述五个 tag types 之一。根据这个暂时物件 的确实型别，编译器决定呼叫哪一个多载化的 advance() 函式。为了满足 上述行为，我们的 traits 必须再增加一个 associated type： template <class 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; }; // partial specialization for regular pointers template <class T> struct iterator_traits<T*> { typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; }; // partial specialization for regular const pointers template <class T> struct typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef ptrdiff_t difference_type; typedef const T* pointer; typedef const T& reference; }; 所谓 iterator category，是指与「该 iterator 隶属之 concepts 中，最明确者」 所对应之 tag type。例如 int* 既是 Random Access Iterator 又是 Bidirectional Iterator, 同时也是 Forward Iterator, 也是 Input Iterator， 但其 category 是 random_access_iterator_tag。这便是为什麽上述 traits 针对指标所做的 partial specialization 中要使用 random_access_iterator_tag 之故。 以 class 来定义 tag types，不唯可以促成多载化机制的运作，它带来的 另一个好处是，透过继承，我们可以去除纯粹的转呼叫函式 （trivial forwarding function，前述的 advance() ForwardIterator 版）。 是的，请考虑下面这样的物件导向设计。至於它和 tag types 的关系， 就留给你好好思索。 // 模拟测试 tag types 继承关系所带来的影响。 #include <iostream> using namespace std; struct B { }; struct D1 : public B { }; struct D2 : public D1 { }; template <class I> func(I& p, B) { cout << "B version" << endl; } template <class I> func(I& p, D2) { cout << "D2 version" << endl; } int main() { int* p; func(p, B()); // exact match. output: "B version" func(p, D1()); // output: "B version" func(p, D2()); // exact match. output: "D2 version" } ●一个完整的范例 以下程式把上述的 iterator_traits 整合起来，并加入几个足以示范如何运用 各种 iterator associated types 的 algorithms。注意，这个技术正是 STL 所使用的技术，所以程式内千万不能打开 namespace std，否则会和 STL 内的 traits 相冲突。你可以在 C++Builder4 和 GNU C++ 所附的 STL 原始码中，看到大同小异的写法。VC6 目前尚未支援 partial specialization， 所以其所附之 STL 对此的作法稍有不同。 ref \austern\prog\??.cpp ●STL container 所提供的 iterators STL iterators 分为五大类。每一个 STL containers 都定义有一个 iterator 型别和一个 const_iterator 型别。以下是其宣告型式示范： vector<int>::iterator viter; vector<int>::const_iterator cviter; list<int>::iterator liter; list<int>::const_iterator cliter; deque<int>::iterator diter; deque<int>::const_iterator cditer; map<string, int>::iterator miter; map<string, int>::const_iterator cmiter; set<int>::iterator siter; set<int>::const_iterator csiter; 这些 iterators 隶属哪一种 iterator concepts 呢？[Austern99] 和 [Josuttis99] 有明确的说明。当我们要使用某个 algorithms 时（所有 STL algorithms 的最前面 两个参数都是 iterators，标记出一个范围），只需切记，你的 container iterators 的层级必须「优於」algorithms 所需层级。例如 remove() 需要 ForwardIterator， 而 vector 和 deque 提供的是 RandomAccessIterator， list 提供的是 BidirectionalIterator， set 和 map 提供的 iterators 是 ForwardIterator， 所以它们都可以和 remove() 搭配。 ●分析 STL istream_iterator 并订制一个 line_iterator STL 提供有所谓的 stream iterator：istream_iterator 用於输入， ostream_iterator 用於输出。让我们好好分析 istream_iterator 的实作技巧， 以便为自己订制 iterator 铺路。 以下是 SGI STL 的 istream_iterator 实作内容： see stl-2-3.cpp. 我们要订制一个 iterator 时，istream_iterator 的作法可以提供一个 有效的参考。假设现在我要设计一个 myistream_line_iterator， 它读取资料的方式不像 istream_iterator 那般以 token（语汇单元）为单位， 而是以一行文字为单位。也因此，它的 value type 固定为 string， 而不再是个 template 参数。下面是 myistream_line_iterator 的实作码 与测试范例： see stl-2-4.cpp. 这一期我们历经了份量很重的技术洗礼。彻底了解了所谓的 traits 技术。 这项技术无所不在地存在於 STL 的各个角落。下一期我们可以喘口气， 看看 containers 的应用 -- 那将是很令人愉快的程式经验。 ●参考资料： 1. [Austern99] "Generic Programming and the STL" by Matthew H. Austern, AW, 1999 2. [Josuttis99] "The C++ Standard Library" by Nicolai M. Josuttis, AW, 1999 3. [Hughes99] "Mastering the Standard C++ Classes", Cameron Hughes and Tracey Hughes, Wiley, 1999 4. [Musser96] "STL Tutorial and Reference Guide" by David R. Musser, AW, 1996 ●作者简介： 侯捷，自由作家，专长 Windows 作业系统、SDK/MFC 程式设计、C/C++ 语言、 物件导向程式设计、泛型程式设计。目前在元智大学开授泛型程式设计课程， 并进行新书《泛型程式设计》之写作。 --- the end -- ※ Origin: 枫桥驿站<bbs.cs.nthu.edu.tw> ◆ Mail: [email protected]