首页 > 编程笔记 > C++笔记

C++自定义迭代器（STL自定义迭代器)的实现详解

迭代器对于任何自定义的类序列都是一个强大的附加工具。它允许我们将算法运用到有自定义类元素的容器上。可能会出现一种情形，没有可以满足我们需要的标准 STL 容器，这时候就需要定义一个自己的容器。我们的容器类可能需要迭代器。通过深入理解什么样的类(定义了迭代器)才能被 STL 所接受，可以让我们了解到 STL 内部发生了些什么。

STL迭代器的要求

STL 对定义了迭代器的类类型有一些特定的要求。这是为了保证所有接受这种迭代器的算法都可以正常工作。算法不需要知道，也不在乎它所处理的元素来自何种容器，但是它们在意传给它们作为参数的迭代器的特性。不同的算法要求不同功能的迭代器。我们在前面章节看到过这几类迭代器：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。我们总是可以在需要低级别迭代器的地方使用高级别迭代器。

定义算法的模板需要决定可传入迭代器的类别，用来验证所传入的迭代器的功能是否足够。知道迭代器参数的类别能为算法的应用提供潜在的优势，可以充分利用任何最少的额外功能让算法更加高效。

一般来说，必须用标准的方式确认迭代器的功能。不同类别的迭代器意味着需要为迭代器类定义不同的成员函数集。我们知道，迭代器类别具有功能叠加性，这当然也会反映到每种类别的成员函数集上。在探讨这些之前，先介绍一下函数模板如何使用迭代器。

使用 STL 迭代器存在的问题

定义一个参数中有迭代器的函数模板会产生一个问题，我们并不总是知道在函数模板中要用到哪些类型的迭代器。思考下面用迭代器作为参数的交换函数；模板类型参数指定了迭代器类型：
template <typename Iter> void my_swap(Iter a, Iter b)
{
    tmp = *a;//error -- variable tmp undeclared
    *a = *b;
    *b = tmp;
}
函数模板的实例用来交换迭代器参数所指向的两个对象：a 和 b。dmp 应该是什么类型我们没法知道，我们知道迭代器指向对象的类型却无计可施，因为直到类模板生成实例时，才能确定对象的类型。在不知道对象的类型时，如何定义变量？当然，这里可以使用 auto。在一些情况下，我们也想知道迭代器类型的值和类型差别。

有些其他的机制可以确定一个迭代器参数所指向值的类型。一种是，坚持要求每个使用 my_swap() 的迭代器都应该包含一个公共定义的类型别名，因为这样就可以确定迭代器所指向对象的类型。既然这样，就可以在迭代器类中使用 value_type 的别名来指定函数模板 my_swap() 中 tmp 的类型，如下所示：
template <typename Iter> void my_swap(Iter a, Iter b)
{
    typename Iter::value—type tmp = *a;
    *a = *b;
    *b = tmp;
}
因为 value_type 的别名定义在 Iter 类中，所以可以通过用类名限定 value_type 的方式引用它。这样定义了 value_type 别名的迭代器类就能在函数中正常使用。然而，算法既使用指针，也使用迭代器；如果 Iter 是普通类型的指针，例如 int*，甚至是 Box*，而 Box 是类型一这样可能就无法使用了。因为指针不是类，不能包含定义的别名，所以不能写成 int*::value_type 或 Box*::value_type。STL 用模板优雅地解决了这个问题和其他一些相关问题！

走进 STL

模板类型 iterator_traits 定义在头文件 iterator 中。这个模板为迭代器的类型特性定义了一套标准的类型别名，让算法既可以用迭代器，也可以用一般的指针。iterator_traits 模板的定义如下所示：
template<class Iterator>
struct iterator_traits
{
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
    typedef typename Iterator::iterator_category iterator_category;
}；

相信你肯定记得，结构体和类在本质上是相同的，除了结构体的成员默认是 public，这个结构体模板中没有成员变量和成员函数。iterator_traits 模板的主体只包含类型别名的定义。这些别名以 Iterator 作为类型参数的模板。它在模板的类型别名——difference_type、value_type 等，以及用来生成迭代器模板实例的类型，与对应 Iterator 的类型参数之间定义了映射。

