CUJ:标准库:定义iterator和const iterator

时间:2021-12-16 15:49:00

The Standard Librarian: Defining Iterators and Const Iterators

Matt Austern

http://www.cuj.com/experts/1901/austern.htm?topic=experts

------------------------------------------------------------------------------------------------------------------------

    写一个iterator并不难,并且它是扩展C++标准运行库的一个自然方式。但如果你想做正确,还是一些应该知道的关键点的。

    标准C++运行库被设计得可扩展的:标准算法(如reverse()和partition())对预定义的容器(如vector和list)进行操作,并且它们也可以操作于用户自定义的提供了适当iterator的数据结构。对运行库的高效使用包括对它的扩充。

    现如今,iterator对绝大多数的C++程序员都不陌生了。Iterator抽象了指针的绝大部分基本特征:forward iterator指向序列中的某个对象,而且它能进行增量运算以指向序列中的下一个元素。(更强的iterator范畴,bidirectional iterator和random iterator提供了额外的遍历序列的方法。更弱的iterator范畴则对绝大多数的数据结构都是不合适的。)

    每iterator都有一个范畴类型category_type(对forward iterator来说则是std::forward_iterator_tag),一个value_type (它所指向的对象的类型),一个difference_type(表示序列中两个元素间距离的一个整数类型),以及一个pointer_type和reference_type(指向iterator的value_type的指针和引用)。这些类型都可通过std::iterator_traits来访问;当你定义自己的iterator类时,提供它们的最容易的方法是提供嵌套的typedefs: iterator_category,value_type,difference_type,pointer,和reference。

    所谓forward iterator就是任何满足C++标准§24.1.3中的需求的类型;标准的那个小节告诉了你要定义什么成员函数和重载哪些运算符。一旦你已经知道iterator需要掌握的信息(以使得它能指向一个元素和找到其下一个元素),定义一个forward iterator只不过是对这些成员函数进行填空。   

配对的Iterator

使问题变复杂的一个因素是通常定义一个iterator类是不够的。你可能需要定义两个iterator类,一个允许修改它所指向的对象(*i返回对象的引用),而另一个不允许(*i返回一个const的引用)。运行库预定义的容器类这么做了:举例来说,std::list类,有一个嵌套类型 iterator和另外一个不同的嵌套类型const_iterator;后者可以用来遍历const std::list。list<T>::iterator和list<T>::const_iterator的value_type都是T,但reference_type和pointer_type不同:对list<T>::iterator它们分别是T&和T*,而对list<T>::const_iterator它们是const T&和const T*。你能将一个list<T>::iterator转换到一个list<T>::const_iterator,但(由于const 的正确性的明显理由)不能反过来。

    配对的iterator在用户自定义类型中如同在标准运行库预定义类型中一样常见。举例来说,假设你正在定义一个简单的单向链表类。你可能这样开始:   

template <class T>

struct slist_node {

  T val;

  slist_node* next;

  slist_node

     (const T& t, slist_node* p)

     : val(t), next(p) { }

};

template <class T> struct slist {

  slist_node<T>* head;

      ...

};

    供slist用的iterator类同样简单:

template <class T>

struct slist_iterator {

  typedef std::forward_iterator_tag

     iterator_category;

  typedef T value_type;

  typedef std::ptrdiff_t

     difference_type;

  typedef T& reference;

  typedef T* pointer;

      slist_iterator(slist_node<T>* x=0)

     : p(x) { }

  slist_iterator

    (const slist_iterator& i)

    : p(i.p) { }

  reference operator*() const

  { return p->val; }

  pointer operator->() const

  { return &(p->val); }

  slist_iterator& operator++() {

    p = p->next;

    return *this;

  }

  slist_iterator operator++(int) {

    slist_iterator tmp(*this);

    ++*this;

    return tmp;

  }

      slist_node<T>* p;

};

    我们该如何定义相应的const iterator?我们可以定义一个独立的 slist_const_iterator类,但代码重复造成浪费和易于出错。将slist_iterator变成slist_const_iterator时,变化是极小的:

l         申明p的类型为const slist_node<T>*而不是slist_node<T>*。

l         申明pointer和reference为const T*和const T&。

l         定义一个转换构造函数,它接受一个slist_iterator类型的参数。

    这并不妨碍定义单个类来同时取代slist_iterator和slist_const_iterator。我们将iterator定义为接受一些额外模板参数,这些参数决定它是否为一个const iterator。我们给这个类一个带非const版本的参数的构造函数;一种情况下它将成为一个拷贝构造函数,而另一种情况下它将成为一个转换构造函数。另外二个差异只涉及用一个类型代替另外一个,因此很容易将它们封装入模板参数。

    最后:那些额外的模板参数应该看起来象什么?在我的书中[注1],我建议pointer和reference类型作为模板参数显式传入。那个方法是可以的,但是它造成了多少有些笨重的类型名称;有一个整洁的解决方案。我们可以只提供一个额外模板参数,一个布尔标志,以决定我们是否正在定义const iterator,然后使用一点小技巧:“编译期的? : 操作”以根据此标志选择一个类型或另一个。这展示于Listing 1。

