65.9K
CodeProject 正在变化。 阅读更多。
Home

"迭代器特性" 入门

程序员思维
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.91/5 (35投票s)

2009年5月18日

CPOL

6分钟阅读

viewsIcon

72944

本文介绍如何使用迭代器特性来无缝地为任何类型的迭代器编写通用函数。

引言

如果按照字典的解释，特质（trait）意味着特征/属性。在 C++ 中也不例外，这里的迭代器特性（iterator traits）意味着 C++ 迭代器的特征/属性。在深入研究之前，我们首先需要理解 C++ 中迭代器的设计基础。

在 C++ STL（标准模板库）中，有 3 个事物是有意义且重要的：

  1. 容器：用于管理特定类型的对象集合。容器可以分为两类：序列容器（vector、deque、list）和关联容器（Set、Multiset、Map、Multimap）。
  2. 算法：用于处理集合中的元素。也就是说，算法从容器获取数据，以预定义的方式处理这些元素，并可能将结果推送到同一/不同容器中。
  3. 迭代器：用于遍历对象集合（也称为容器）的元素。

STL 的设计者选择了一种出色而简单的通用方法——“数据与操作的分离”。

  • 数据由 Container 类持有和管理。
  • 容器上的操作由可配置的算法定义和管理。

因此，如果 Container 类和算法是完全不同的实体，它们之间就必须有一个桥梁，对吧？它们之间必须有一个专用的通道，它们之间必须有一些粘合剂。是的，您说得对 <=====> 迭代器就是这些桥梁/通道/粘合剂。

有人可能会争辩说，STL 的容器/算法/迭代器概念与面向对象编程的基本思想相悖：STL 将数据与其上的操作（算法）分开 <---> 而不是将它们结合起来。这种设计的优点和灵活性在于，您可以几乎将任何类型的容器与任何类型的算法绑定（按算法类型，我的意思是——修改/非修改/变异/排序/数值等）。

背景

介绍完了，但为了编写特定于迭代器特性的代码，还需要复习/完善一点背景知识。正如大家所知，迭代器实际上有不同的类别（随机访问、双向等）。为不同的能力构建了不同的迭代器类别。

尽管如此，有时几乎有必要以无缝的方式（即——对用户/外部人员来说是独立于迭代器的）重载不同迭代器的能力/行为。您可以在这里停下来问……嘿，等等。您刚才说了什么？“您想以独立于迭代器的方式重载迭代器的行为？那到底是什么意思？”

是的，您没有读错——有时绝对有必要在通用平台上重载不同迭代器的行为，以便从外部看起来是无缝的。

好的，您需要一个例子吗？有成千上万个。我将举几个例子。

  1. difference_type count(Iterator iter1, Iterator iter2)
  2. difference_type count_if(Iterator iter1, Iterator iter2, UnaryPredicate op)

count 算法的作用是计算容器中具有特定值（第一种形式）和满足一元谓词（第二种形式）的元素的数量……自然会有一个问题，它们的返回类型是什么？第一反应可能是……嘿，废话……可以是 INT/SHORT。但不行，那不是泛型编程。我们很快就会找到答案。
这里的另一点是：您应该以这样的方式编写泛型算法（这里是 count/count_if），以便用户可以将其用于任何类型的容器（以及任何类型的迭代器）。所以您需要以这样的方式编写它们——泛型函数应该对任何类型的迭代器都表现得无缝。

另一个例子是 distance() 方法。此方法接受两个迭代器位置并返回它们之间的数值距离。此方法也适用于所有类型的容器，因此也适用于所有类型的迭代器。

还有更多……详情请参阅 STL 算法部分。

那么，现在来到了一个大问题。我们如何以无缝的方式编写泛型函数/算法？

非常感谢 STL 设计者：他们提供了我们所需的一切。这项工作中有一些东西有点棘手，但它们非常简单且有用。

首先：对于每个迭代器类别，C++ 库都提供了一个“迭代器标签”，可以用作迭代器的“标签”。这种结构如下：（您会在一个名为 stl_iterator_base_types.hpp 的文件中找到它，我使用的是 MinGw）。

//@{
  /**
   *  @defgroup iterator_tags Iterator Tags
   *  These are empty types, used to distinguish different iterators.  The
   *  distinction is not made by what they contain, but simply by what they
   *  are.  Different underlying algorithms can then be used based on the
   *  different operations supported by different iterator types.
  */
  ///  Marking input iterators.
  struct input_iterator_tag {};
  ///  Marking output iterators.
  struct output_iterator_tag {};
  /// Forward iterators support a superset of input iterator operations.
  struct forward_iterator_tag : public input_iterator_tag {};
  /// Bidirectional iterators support a superset of forward iterator
  /// operations.
  struct bidirectional_iterator_tag : public forward_iterator_tag {};
  /// Random-access iterators support a superset of bidirectional iterator
  /// operations.
  struct random_access_iterator_tag : public bidirectional_iterator_tag {};
  //@}

注意继承的使用。因此，例如，任何前向迭代器（forward iterator）都是一种输入迭代器（input iterator）。但是，请注意，前向迭代器的标签仅源自输入迭代器的标签，而不是输出迭代器（output iterator）的标签。因此，任何前向迭代器都不是输出迭代器。事实上，前向迭代器具有一些要求，使其不能成为输出迭代器。