因此，对于一个实体类 Boggle，iterator_traits<Boggle> 实例定义 difference_type 作为 Boggle::difference_type 的别名，定义 value_type 作为 Boggle::value_type 的别名，等等。

这帮我们有效地解决了不知道模板定义中类型是什么的问题。首先，假设定义了一个迭代器类型 MyItemtor，它包含具有下列类型别名的定义：
一个满足 STL 要求的迭代器类必须全部定义这些别名。但是对于输出迭代器，除了 iterator_category，所有的别名都可以定义为 void。这是因为输出迭代器指向对象的目的地址而不是对象。这套迭代器提供了我们所想知道的关于迭代器的一切。

当以迭代器为参数定义函数模板时，可以在模板中使用 iterator_traits 模板定义的标准类型别名。因此类型 MyIterator 的迭代器代表的指针类型总是可以作为 std::iterator_traits<MyIterator>:: pointer 引用，因为它等同于 MyIterator::pointer。当需要指定一个 MyIterator 迭代器所指向值的类型时，可以写作 std::iterator_traits<MyIterator>::value_type，这将会被映射为 Mylterator::value_ type。我们用 my_swap() 模板中的 iterator_traits 模板类型别名来指定 tmp 的类型，例如：
template <typename Iter>
void my_swap(Iter a, Iter b)
{
    typename std::iterator_traits<Iter>::value_type tmp = *a;
    *a = *b;
    *b = tmp;
}
上述代码将 tmp 的类型指定为 iterator_traits 模板中的 value_type 别名。当用 Iter 模板参数实例化 my_swap() 模板时，tmp 的类型变为迭代器所指向的类型 Iter::value_type。

为了说清楚发生了什么，以及是如何解决这个问题的，让我们考虑一个 my_swap() 模板实例的具体情况。假设一个程序包含下面的代码：
std::vector<std::string> words {"one", "two", "three"};
my_swap(std::begin(words), std::begin(words)+1); //Swap first two elements
当编译器遇到 my_swap() 调用时，它会生成一个基于调用参数的函数模板实例。模板类型的迭代器是 iterator<std::string>。在 my_swap() 模板的主体中，编译器不得不处理 tmp 的定义，编译器知道模板的类型参数是 iterator<std::string>，因此在向模板添加了这个类型后，tmp 的定义变为：
typename std::iterator_traits<iterator<std::string> >::value_type tmp = *a;
tmp 的类型现在是一个 iterator_traits 模板实例的成员变量。为了弄清楚这意味着什么，编译器需要使用 my_swap() 函数中用来指定 tmp 类型的类型参数来实例化 iterator_traits 模板。下面是一个编译器将会生成的 iterator_traits 模板实例：
struct iterator—traits
{
    typedef typename iterator<std::string>::difference_type difference_type;
    typedef typename iterator<std::string>::value_type value_type;
    typedef typename iterator<std::string>::pointer pointer;
    typedef typename iterator<std::string>::reference reference;
    typedef typename iterator<std:: string>:: iterator_category iterator_category;
}；
从这里编译器可以确定 tmp 的类型为 iterator_traits<iterator<std::string>>::value_type，然而它也是 iterator<std::string>::value_type 的别名。就像所有的 STL 迭代器类型，iterator<std::string> 类型的定义是从 iterator 模板中生成的，并且会包含 value_type 的定义， 看起来像下面这样：
typedef std::string value_type;
现在编译器从 iterator_traits 实例中知道 itemtor_traits<itemtor<std::string>>::value_type 是 iterator<std::string>::value_type 的别名，并且从 itemtor<std::string> 类定义中知道 iterator<std::string>:: value_type 是 std::string 的别名。通过将别名转换为真实类型，编译器推断出 my_swap() 函数中 tmp 的定义是：
std::string tmp = *a;
有必要提醒自己模板不是代码一它是编译器用来生成代码的配方。iterator_traits 模板只包含类型别名，因此不会产生可执行代码。编译器在生成 C++ 代码的过程中，会用到它。被编译的代码中将不会有 iterator_traits 模板的踪迹；它的唯一用武之地是在生成 C++ 代码的过程中。

