C++ 中的自定义迭代器

Custom Iterator in C++

提问by Sugar

I have a class TContainer that is an aggregate of several stl collections pointers to TItems class.

我有一个 TContainer 类，它是指向 TItems 类的几个 stl 集合指针的聚合。

I need to create an Iterator to traverse the elements in all the collections in my TContainer class abstracting the client of the inner workings.

我需要创建一个迭代器来遍历 TContainer 类中所有集合中的元素，抽象出内部工作的客户端。

What would be a good way to do this?. Should I crate a class that extends an iterator (if so, what iterator class should I extend), should I create an iterator class that is an aggregate of iterators?

这样做的好方法是什么？我应该创建一个扩展迭代器的类（如果是，我应该扩展哪个迭代器类），我应该创建一个迭代器聚合的迭代器类吗？

I only need a FORWARD_ONLY iterator.

我只需要一个 FORWARD_ONLY 迭代器。

I.E, If this is my container:

IE，如果这是我的容器：

typedef std::vector <TItem*> ItemVector;
class TContainer {
   std::vector <ItemVector *> m_Items;
};

What would be a good Iterator to traverse all the items contained in the vectors of the m_Items member variable.

什么是遍历 m_Items 成员变量的向量中包含的所有项目的好迭代器。

回答by Martin York

When I did my own iterator (a while ago now) I inherited from std::iterator and specified the type as the first template parameter. Hope that helps.

当我做我自己的迭代器时（不久前），我从 std::iterator 继承并将类型指定为第一个模板参数。希望有帮助。

For forward iterators user forward_iterator_tag rather than input_iterator_tag in the following code.

对于前向迭代器，在以下代码中使用 forward_iterator_tag 而不是 input_iterator_tag。

This class was originally taken from istream_iterator class (and modified for my own use so it may not resemble the istram_iterator any more).

这个类最初取自 istream_iterator 类（并修改为我自己使用，因此它可能不再类似于 istram_iterator）。

template<typename T>
class <PLOP>_iterator
         :public std::iterator<std::input_iterator_tag,       // type of iterator
                               T,ptrdiff_t,const T*,const T&> // Info about iterator
{
    public:
        const T& operator*() const;
        const T* operator->() const;
        <PLOP>__iterator& operator++();
        <PLOP>__iterator operator++(int);
        bool equal(<PLOP>__iterator const& rhs) const;
};

template<typename T>
inline bool operator==(<PLOP>__iterator<T> const& lhs,<PLOP>__iterator<T> const& rhs)
{
    return lhs.equal(rhs);
}

Check this documentation on iterator tags:
http://www.sgi.com/tech/stl/iterator_tags.html

检查有关迭代器标签的文档：http:
//www.sgi.com/tech/stl/iterator_tags.html

Having just re-read the information on iterators:
http://www.sgi.com/tech/stl/iterator_traits.html

刚刚重新阅读了有关迭代器的信息：http:
//www.sgi.com/tech/stl/iterator_traits.html

This is the old way of doing things (iterator_tags) the more modern approach is to set up iterator_traits<> for your iterator to make it fully compatible with the STL.

这是旧的做事方式（iterator_tags），更现代的方法是为您的迭代器设置 iterator_traits<> 以使其与 STL 完全兼容。

回答by James Hopkin

If you have access to Boost, using iterator_facadeis the most robust solution, and it's pretty simple to use.

如果您可以访问 Boost，则 usingiterator_facade是最强大的解决方案，而且使用起来非常简单。

回答by Manuel

First let's generalize a little bit:

首先让我们概括一下：

typedef int value_type;
typedef std::vector<value_type*> inner_range;
typedef std::vector<inner_range*> outer_range;

Now the iterator:

现在迭代器：

struct my_iterator : std::iterator_traits<inner_range::iterator> 
{
    typedef std::forward_iterator_tag iterator_category;

    my_iterator(outer_range::iterator const & outer_iterator, 
                outer_range::iterator const & outer_end)
    : outer_iterator(outer_iterator), outer_end(outer_end)
    { 
        update();
    }

    my_iterator & operator++()
    {
        ++inner_iterator;
        if(inner_iterator == inner_end)
        {
            ++outer_iterator;
            update();
        }
        return *this;
    }

    reference operator*() const
    {   
        return *inner_iterator;
    }

    bool operator==(my_iterator const & rhs) const
    {   
        bool lhs_end = outer_iterator == outer_end;
        bool rhs_end = rhs.outer_iterator == rhs.outer_end;
        if(lhs_end && rhs_end)
            return true;
        if(lhs_end != rhs_end)
            return false;
        return outer_iterator == rhs.outer_iterator 
            && inner_iterator == rhs.inner_iterator;
    }

private:

    outer_range::iterator outer_iterator, outer_end;
    inner_range::iterator inner_iterator, inner_end;

    void update()
    {
        while(outer_iterator != outer_end)
        {
            inner_iterator = (*outer_iterator)->begin();
            inner_end = (*outer_iterator)->end();
            if(inner_iterator == inner_end)
                ++outer_iterator;
            else
                break;
        }
    }    
};

