c++ - Boost::Range 中的 itertools.tee 等效项？

Question

Python 的 itertools 有 tee 用于 n-plicating iterables:

def tee(iterable, n=2):
    it = iter(iterable)
    deques = [collections.deque() for i in range(n)]
    def gen(mydeque):
        while True:
            if not mydeque:             # when the local deque is empty
                newval = next(it)       # fetch a new value and
                for d in deques:        # load it to all the deques
                    d.append(newval)
            yield mydeque.popleft()
    return tuple(gen(d) for d in deques)

我在 Boost::Range 中找不到等效项。我是不是遗漏了什么，还是应该自己动手？

Answer 1

itertools.tee非常适合 Python 中普遍存在的单遍迭代。例如Generators是单程的，经常使用。

但是如果你已经有了 list/deque，你就不会为它使用 itertools.tee，因为它会涉及多余的重复 - 你可以一遍又一遍地遍历原始 list/deque。

C++ 也有单 channel 范围的概念，例如 Input Iterator ，但它们并不是那么普遍。它是典型 C++ 程序的另一组目标的结果——尽可能为用户提供最大的性能，从而保持最佳性能。如果您愿意，这是另一种心态。

为了说明这一点，让我们比较一下 boost::transformed和 itertools.imap (或 generator expressions ):

它们都通过给定的“棱镜”提供输入序列的 View 。 itertools.imap 返回单遍迭代，而 boost::transformed 返回与输入范围具有相同类别的范围 View - 即，如果您要传递 Random Access Range作为输入，您将得到 Random Access Range 作为结果。

另一个事实是 C++ 使用 value semantics默认情况下，而 python 具有指针语义。这意味着如果在 C++ 中复制迭代器，并“碰撞”它几次 - 原始迭代器将不会改变(尽管如果它是单次传递范围，它可能会失效，但这不是重点)。

但是，有时您确实希望从单次通过范围中累积值并多次查看它们。在这种情况下，最常见的解决方案是手动将值明确地累积到某个容器中。例如:

vector<int> cache(first,last);

---

但是，类似 tee 的包装器在 C++ 中仍然是可能的，这里是概念验证。用法是:

auto forward_range = tee_range(first,last);

tee_range 将single pass range 作为参数并返回forward range(这是multi-pass)(还有ma​​ke_tee_iterator ，在迭代器级别工作)。因此，您可以复制该范围并对其进行多次迭代:

auto r = forward_range;
auto out = ostream_iterator<int>(cout," ");
copy(forward_range,out);
copy(forward_range,out);
copy(r,out);

itertools.tee 也有改进 - 在内部，只有一个 deque 用于缓存值。

live demo :

#include <boost/range/adaptor/transformed.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/smart_ptr/make_shared.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/smart_ptr/shared_ptr.hpp>
#include <boost/container/vector.hpp>
#include <boost/container/deque.hpp>
#include <boost/range/algorithm.hpp>
#include <algorithm>
#include <iterator>
#include <cassert>
#include <limits>