这里仍然遗留了一些有关指针的问题。iterator_traits 如何让算法像接受迭代器一样接受指针。iterator_traits 模板特化了类型 T* 和 const T* 的定义。例如，当模板类型参数是指针类型 T* 时，特化被定义为：
template<class T>
struct iterator_traits<T*>
{
    typedef ptrdiff_t   difference_type;
    typedef T   value_type;
    typedef T*  pointer;
    typedef T&  reference;
    typedef random_access_iterator_tag iterator_category;
}；
当模板类型参数是指针类型时，这定义了对应于别名的类型。T* 类型的指针 value_type 的别名总是为 T；如果将 Box* 类型的指针作为 my_swap() 的参数，那么 value_type 的别名是 Box，因此 tmp 也为这种类型。

随机访问迭代器类别所要求的全部操作都可以运用到指针上。因此对于指针，iterator_categor 的别名总是等同于 std::random_access_iterator_tag 类型。因而 iterators_traits 能否正常工作取决于模板类型参数是指针还是迭代器类类型。当模板类型参数是指针时，会选择使用 iterators_traits 针对指针的特例化模板；否则选择标准的模板定义。

使用迭代器模板

STL 定义了迭代器模板，用来帮助我们在自己的迭代器类中包含要求的类型别名。 iterator 是一个结构体模板，它定义了 5 个来自于 iterator_traits 模板的类型别名：
template<class Category, class T, class Difference = ptrdiff_t, class Pointer =T*,class Reference = T&> struct iterator
{
    typedef T value_type;
    typedef Difference difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
    typedef Category iterator_category
}；
这个模板定义了 STL 对迭代器所要求的全部类型。例如，如果有一个未知类型的模板参数 Iter，当需要声明一个指针时，它指向一个迭代器解引用时提供的类型，这时可以写作 Iter::pointer。 iterator_category 的值必定是在前面章节介绍的类别标签类中的一个。

当定义一个表示迭代器的类时，可以使用以迭代器模板为基类生成的实例，这样会添加类需要的类型别名。例如： 
class My_Iterator : public std::iterator<std::random_access_iterator_tag,int>
{
    // Members of the iterator class...
}；
还需要注意，需要为迭代器定义 STL 要求的全部类型。模板的第 1 个参数指定了作为完全随机访问迭代器的迭代器类型。第 2 个参数是迭代器所指向对象的类型。最后的 3 个参数是默认值，因此第 3 个参数和这两个迭代器的类型不同，是 ptrdiff_t。第 4 个参数是一个指向对象的指针类型，因此是 int*。最后一个模板参数指定了引用的类型，是 int&。当然，迭代器类型不做任何事，仍然需要定义类的全部成员。

STL迭代器成员函数的要求

STL 定义了一套需要迭代器类型支持并且依赖迭代器类别的成员函数。如果把它们编成组，显然很有用。第一组需要全部迭代器和一些所有迭代器类都需要的重要函数：默认构造函数、拷贝构造函数以及赋值运算符。根据经验，如果为迭代器类定义了其中任意一个函数，就需要定义一个显式的析构函数。该组中类型迭代器的全套函数是：
Iterator(); // Default constructor
Iterator (const Iterator& y) ; // Copy constructor
~Iterator (); // Destructor
Iterator& operator= (const Iterator& y) ;// Assignment operator
对于随机访问迭代器类，STL 需要一整套的关系运算符。事实上，可以通过使用 utility 标准库头文件中的函数模板来完成这些定义：
bool operator==(const Iterator& y) const;
bool operator<(const Iterator& y) const;
下面假定已经直接 #include 头文件 utility，并且直接使用命名空间 std::relops：
#include <utility>
using namespace std::rel_ops;
如果为类定义了 operator=() 和 operator<()，然后 std 中声明的命名空间 rel_ops 在必要时，就可以包含我们为 !=、>、>= 和 <= 生成的运算符函数的函数模板。因此直接用 using 激活 std::rel_ops，就可以显式保存这 4 个运算符函数。如果定义一个运算符函数，但是它已经被命名空间 std::rd_ops 模板生成，那么我们的实现的优先级高于模板生成的实现。函数 operator() 比较特别，叫作顺序关系，它对搜索和比较算法很重要。

函数 operator==() 可以检验两个容器对象的内容是否相同。这是一个有趣的方面，对于任意一对操作数 x 和 y，表达式 (x<y || y<x || x==y) 总为真，因为这个表达式的三部分中总有一部分为真。

