C ++中的多态迭代器 [英] polymorphic iterators in C++

问题描述

我想在C ++中实现一个多态迭代器。基本上，我需要这能够应用一个过滤器，以便迭代器将跳过一些项，取决于相关的条件。因此，我制作了一个具有抽象接口的 GoF类迭代器，这允许我以从其导出过滤的迭代器并实现所需的逻辑。我还喜欢基于模板的迭代器，因为它们允许隐藏实现，而不会导致一连串的鸭式模板。

I'm trying to implement a polymorphic iterator in C++. Basically, I need this to be able to apply a filter, so that the iterator would skip some items depending on the associated condition. So I made a GoF-like iterator with an abstract interface, this allows me to derive a filtered iterator from it and implement the required logic. I also prefer interface-based iterators over templated ones as they allow to hide implementation without leading to a mess of duck-typed templates.

但是，多态迭代器不能返回值（相对于STL迭代器），所以我必须传递指针，这可能很容易变得危险，在这种情况下，这似乎是逻辑，但导致内存泄漏：

However, polymorphic iterators cannot be returned by value (as opposed to STL iterators), so I have to pass pointers around, and this can easily become dangerous like in this case, which seems logical but leads to a memory leak:

Iter* Collection::GetIter() {...} // new IterImpl
DoSomething(Iter*) {...} // doesn't do delete

DoSomething(Collection.GetIter()); // convenient, but wrong :\

显而易见的解决方案是使用某种智能指针控制迭代器的生命周期，但人们经常说接口应该尽可能简单和一般，所以聪明的指针应该可能避免？

The obvious solution is to use some kind of smart pointers to control iterators lifetime, but people often say that interfaces should be as simple and as general as possible, so smart pointers should probably be avoided there?

如果你已经处理多态迭代器在C ++中，这个问题如何解决？还是基于模板的迭代器是C ++中唯一的好的迭代方式？感谢。

If you have worked with polymorphic iterators in C++, how was this issue resolved? Or are template-based iterators the only "good" way of iteration in C++? Thanks.

推荐答案

通常的方法是使用编译时多态而不是运行时多态性;这允许编译器更多的机会使用迭代器优化代码，通常在现代C ++中更为惯用。

The usual approach is to use compile-time polymorphism instead of runtime polymorphism; this allows the compiler many more opportunities to optimize code using the iterator and generally is more idiomatic in modern C++.

如果你需要运行时多态行为，它可能是最简单的封装迭代器本身内的多态性，而不是外部暴露。你可以使用一个多态函数包装器来实现这个功能，比如在Boost，C ++ TR1和C ++ 0x中找到的 function 。我在这里提供了一个例子，基于一个我的爱好项目的过滤器迭代器：

If you do need runtime polymorphic behavior, it's probably easiest to encapsulate the polymorphism within the iterator itself and not expose it externally. You can accomplish this using a polymorphic function wrapper like function, found in Boost, C++ TR1, and C++0x. I've provided an example here based on a filter iterator from one of my hobby projects:

template <typename ForwardIt>
class filter_iterator
    : public std::iterator<
          std::forward_iterator_tag, 
          typename std::iterator_traits<ForwardIt>::value_type>

{
public:

    typedef typename std::iterator_traits<ForwardIt>::value_type ValueType;
    typedef typename std::function<bool(ValueType)> FunctionType;

    filter_iterator() { }

    explicit filter_iterator(ForwardIt end)
        : it_(end), end_(end) 
    {
    }

    filter_iterator(ForwardIt it, ForwardIt end, FunctionType is_filtered) 
        : it_(it), end_(end), is_filtered_(is_filtered)
    { 
        skip_filtered_elements(); 
    }

    const ValueType& operator*()  const { return it_.operator*();  }
    const ValueType* operator->() const { return it_.operator->(); }

    filter_iterator& operator++()   
    { 
        ++it_; skip_filtered_elements(); return *this; 
    }

    filter_iterator operator++(int) 
    { 
        filter_iterator it(*this); ++*this; return it; 
    }


    friend bool operator==(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return lhs.it_ == rhs.it_;
    }

    friend bool operator!=(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return !(lhs == rhs);
    }

private:

    void skip_filtered_elements()
    {
        while (it_ != end_ && is_filtered_(*it_))
            std::advance(it_, 1);
    }

    ForwardIt it_;
    ForwardIt end_;

    std::function<bool(const ValueType&)> is_filtered_;
};

template <typename ForwardIt>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt end)
{
    return filter_iterator<ForwardIt>(end);
}

template <typename ForwardIt, typename Function>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt it, 
                                                ForwardIt end, 
                                                Function f)
{
    return filter_iterator<ForwardIt>(it, end, f);
}

用法很简单。这个例子（使用C ++ 0x lambda表达式作为函数类型）演示从范围中过滤奇数：

Usage is straightforward. This example (using a C++0x lambda expression as the function type) demonstrates filtering odd numbers from a range:

int main()
{
    std::array<int, 4> x = { 1, 2, 3, 4 };

    std::copy(make_filter_iterator(x.begin(), x.end(), [](int i) { return i % 2; }),
              make_filter_iterator(x.end()),
              std::ostream_iterator<int>(std::cout, " "));
}

这篇关于C ++中的多态迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！