template<typename InputIterator>
class tee_iterator : public boost::iterator_facade
    <
        tee_iterator<InputIterator>,
        const typename std::iterator_traits<InputIterator>::value_type,
        boost::forward_traversal_tag
    >
{
    typedef typename std::iterator_traits<InputIterator>::value_type Value;
    typedef unsigned Index;
    struct Data
    {
        boost::container::deque<Value> values;
        boost::container::vector<tee_iterator*> iterators;
        InputIterator current,end;
        Index min_index, current_index;
        Index poped_from_front;
        //
        Data(InputIterator first,InputIterator last)
            : current(first), end(last), min_index(0), current_index(0), poped_from_front(0)
        {}
        ~Data()
        {
            assert(iterators.empty());
        }
    };
    boost::shared_ptr<Data> shared_data;
    Index index;
    static Index get_index(tee_iterator *p)
    {
        return p->index;
    }
public:
    tee_iterator()
        : index(std::numeric_limits<Index>::max())
    {}
    tee_iterator(InputIterator first,InputIterator last)
        : shared_data(boost::make_shared<Data>(first,last)), index(0)
    {
        shared_data->iterators.push_back(this);
    }
    tee_iterator(const tee_iterator &x)
        : shared_data(x.shared_data), index(x.index)
    {
        if(shared_data)
            shared_data->iterators.push_back(this);
    }
    friend void swap(tee_iterator &l,tee_iterator &r)
    {
        using std::swap;
        *boost::find(l.shared_data->iterators,&l) = &r;
        *boost::find(r.shared_data->iterators,&r) = &l;
        swap(l.shared_data,r.shared_data);
        swap(l.index,r.index);
    }
    tee_iterator &operator=(tee_iterator x)
    {
        swap(x,*this);
    }
    ~tee_iterator()
    {
        if(shared_data)
        {
            erase_from_iterators();
            if(!shared_data->iterators.empty())
            {
                using boost::adaptors::transformed;
                shared_data->min_index = *boost::min_element(shared_data->iterators | transformed(&get_index));
                Index to_pop = shared_data->min_index - shared_data->poped_from_front;
                if(to_pop>0)
                {
                    shared_data->values.erase(shared_data->values.begin(), shared_data->values.begin()+to_pop);
                    shared_data->poped_from_front += to_pop;
                }
            }
        }
    }
private:
    friend class boost::iterator_core_access;
    void erase_from_iterators()
    {
        shared_data->iterators.erase(boost::find(shared_data->iterators,this));
    }
    bool last_min_index() const
    {
        return boost::count
        (
            shared_data->iterators | boost::adaptors::transformed(&get_index),
            shared_data->min_index
        )==1;
    }
    Index obtained() const
    {
        return Index(shared_data->poped_from_front + shared_data->values.size());
    }
    void increment()
    {
        if((shared_data->min_index == index) && last_min_index())
        {
            shared_data->values.pop_front();
            ++shared_data->min_index;
            ++shared_data->poped_from_front;
        }
        ++index;
        if(obtained() <= index)
        {
            ++shared_data->current;
            if(shared_data->current != shared_data->end)
            {
                shared_data->values.push_back(*shared_data->current);
            }
            else
            {
                erase_from_iterators();
                index=std::numeric_limits<Index>::max();
                shared_data.reset();
            }
        }
    }
    bool equal(const tee_iterator& other) const
    {
        return (shared_data.get()==other.shared_data.get()) && (index == other.index);
    }
    const Value &dereference() const
    {
        if((index==0) && (obtained() <= index))
        {
            shared_data->values.push_back(*(shared_data->current));
        }
        assert( (index-shared_data->poped_from_front) < shared_data->values.size());
        return shared_data->values[index-shared_data->poped_from_front];
    }
};

template<typename InputIterator>
tee_iterator<InputIterator> make_tee_iterator(InputIterator first,InputIterator last)
{
    return tee_iterator<InputIterator>(first,last);
}

template<typename InputIterator>
boost::iterator_range< tee_iterator<InputIterator> > tee_range(InputIterator first,InputIterator last)
{
    return boost::iterator_range< tee_iterator<InputIterator> >
    (
        tee_iterator<InputIterator>(first,last),
        tee_iterator<InputIterator>()
    );
}
// _______________________________________________________ //

#include <iostream>
#include <ostream>
#include <sstream>

int main()
{
    using namespace std;
    stringstream ss;
    ss << "1 2 3 4 5";
    istream_iterator<int> first(ss /*cin*/ ),last;
    typedef boost::iterator_range< tee_iterator< istream_iterator<int> > > Range; // C++98
    Range r1 = tee_range(first,last);
    Range r2 = r1, r3 = r1;
    boost::copy(r1,ostream_iterator<int>(cout," "));
    cout << endl;
    boost::copy(r2,ostream_iterator<int>(cout," "));
    cout << endl;
    boost::copy(r2,ostream_iterator<int>(cout," "));
}

输出是:

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 

---

Boost.Spirit有Multi Pass iterator具有相似的目标。

The multi_pass iterator will convert any input iterator into a forward iterator suitable for use with Spirit.Qi. multi_pass will buffer data when needed and will discard the buffer when its contents is not needed anymore. This happens either if only one copy of the iterator exists or if no backtracking can occur.