C++ 中的自定义迭代器

Question

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

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

有什么好的方法可以做到这一点？ 我是否应该创建一个扩展迭代器的类（如果是这样，我应该扩展哪个迭代器类），是否应该创建一个作为迭代器聚合的迭代器类？

我只需要一个 FORWARD_ONLY 迭代器。

即，如果这是我的容器：

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

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

Answer 1

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

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

这个类最初取自 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);
}

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

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

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

Answer 2

如果您有权访问 Boost，请使用 iterator_facade< /code>是最强大的解决方案，而且使用起来非常简单。

Answer 3

首先让我们概括一下：

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

现在迭代器：

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;
        }
    }    
};

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

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

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

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

另一个有趣的练习是将其转换为可与任意容器一起使用的模板。 代码基本相同，只是您必须在一些地方添加 typename 注释。

使用示例：

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";
}

打印：

0 1 2

Answer 4

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

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

一旦您拥有一个可以为您明智地执行此操作的类集合，您将需要修改集合以具有返回迭代器的函数。 至少，您需要

• 一个 begin() 函数，该函数返回位于第一个元素的新迭代器类型的实例；
• 一个 end() 函数，该函数返回一个迭代器，该迭代器（可能名义上）位于您的项目中项目末尾的一个位置。容器

Answer 5

检查视图模板库。

特别是检查

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

Answer 6

这是我能够生成的最简单的代码（对于自定义迭代器）。 请注意，我才刚刚开始探索这个领域。 这会调用内置的 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:

输出如下所示：

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

Answer 7

添加到建议使用 Boost.iterator 的 iterator_facade 来实现自定义迭代器的答案中，我编写了一个独立的、仅包含头文件的库，它模仿了 Boost.iterator 提供的（重要）部分。 好处是没有 Boost 依赖项（也没有除 C++17 之外的任何其他依赖项）。

我的库的一个显着特征是，通过使用它，您的迭代器将始终遵循迭代器接口的标准要求仅此而已。 这确保下游用户不会依赖当前迭代器实现的实现细节（将来可能会被删除/更改）。 这应该有助于提高可移植性和可维护性。

您可以在 https://github.com/Krzmbrzl/iterators 找到该库。

以下是如何使用此库创建自定义迭代器的示例：

#include <iterators/iterator_facade.hpp>

#include <cstddef>
#include <iostream>
#include <iterator>

struct MyCore {
    // Declare what iterator category we are aiming for
    using  target_iterator_category = std::input_iterator_tag;

    // These functions are required for all iterator cores

    MyCore(int *ptr) : m_ptr(ptr) {}
    MyCore(const MyCore &) = default;
    MyCore &operator=(const MyCore &) = default;

    int &dereference() const { return *m_ptr; }

    void increment() { m_ptr += 1; }

    bool equals(const MyCore &other) const { return m_ptr == other.m_ptr; }

private:
    int * m_ptr = nullptr;
};

using MyIterator = iterators::iterator_facade< MyCore >;


// Example usage
int main() {
    int numbers[3] = { 1, 2, 3 };

    MyIterator iter(MyCore{numbers});

    std::cout << *iter << "\n";
    iter++;
    std::cout << *iter << "\n";
    ++iter;
    std::cout << *iter << "\n";

    return 0;
}