This class assumes than the outer iterators contain pointers to the inner ranges, which was a requirement in your question. This is reflected in the updatemember, in the arrows before begin()and end(). You can replace these arrows with dots if you want to use this class in the more common situation where the outer iterator contains the inner ranges by value. Note BTW that this class is agnostic to the fact that the inner range contains pointers, only clients of the class will need to know that.

此类假设外部迭代器包含指向内部范围的指针，这是您的问题的要求。这反映在该update部件，在之前的箭头begin()和end()。如果您想在外部迭代器按值包含内部范围的更常见情况下使用此类，您可以用点替换这些箭头。请注意顺便说一句，该类与内部范围包含指针的事实无关，只有该类的客户端需要知道这一点。

The code could be shorter if we use boost::iterator_facadebut it's not necessary to add a boost dependency for something so simple. Besides, the only tricky parts are the equality and increment operations, and we have to code those anyway.

如果我们使用，代码可能会更短，boost::iterator_facade但没有必要为这么简单的事情添加 boost 依赖项。此外，唯一棘手的部分是等式和增量操作，无论如何我们都必须对它们进行编码。

I've left the following boiler-plate members as "exercises for the reader":

我将以下样板成员留作“读者练习”：

• postfix increment iterator
• operator!=
• default constructor
• operator->

• 后缀增量迭代器
• 运算符！=
• 默认构造函数
• 运算符->

Another interesting exercise is to turn this into a template which works with arbitrary containers. The code is basically the same except that you have to add typenameannotations in a few places.

另一个有趣的练习是将其转换为适用于任意容器的模板。代码基本相同，只是需要typename在几个地方添加注释。

Example of use:

使用示例：

int main()
{
    outer_type outer;
    int a = 0, b = 1, c = 2;
    inner_type inner1, inner2;
    inner1.push_back(&a);
    inner1.push_back(&b);
    inner2.push_back(&c);
    outer.push_back(&inner1);
    outer.push_back(&inner2);

    my_iterator it(outer.begin(), outer.end());
                e(outer.end(), outer.end());
    for(; it != e; ++it)
        std::cout << **it << "\n";
}

Which prints:

哪个打印：

0 1 2

0 1 2

回答by Manuel

An iterator is just a class that supports a certain interface. At minimum, you will want to be able to:

迭代器只是一个支持特定接口的类。至少，您将希望能够：

• increment and/or decrement it
• dereference it to get the object it "points" to
• test it for equality and inequality
• copy and assign it

• 增加和/或减少它
• 取消引用它以获取它“指向”的对象
• 测试它的平等和不平等
• 复制并分配它

Once you have a class that can do that sensibly for your collection, you will need to modify the collection to have functions that return iterators. At minimum you will want

一旦你有一个可以为你的集合明智地做这件事的类，你将需要修改集合以具有返回迭代器的函数。至少你会想要

• a begin() function that returns an instance of your new iterator type positioned at the first element
• an end() function that returns an iterator which is (possibly notionally) positioned at one past the end of the items in your container

• 一个 begin() 函数，它返回位于第一个元素的新迭代器类型的实例
• 一个 end() 函数返回一个迭代器，该迭代器（可能理论上）位于容器中项目末尾的后面

回答by Nitin Bhide

Check the Views Template Library.

检查视图模板库。

Especially check

特别检查

1. Union Viewpresenting two containers concatenated.
2. Concatenation Viewpresenting a collection of containers concatenated.

1. 联合视图呈现两个连接的容器。
2. 串联视图显示串联的容器集合。

回答by Jarekczek

This is the simplest code I was able to produce (for custom iterators). Note that I'm only beginning to explore this area. This calls built-in upper_boundfunction to perform binary search on an integer function, x^2as an example.

这是我能够生成的最简单的代码（用于自定义迭代器）。请注意，我才刚刚开始探索这个领域。例如，这将调用内置upper_bound函数对整数函数执行二分查找x^2。

#include <algorithm>
#include <iostream>

using namespace std;

class Iter
{
  public:
  int x;
  Iter() { x = -1; }
  Iter(int a) { x = a; }

  bool operator!=(Iter &i2) const { return x != i2.x; }
  void operator++() { x++; }
  void operator+=(int b) { x += b; }
  int operator-(const Iter &i2) const { return x - i2.x; }
  int operator*() const {
    cout << "calculating for x " << x << endl;
    return x*x;
  }

  typedef random_access_iterator_tag iterator_category;
  typedef int value_type;
  typedef int difference_type;
  typedef int* pointer;
  typedef int& reference;
};

main ()
{
  ios::sync_with_stdio(false);
  cout << upper_bound(Iter(0), Iter(100), 40).x << endl;
}

// :collapseFolds=1:folding=explicit:

And this is how the output looks like:

这就是输出的样子：

calculating for x 50
calculating for x 25
calculating for x 12
calculating for x 6
calculating for x 9
calculating for x 8
calculating for x 7
7