事实上，不需要那样做，如果 x==y 为真，那么 x<y 和 y<x 都不可能为真。唯一可以确定的是两个相等元素没有什么不同。然而，如果 x!=y，就无法断定中的哪个为真。当表达式 (!(x<y)) &&(!(y<x)) 为真时，就可以说 x 和 y 不相等，也就意味着在排序时没有偏向。这种情况的一个常见示例是对字符串进行排序时，但是要忽略大小写。如果以大小写敏感为基准，字符串 "A123" 和 "a123" 是不等价的(第一个字母不相同)，它们不相同，也不相等。

迭代器的其他操作由它的类别决定。可以在前面章节看到每种迭代器的特定操作，而且因为迭代器的累加特性，随机访问迭代器可以支持全部操作。

让我们在示例中看一个简单迭代器类型的定义。我们定义一个类模板，用来表示一段数值类型值，也可以生成指定范围的开始和结束迭代器。这个迭代器也是模板类型，两个模板都定义在同一个头文件 Numeric_Range.h 中。下面是 Numeric_Range<T> 模板的定义：
template <typename T> class Numeric_Iterator;    // Template type declaration
// Defines a numeric range
template<typename T>
class Numeric_Range
{
    static_assert(std::is_integral<T>::value || std::is_floating_point<T>::value,
                                 "Numeric_Range type argument must be numeric.");
    friend class Numeric_Iterator < T >;
protected:
    T start;                                       // First value in the range
    T step;                                        // Increment between successive values
    size_t count;                                  // Number of values in the range
public:
    Numeric_Range(T first=0, T incr=1, size_t n=2) : start {first}, step {incr}, count {n}{}
    // Return the begin iterator for the range
    Numeric_Iterator<T> begin(){ return Numeric_Iterator<T>(*this); }
    // Return the end iterator for the range
    Numeric_Iterator<T> end()
    {
        Numeric_Iterator<T> end_iter(*this);
        end_iter.value = start + count*step;          // End iterator value is one step over the last
        return end_iter;
    }
};
类型参数 T 是序列的值类型，因此它必定是数值类型。对于模板主体中的函数 static_assert()，当 T 不是整型也不是浮点型时，它的第一个参数会为 false，这时会生成一条包含第二个字符串参数的编译时错误消息。这里使用的断言模板定义在头文件 type_traits 中，模板中还有一些其他的编译时模板类型参数检查断言。这个构造函数的三个参数都有默认值，因此它也可以作为无参构造函数。这三个参数分别用来初始化值、指定一个值到另一个值的增量，以及指定值的个数。因此默认定义了又有两个值的元素段：0 和 1。编译器会在需要时，提供适当的拷贝构造函数。

另有两个成员函数生成，然后返回元素段的开始和结束迭代器。结束迭代器的成员变量 value 的值为最后一个 value+1。结束迭代器是通过修改开始迭代器的 value 生成的。Numeric_Itemtor<T>模板类型的声明在其定义之前是必要的，因为还没有定义迭代器类型模板。Numeric_Iterator<T> 模板被指定为这个模板的友元类，这样 Numeric_Iterator<T> 的实例就可以访问Numeric_Range<T> 的私有成员。Numeric_Range<T> 模板也需要成为 Numeric_Iterator<T> 的友元类，因为 Numeric_Range<T> 的成员函数 end() 需要访问 Numeric_Iterator<T> 的一个私有成员。

这个迭代器的模板类型定义如下： 
// Iterator class template- it's a forward iterator
template<typename T>
class Numeric_Iterator : public std::iterator < std::forward_iterator_tag, T >
{
    friend class Numeric_Range < T >;
protected:
    Numeric_Range<T>& range;                       // Reference to the range for this iterator
    T value;                                       // Value pointed to
public:
    explicit Numeric_Iterator(Numeric_Range<T>& a_range) : range {a_range}, value {a_range.start} {};

    // Assignment operator
    Numeric_Iterator& operator=(const Numeric_Iterator& src)
    {
        range = src.range;
        value = src.value;
    }