如果您编写泛型代码，您可能不仅对迭代器类别感兴趣。例如，您可能需要迭代器引用的元素的类型。因此，C++ 标准库提供了一个特殊的模板结构来定义迭代器特性。该结构包含有关迭代器的所有相关信息。它被用作所有迭代器应具有的类型定义的通用接口（类别、元素类型等）。

    namespace std {
       template <class T>
       struct iterator_traits {
           typedef typename T::value_type            value_type;
           typedef typename T::difference_type       difference_type;
           typedef typename T::iterator_category     iterator_category;
           typedef typename T::pointer               pointer;
           typedef typename T::reference             reference; 
       };
   }

在此模板中，T 代表迭代器的类型。因此，您可以编写代码，对任意迭代器在其类别中、其元素类型等使用代码。例如，以下表达式产生迭代器类型 T 的值类型。

   typename std::iterator_traits<T>::value_type

此结构有两个优点：

  1. 它确保迭代器提供所有类型定义。
  2. 它可以（部分）特化以适应（集合）特殊迭代器。后者适用于普通指针，它们也可以用作迭代器。
   namespace std {
       template <class T>
       struct iterator_traits<T*> {
           typedef T                          value_type;
           typedef ptrdiff_t                  difference_type;
           typedef random_access_iterator_tag iterator_category;
           typedef T*                         pointer;
           typedef T&                         reference;
       };
   }

因此，对于任何类型的“指向 T 的指针”，它被定义为具有随机访问迭代器类别。对于常量指针（const T*）也存在相应的偏特化。

Using the Code

为迭代器编写泛型函数

使用迭代器特性，您可以编写泛型函数，这些函数可以根据迭代器类别推导出类型定义或使用不同的实现代码。

使用迭代器类别

要为不同的迭代器类别使用不同的实现，您必须遵循以下两个步骤：

  1. 让您的模板函数调用另一个函数，并将迭代器类别作为附加参数。例如：
    template <typename Itr>
inline void my_function(Itr begin, Itr end)
{
    my_function (beg, end,
        std::iterator_traits<Itr>::iterator_category());
}
  2. 为任何提供特殊实现（不派生自其他迭代器类别）的迭代器类别实现该其他函数。例如：
     //my_function() for bidirectional iterators
  template <typename BidectionalIterator>
  void my_function (BidectionalIterator begin, BidirectionalIterator end,
                    std::bidirectional_iterator_tag)
  {
        //Bidirectional Iterator specific code is here
  }

 //my_function() for random access iterators
  template <typename RandomIterator>
  void  my_function(RandomIterator begin, RandomIterator end,
                    std::random_access_iterator_tag)
  {
              
             // Random access Iterator specific code is here
  }

distance() 的实现

这是遵循上一节步骤的一个示例，即实现辅助 distance() 迭代器函数。此函数返回两个迭代器位置及其元素之间的距离。随机访问迭代器的实现仅使用 - 运算符（也称为一元减法）。对于所有其他迭代器类别，返回到达范围末尾所需的增量数。

请仔细阅读以下代码中的注释。

 //User always calls this method, general method for distance()

// User needs to satisfy the following 2 criteria: 
// For random access iterator, second iterator position must come 
// after first iterator position/
// For all other kind of iterator, second iterator must be reachable from first iterator
// Both of the iterator must refer to the same container, otherwise result is undefined
    template <typename Iterator>
    typename std::iterator_traits<Iterator>::difference_type
    distance (Iterator pos1, Iterator pos2)
    {
        return distance (pos1, pos2,
                         std::iterator_traits<Iterator>
                            ::iterator_category()); 
    }
 
    //Core implementation ..... distance() for random access iterators
    template <typename RandomAccessIterator>
    typename std::iterator_traits<RandomAccessIterator>::difference_type
    // Note the return type above, it solely depends on Iterators declared typedefs,
    // no so called INT/SHORT here
    distance (RandomAccessIterator first_position, RandomAccessIterator second_position,
               std::random_access_iterator_tag) 
    {
        return second_position - first_position; 
    }


    //distance() for input, forward, and bidirectional iterators
    // Keep in mind that here we are using only Input iterator tags, so
    // forward and bidirectional iterator will also be in this bucket, because we
    // used Inheritance while declare forward and bidirectional iterator tags.

    template <typename InputIterator>
    typename std::iterator_traits<lnputIterator>::difference_type
    // Note the return type here, truly generic
    distance (Inputlterator first_position, InputIterator second_position,
              std::input_iterator_tag) 
    {
        // note the type of the temp variable here, truly generic 
        typename std::iterator_traits<lnputIterator>::difference_type diff;
        for (diff=0; first_position != second_position; ++first_position, ++diff) {
             ;
        }
        return diff; 
    }

迭代器的差异类型用作返回类型。请注意，第二个版本使用了输入迭代器的标签，因此该实现也被前向迭代器和双向迭代器使用，因为它们的标签派生自 input_iterator_tag。

我们可以对 count/count_if 的返回类型推导出相同的逻辑。所以理想的泛型返回类型应该是：

template <typename iterator>
typename std::iterator_traits<iterator>::difference_type
count(iterator itr1, iterator itr2){
// Your logic
}

进一步实现

您可以通过仅调整这种风格来编写大量泛型函数。当您最终得到一个应该对任何类型的迭代器都无缝工作的泛型函数时，这种风格确实是必要的。

参考文献 

  • C++ 编程语言 - 作者：Stroustrup
  • C++ 标准库：教程与参考 - 作者：Josutis

历史

  • 2009 年 5 月 18 日：首次发布
© . All rights reserved.