c++ - C++中的多态迭代器

Question

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

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

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

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

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

如果您在 C++ 中使用过多态迭代器，这个问题是如何解决的？还是基于模板的迭代器是 C++ 中唯一“好”的迭代方式？谢谢。

Answer 1

通常的做法是使用编译时多态而不是运行时多态；这使编译器有更多机会使用迭代器优化代码，并且通常在现代 C++ 中更惯用。

如果您确实需要运行时多态行为，那么将多态性封装在迭代器本身中而不将其暴露在外部可能是最简单的。您可以使用 Boost、C++ TR1 和 C++0x 中的多态函数包装器(如 function)来完成此操作。我在这里提供了一个基于我的一个爱好项目中的过滤器迭代器的示例:

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