等于比较

我们还没有定义一个相等操作。这中间还隐藏着一个问题,而你甚至能在一些标准运行库预定义的iterator中发现它。试着编译这一个程序:

#include <deque>

int main() {

   std::deque<int> d;

   std::deque<int>::const_iterator i = d.begin();

   while (d.end() != i)

      ++d;

}

    程序没有做任何事,但问题不在于这一点。重要的是,对很多现存的运行库的实作,它甚至不能编译。那些实作有bug吗?不一定;i的类型是deque<int>::const_iterator,而d.begin()返回一个deque<int>::iterator,C++标准没有明确这两者之间的等于比较是否保证能工作[注3]。然而,即使标准没有明确要求这一点,如果你在你自己的iterator类中支持它的话,当然会更友好。

    你可能想知道这怎么会成为问题。毕竟,我们不是已经说了容器的 iterator类型总能被转换到它的const iterator类型吗?如果d.begin()能转换成deque<>::const_iterator,那么为什么不能比较他们?

    问题是有许多的不同方法来定义iterator的相等操作;如果它们是按两种最显而易见的方法来定义的,容器的iterator和const iterator类型之间的比较将不能工作。

    首先,假设operator==()被定义为成员函数。这不足够好。如果i是 deque<>::const_iterator,而j是deque<>::iterator,那么i == j可以工作而j == i不能。很容易明白不对称的原因:成员函数天生就是不对称的。a.f(b)这样的表达式(或,对本例,j.operator==(i))调用特定类的成员函数;转换只发生在函数的参数上。

    再明白不过了,于是,你的下个想法可能是定义operator==()为非成员函数。很不幸,这样作更糟!一个简单的程序举例说明了问题: 

template <class T> struct A { };

template <class T> struct B {

   B() { }

   B(A<T>) { }

};

 

template <class T>

