C++中的多态迭代器

Question

我正在尝试在C++中实现多态迭代器.基本上,我需要这个能够应用一个过滤器,以便迭代器可以跳过一些项目,具体取决于相关的条件.所以我使用抽象接口创建了一个类似GoF的迭代器,这允许我从中派生一个过滤迭代器并实现所需的逻辑.我也更喜欢基于接口的迭代器而不是模板化的迭代器,因为它们允许隐藏实现而不会导致一堆鸭类模板.

但是,多态迭代器不能通过值返回(与STL迭代器相反),所以我必须传递指针,这很容易变得危险,就像在这种情况下,这似乎是合乎逻辑的,但会导致内存泄漏:

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

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

显而易见的解决方案是使用某种智能指针来控制迭代器的生命周期,但人们常说接口应该尽可能简单和通用,因此应该避免使用智能指针？

如果你在C++中使用过多态迭代器,那么这个问题是如何解决的？或者基于模板的迭代器是C++中唯一"好"的迭代方式？谢谢.

Answer 1

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

如果确实需要运行时多态行为,那么将多态性封装在迭代器本身中并且不在外部公开它可能是最容易的.您可以使用多态函数包装器来完成此操作,如functionBoost,C++ TR1和C++ 0x中所示.我在这里提供了一个基于我的一个业余爱好项目的过滤器迭代器的例子:

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表达式作为函数类型)演示了从一个范围中过滤奇数:

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