自定义输入迭代器

Question

我有一个需要遍历的自定义只读数据结构。我想创建一个需要跳过某些值的自定义迭代器。

下面是一个简单但等效的示例。我有一个数字向量，我想循环遍历所有跳过负值的向量。通常我会做类似的事情：

vector<int> v;
for (vector<int>::iterator it = v.begin(); it!=v.end(); ++it) {
    if (*it > 0) {
       dosomething(*it);
    }
}

但我想做类似的事情：

vector<int> v;
for (vector<int>::my_iterator it = v.my_begin(); it!=v.my_end(); ++it) {
    dosomething(*it);
}

实现这一目标的正确方法是什么？

Answer 1

这可以通过 boost::filter_iterator 轻松实现，如果您的数据结构已经在底层存储了一个容器。这是一个简单的示例：

#include <vector>
#include <iostream>
#include <boost/iterator/filter_iterator.hpp>

class X{
    typedef std::vector<int> container;
    struct Pred{
        bool operator()(int i){
            return i % 2 == 0;
        }
    };

public:
    typedef boost::filter_iterator<Pred, container::iterator> iterator;

    void add(int val){ nums.push_back(val); }
    iterator begin(){ return iterator(nums.begin(), nums.end()); }
    iterator end(){ return iterator(nums.end(), nums.end()); }

private:
    container nums;
};

int main(){
    X x;
    for(int i=0; i < 10; ++i)
        x.add(i);
    for(X::iterator it = x.begin(), ite = x.end(); it != ite; ++it)
        std::cout << *it << ' ';
}

Ideone 的实时示例。 输出：

0 2 4 6 8

Answer 2

这不是一个很好的解决方案，但无论如何我都会发布它。任何取消引用此迭代器包装器的尝试都将导致它检查当前值并将迭代器推进到超过任何负值。它将被称为 recur，

template<typename InputIterator>
struct nonnegative_iterator : InputIterator {
        template<typename Arg>
        nonnegative_iterator(Arg i) : InputIterator(i) {
        }
        typename InputIterator :: reference operator* () {
            typename InputIterator :: reference x = InputIterator :: operator*();
            if( x < 0) {
                    ++ (*this); // equivalent to this -> operator++ ()
                    return **this;
            } else 
                    return x;
        }
};

可以像这样使用：

 for ( nonnegative_iterator< vector<int>::iterator > it = v.begin(); it!=v.end(); ++it) {

这有一些问题，例如我还没有实现 const 方法来允许取消引用 value_type。因此，使用风险需您自担！

Answer 3

假设您无法控制 vector 的接口，例如因为它实际上是 std::vector，那么您要做的第一件事就是是改变你获取自定义迭代器的方式。也就是说，

for (vector<int>::my_iterator it = v.my_begin(); it != v.my_ned(); ++it)

您可以使用

for (my_iterator it(my_begin(v)), end(my_end(v)); it != end; ++it)

您可以实现自定义容器的修改接口，而不是编写，但这是一个更大的问题。现在创建输入迭代器本质上相当于为底层迭代器创建合适的包装器。这可能看起来像这样：

template <typename InIt, Pred>
struct my_iterator {
    typedef typename std::iterator_traits<InIt>::value_type      value_type;
    typedef typename std::iterator_traits<InIt>::difference_type difference_type;
    typedef typename std::iterator_traits<InIt>::reference       reference;
    typedef typename std::iterator_traits<InIt>::pointer         pointer;
    my_iterator(InIt it, InIt end, Pred pred): it_(it), end_(end), pred_(pred) {}
    bool operator== (my_iterator const& other) const { reutrn this->it_ == other.it_; }
    bool operator!= (my_iterator const& other) const { return !(*this == other); }
    reference operator*() { return *this->it_; }
    pointer   operator->() { return this->it_; }
    my_iterator& operator++() {
        this->it_ = std::find_if(this->it_, this->end_, this->pred_);
        return *this;
    }
    my_iterator operator++(int)
    { my_iterator rc(*this); this->operator++(); return rc; }
private:
    InIt it_, end_;
    Pred pred_;

my_begin() 和 my_end() 函数将创建该类型的合适对象。避免编写此代码的一种方法是查看 Boost 的迭代器适配器：那里应该有合适的东西。