深入 STL distance 函数

• 下载源代码 - 3.79 Kb

引言

本文的目的是演示模板编程的基本概念（例如：标签和特质类）。在本文中，我将实现“distance”STL 函数的一些功能。通过处理出现的各种问题，基本概念会变得更加清晰。

背景

迭代器是一种对象，它允许用户遍历另一个对象中包含的所有元素。

迭代器是泛型编程的核心，因为它们是容器和算法之间的接口：算法通常将迭代器作为参数，因此容器只需要提供一种方法来使用迭代器访问其元素。这使得编写一个可以操作多种不同类型容器的泛型算法成为可能（有关更多信息，请参阅STL 文档）。

给定同一容器上的两个迭代器，我们希望创建一个泛型函数来返回它们之间的元素数量，即它们之间的距离。如果不要求以最快的方式执行此操作，这听起来很简单。通过说“以最快的方式执行”，我的意思是，如果这是一个随机访问迭代器，它将在常数时间内完成，如果它只是一个前向迭代器，它将在线性时间内完成（有关更多信息，请参阅STL 文档）。

详细说明

如果没有泛型编程知识，基本实现应该看起来像这样

//
// The my_distance function returns
// the distance between two iterators in a container
//
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd)
{
    int dist = 0;
    if( isRandomAccessIterator(itBegin) )
    {
        return itEnd - itBegin;
    }
    else
    {
        while( itBegin!=itEnd ) { ++itBegin; ++dist; }
    }
}

此代码存在几个问题

1. 我们如何实现 isRandomAccessIterator？此函数检查它是一个随机访问迭代器还是一个前向访问迭代器。
2. 此示例将永远无法与前向迭代器编译。原因是我们将减法运算符用于随机访问迭代器，而前向迭代器没有此运算符（代码在不执行前向迭代器情况下不执行的事实无关紧要）。
3. 我们希望控制代码的运行（流控制）的决策，是减法还是 while 循环，将在编译时做出。这将使代码运行得更快，并且由于（2）我们没有真正的选择。

所有这些问题都有解决方案

标签

好吧，我们不会完全实现 isRandomAccessIterator 方法。主要原因是从定义上讲，函数在运行时返回值，而我们希望在编译时进行流控制。相反，我们将使用标签来标识迭代器的类别。

标签是空结构，用于在编译时标识类型和类型的属性。以下是前向访问和随机访问迭代器类别的标签定义（取自 STL），以及如何将 MyIterator 的类别定义为随机访问的示例

struct forward_iterator_tag 
       : public input_iterator_tag
{
// identifying tag for forward iterators
};

struct bidirectional_iterator_tag 
       : public forward_iterator_tag
{
// identifying tag for bidirectional iterators
};
 
struct random_access_iterator_tag 
       : public bidirectional_iterator_tag
{
// identifying tag for random-access iterators
};
 
class MyIterator
{
    typedef random_access_iterator_tag iterator_category;
}

random_access_iterator_tag 继承自 bidirectional_iterator_tag，因为随机访问迭代器也是双向迭代器。STL 中的每个迭代器在其类声明中都有一个 iterator_category 类型，如 MyIterator 中所示（这并非完全正确 - 继续阅读）。如何使用标签获取编译时流控制的答案在下一节中提供。

函数重载

如果标签是用于标识某些类型某些属性的“属性”，那么函数重载就是我们根据这些属性（标签）来控制流的工具。函数重载是我们编译时使用的 if/switch 语句。

// function for forward iterator.
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd, 
                forward_iterator_tag tag)
{
        cout << "Forward iterator" << endl;
        int dist=0;
        while( itBegin!=itEnd ) { ++itBegin; ++dist; }
 
        return dist;
}
 
// function for random access iterator.
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd, 
                random_access_iterator_tag tag)
{
        cout << "Random access iterator" << endl;
 
        return itEnd - itBegin;
}
 
// the general distance function
template <class Iterator>
int my_distance(Iterator itBegin, Iterator itEnd)
{
        typedef typename Iterator::iterator_category 
                                  iterator_category;
        return my_distance(itBegin, itEnd, 
                               iterator_category());
}

在 my_distance 函数上，我们只是实例化给定迭代器的 iterator_category（空结构），并将其传递给另一个函数（typename 关键字是必需的，这样编译器才能知道 iterator_category 是 typedef 中的一个类型）。由于每个迭代器都包含其正确的 iterator_category，编译器会选择正确的重载函数（接受 random_access_iterator_tag 的函数或接受 forward_iterator_tag 的函数）。在编译时，我们已成功根据 iterator_category 运行了代码！

上面的代码有一个大问题。如果您尝试将其与 vector<int>::iterator 一起使用，您将收到编译错误。原因是 vector<int>::iterator 实际上是 int*，而 int* 没有 iterator_category 类型，甚至不是类。此问题的解决方案是使用特质类。

特质类

特质类允许我们将标签（以及常量和其他属性）与非类类型以及不属于我们的类关联起来。对于 STL 迭代器，有一个名为 iterator_traits 的特质类。它的默认行为是从模板类中获取标签（和 const 字段）。

// default iterator traits
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;
};

// partial specialization for pointers
template<typename T>
struct iterator_traits<T *>
{
        typedef random_access_iterator_tag iterator_category;
        typedef T value_type;
        typedef ptrdiff_t difference_type;
};

我们使用偏特化为指针类型定义不同的标签。我们可以使用特化将标签关联到我们无法修改的类，因此无法为其添加标签（我们只需要为该特定类特化特质类）。

现在我们的代码看起来应该像这样

// the general distance function
int my_distance(Iterator itBegin, Iterator itEnd)
{
    typedef typename 
      iterator_traits<Iterator>::iterator_category 
      iterator_category;
    return my_distance(itBegin, itEnd, iterator_category());
}

结论

标签是非常强大的工具。它们可以与函数重载一起用于创建编译时流控制。

使用特质类可以使代码更易于使用和适应。