C++中的多态迭代器

2022-01-24 00:00:00 iterator polymorphism c++

我正在尝试在 C++ 中实现多态迭代器.基本上，我需要它才能应用过滤器，以便迭代器根据相关条件跳过一些项目.所以我做了一个带有摘要的 GoF-like 迭代器接口，这允许我从中派生过滤迭代器并实现所需的逻辑.我也更喜欢基于接口的迭代器而不是模板迭代器，因为它们允许隐藏实现而不会导致混乱的鸭子类型模板.

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

相关文章