void f(B<T>, B<T>) { }

    int main() {

   A<int> a;

   B<int> b(a); // OK, A is

                // convertible to B

   f(a, b);     // Doesn’t work

}

    A能转换到B还不足够。如果f不是模板,不会有问题:编译器会应用用户自定义的A<int>到B<int>的转换。然而,因为f依赖于模板参数T,另一个步骤将先执行:编译器必须推导出一个T类型以使得函数的调用匹配于f的实参表。对本例,无法匹配:f的申明说它的实参应该是相同类型的,但我们试图用两个不同的类型来调用它。模板参数推导需要完全匹配[注4];用户自定义的转换操作不会被考虑。

    我们不能申明operator==()为成员函数,也不能是非成员模板函数。看起来我们需要申明一系列的非模板函数,对应于每个可能的iterator类实例。这是一个奇怪的需求,因为一系列参数化的函数正是模板的功能,但最奇怪的是它实际上是可能的。

    它之所以可能,是因为类模板中友元申明上的一个含糊的漏洞[注5](WQ注,参看Herb Sutter的文章《Sutter's Mill: Befriending Templates》,CSDN上亦有我译的中文版)。你能显式申明友元函数是一个模板(的实例)。然而,如果你没有,并且如果它不匹配于已经被申明的函数模板,那么编译器将假设它是一个普通的非模板函数。举例来说:

template <class T> void g(T);

 

template <class T> struct X {

   // f is a function template

   friend void f<T>(T);

       // g is a function template

   friend void ::g(T); 

       // h is a non-template function

   friend void h(T);   

};

    通常这只会造成麻烦:正常情况下你期望编译期将h这样的东西认为是函数模板的申明,于是你不得不记住将它按编译器认为的方式申明。然而,有时候,这个怪异之事还真的有用。如果在友元声明时同时定义这个函数,并且申明它为一个非模板友元,你将会得到一系列的非模板函数--正是我们在iterator的相等操作上所需要的。 

template <class T> struct X {

   friend void f(T) { } // f is a non-template function

};

    slist_iterator的完全的定义,包括相等比较,见于Listing 2。

总结

    当你写一个容器或象容器的东西时,通常定义一个iterator类是不够的。你需要定义配对的iterator和const iterator类。定义这样的配对类会带来一些实现上的问题,这些问题是在只定义单个iterator类时是没有的。

    iterator/const iterator这两个类必须具有相同的iterator category,defference type和value_type;iterator类必须能转换到const iterator类,但不能反过来。你将iterator和const iterator定义为一个类,通过增加额外的模板参数并使用choose模板(或类似的东西)来定义适当的嵌套类型。如果你正在使用预定义的容器类(string,vector,list,deque,set,map,mulitset,multimap),应该避免对它的一个iterator和一个const iterator进行比较。如果d是deque(反过来就是const deque&),你不应该写:

std::deque<int>::const_iterator i = d.begin();

while (i != d.end())

   ...

    你应该写:

std::deque<int>::iterator i = d.begin();

while (i != d.end())

   ...

       C++标准没有明确说第一种形式应该能工作,并且,的确,它不能在所有实作上都工作。如果避免它,你的程序将更可移植。当你正在定义你自己的配对的iteratorconst iterator类时,你能容易地确保两者间的比较将正确工作;只要确保定义比较操作为非模板的友元函数。

Listing 1: An Slist_iterator class, complete except for the equality operator

template <bool flag, class IsTrue, class IsFalse>

struct choose;

 

template <class IsTrue, class IsFalse>

struct choose<true, IsTrue, IsFalse> {

   typedef IsTrue type;

};

 

template <class IsTrue, class IsFalse>

struct choose<false, IsTrue, IsFalse> {

   typedef IsFalse type;

};

 

template <class T, bool isconst = false>

struct slist_iterator {

   typedef std::forward_iterator_tag iterator_category;

   typedef T value_type;

   typedef std::ptrdiff_t difference_type;

   typedef typename choose<isconst, const T&, T&>::type

           reference;

   typedef typename choose<isconst, const T*, T*>::type

           pointer;

 

   typedef typename choose<isconst, const slist_node<T>*,   

                           slist_node<T>*>::type

           nodeptr;

 

  slist_iterator(nodeptr x = 0) : p(x) { }

  slist_iterator(const slist_iterator<T, false>& i)

     : p(i.p) { }

  reference operator*() const { return p->val; }

  pointer operator->() const { return &(p->val); }

  slist_iterator& operator++() {

     p = p->next;

     return *this;

  }

  slist_iterator operator++(int) {

     slist_iterator tmp(*this);

     ++*this;

     return tmp;

  }

 

   nodeptr p;

};

 

End of Listing

Listing 2: A complete implementation of Slist_iterator and a partial implementation of an Slist container

template <class T> struct slist_node {

   T val;

   slist_node* next;

   slist_node(const T& t, slist_node* p)

      : val(t), next(p) { }

};

 

template <bool flag, class IsTrue, class IsFalse>

struct choose;

 

template <class IsTrue, class IsFalse>

struct choose<true, IsTrue, IsFalse> {

   typedef IsTrue type;

};

 

template <class IsTrue, class IsFalse>

struct choose<false, IsTrue, IsFalse> {

   typedef IsFalse type;

};

 

template <class T, bool isconst = false>

struct slist_iterator {

   typedef std::forward_iterator_tag iterator_category;

   typedef T value_type;

   typedef std::ptrdiff_t difference_type;

   typedef typename choose<isconst, const T&, T&>::type

           reference;

   typedef typename choose<isconst, const T*, T*>::type

           pointer;

 

   typedef typename choose<isconst, const slist_node<T>*,   

                           slist_node<T>*>::type

           nodeptr;

 

   slist_iterator(nodeptr x = 0) : p(x) { }

   slist_iterator(const slist_iterator<T, false>& i)

      : p(i.p) { }

   reference operator*() const { return p->val; }

   pointer operator->() const { return &(p->val); }

   slist_iterator& operator++() {

      p = p->next;

      return *this;

   }

   slist_iterator operator++(int) {

      slist_iterator tmp(*this);

      ++*this;

      return tmp;

   }

 

   friend bool operator==(const slist_iterator& x,

                          const slist_iterator& y) {

      return x.p == y.p;

   }

 

   friend bool operator!=(const slist_iterator& x,

                          const slist_iterator& y) {

      return x.p != y.p;

   }

 

   nodeptr p;

};

 

// This is not a complete container class.  It is just

// enough to illustrate defining and using an iterator/

// const iterator pair.

template <class T> struct slist {

   slist_node<T>* head;

 

   typedef slist_iterator<T>       iterator;

   typedef slist_iterator<T, true> const_iterator;

 

   iterator begin() { return iterator(head); }

   iterator end()   { return iterator(0); }

   const_iterator begin() const {

      return const_iterator(head);

   }

   const_iterator end() const {

      return const_iterator(0);

   }

 

   slist() : head(0) { }

   ~slist() {

       while (head) {

          slist_node<T>* next = head->next;

          delete head;

          head = next;

       }

   }

 

   void push_front(const T& t) {

      head = new slist_node<T>(t, head);

   }

 

   ...

};

End of Listing

 

Notes and References

[1] Matt Austern. Generic Programming and the STL (Addison-Wesley, 1998).

[2] Using partial specialization to define a compile-time ?: operator (as well as other compile-time Boolean operations) is a relatively old idea; using it as a clean solution to the iterator/const iterator problem is more recent. I learned of the latter idea from Jeremy Siek.

[3] This is an open issue under consideration by the C++ standardization committee. See http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.htm#179.

[4] The full rules for template argument deduction are described in §14.8.2.1 of the C++ Standard.

[5] See §14.5.3 of the C++ Standard.