    // Dereference an iterator
    T& operator*()
    {
        // When the value is one step more than the last, it's an end iterator
        if (value == static_cast<T>(range.start + range.count*range.step))
        {
            throw std::logic_error("Cannot dereference an end iterator.");
        }
        return value;
    }

    // Prefix increment operator
    Numeric_Iterator& operator++()
    {
        // When the value is one step more than the last, it's an end iterator
        if (value == static_cast<T>(range.start + range.count*range.step))
        {
            throw std::logic_error("Cannot increment an end iterator.");
        }
        value += range.step;                         // Increment the value by the range step
        return *this;
    }

    // Postfix increment operator
    Numeric_Iterator operator++(int)
    {
        // When the value is one step more than the last, it's an end iterator
        if (value == static_cast<T>(range.start + range.count*range.step))
        {
            throw std::logic_error("Cannot increment an end iterator.");
        }
        auto temp = *this;
        value += range.step;                         // Increment the value by the range step
        return temp;                                 // The iterator before it's incremented
    }

    // Comparisons
    bool operator<(const Numeric_Iterator& iter) const { return value < iter.value; }
    bool operator==(const Numeric_Iterator& iter) const { return value == iter.value; }
    bool operator!=(const Numeric_Iterator& iter) const { return value != iter.value; }
    bool operator>(const Numeric_Iterator& iter) const { return value > iter.value; }
    bool operator<=(const Numeric_Iterator& iter) const { *this < iter || *this == iter; }
    bool operator>=(const Numeric_Iterator& iter) const { *this > iter || *this == iter; }
};
#endif
代码看起来虽多，却很简单直白。这个迭代器有一个成员变量，它保存了一个和它相关联的 Numeric_Range 对象的引用，另外还保存了它所指向元素的值。迭代器的构造函数的参数是一个 Numeric_Range 对象的引用。构造函数用参数初始化成员变量 range，并将成员变量 value 的值设为 Numeric_Range 的 start。

还定义了一些解引用运算符、前缀或后缀自增运算符以及一套比较运算符。对元素段的结束迭代器的解引用或自增都是非法的，因此如果操作数是结束迭代器，那么自增运算符函数和解引用运算符函数都会拋出异常；这表明成员变量 value 超出了元素段中的最后一个值。为了简单，选择拋出一个标准异常。

头文件 Numeric_Range.h 的完整内容如下： 
// Exercising the Numeric_Range template
#include <algorithm> // For copy()
#include <numeric> // For accumulate()
#include <iostream> // For standard streams
#include <vector> // For vector container
#include "Numeric_Range.h" // For Numeric_Range<T> & Numeric_Iterator<T>

int main()
{
    Numeric_Range<double> range {1.5, 0.5, 5};
    auto first = range.begin();
    auto last = range.end();
    std::copy(first, last, std::ostream_iterator<double>(std::cout, "  "));
    std::cout << "\nSum = " << std::accumulate(std::begin(range), std::end(range), 0.0) << std::endl;

    // Initializing a container from a Numeric_Range
    Numeric_Range<long> numbers {15L, 4L, 10};
    std::vector<long> data {std::begin(numbers), std::end(numbers)};
    std::cout << "\nValues in vector are:\n";
    std::copy(std::begin(data), std::end(data), std::ostream_iterator<long>(std::cout, "  "));
    std::cout << std::endl;

    // List the values in a range
    std::cout << "\nThe values in the numbers range are:\n";
    for (auto n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
}
运行结果为：
1.5 2 2.5 3 3.5
Sum = 12.5
Values in vector are:
15 19 23 27 31 35 39 43 47 51
The values in the numbers range are:
15 19 23 27 31 35 39 43 47 51

生成的第一个 Numeric_Range 实例有 5 个 double 型元素，它们从 1.5 开始，每次增加 0.5。Numeric_Range 的迭代器用来在 copy() 算法中将值复制到 ostream_iterator。这表明算法可以接受这个迭代器。第二个 Numeric_Range 实例有 10 个 long 型元素。在 vector 容器的初始化列表中，使用开始和结束迭代器，然后用 copy() 算法输出 vector 中的元素。最后，为了演示它的工作原理，以 for 循环的方式输出它的值。输出表明 Numeric_Range 模板成功创建了整型和浮点型的元素段，我们成功定义了一个可以使用 STL 的迭代器类型。

相关文章