问题 boost :: adapters :: transformed后跟boost :: adapters :: filtered调用函数两次

我正试图连锁 boost::adaptors::transformed （我们称之为 map）到 boost::adaptors::filtered （我们称之为 filter） - 想法是映射一个 fun 返回“可能”（在我的情况下，一个 std::pair<bool, T>）超出范围并仅输出部分结果。我的第一个实施：

define BOOST_RESULT_OF_USE_DECLTYPE // enable lambda arguments for Boost.Range
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>

struct OnlyEven
{
    typedef int argument_type;
    typedef std::pair<bool, int> result_type;
    result_type operator()(argument_type x) const
    {
        std::cout << "fun: " << x << std::endl;
        return std::make_pair(x % 2 == 0, x);
    }
} only_even;

int main(int argc, char* argv[])
{
    auto map = boost::adaptors::transformed;
    auto filter = boost::adaptors::filtered;
    int v[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto s = v | map(only_even) | filter([](std::pair<bool, int> x)->bool{ return x.first; });
    for (auto i : s) {}
    return 0;
}

当我运行这个时，我得到：

fun: 1
fun: 2
fun: 2
fun: 3
fun: 4
fun: 4
fun: 5
fun: 6
fun: 6
fun: 7
fun: 8
fun: 8
fun: 9
fun: 10
fun: 10

每一次 predicate 是 true， fun 被叫两次。这是预期的行为吗？我做错了什么，或者这是Boost中的一个错误（我使用的是1.48）？

编辑：我在Boost的主干版本上尝试了这个，它仍然会发生。

12539

2017-11-09 02:02

起源

答案:

第一次在传递给过滤器时调用它 - 在增量期间。

在解除引用期间，第二次在基于范围的调用中调用它。它不缓存结果。

即，只是通过范围：

++++++++++boost::begin(s);

给：

fun: 1
fun: 2
fun: 3
fun: 4
fun: 5
fun: 6
fun: 7
fun: 8
fun: 9
fun: 10

检查执行情况 filter_iterator （过滤基于它）。它不做任何缓存。

如果转型很昂贵怎么办？

过滤不要使用知识输入来自哪里。

缓存结果需要大小过滤的迭代器。试想一下应该存储缓存结果的位置。它应该被复制到filter过滤器的某个成员中。

因此，基本上，在用于缓存的空间和解除引用的计数之间存在折衷。

编辑：我已经做了cached_iterator的概念验证，它缓存了解除引用的结果，并在每次推进时使其无效。另外，我已经制作了相应的范围适配器。

它是如何使用的：

auto s = v | transformed(only_even) | cached | reversed | cached | flt | flt | flt | flt | flt | flt;

你应该放置缓存在您想要缓存结果的链中。

现场演示

#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/adaptor/map.hpp>
#include <boost/range/algorithm.hpp>

#include <iostream>
#include <ostream>

// ____________________________________________________________________________________________ //

#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/range/iterator.hpp>
#include <iterator>

namespace impl
{

template<typename Iterator>
class cached_iterator : public boost::iterator_adaptor<cached_iterator<Iterator>,Iterator>
{
    typedef boost::iterator_adaptor<cached_iterator,Iterator> super;
    mutable bool invalidated;
    mutable typename std::iterator_traits<Iterator>::value_type cached;    
public:
    cached_iterator() : invalidated(true) {}
    cached_iterator(const Iterator &x) : super(x), invalidated(true) {}

    typename std::iterator_traits<Iterator>::value_type dereference() const
    {
        if(invalidated)
        {
            cached = *(this->base());
            invalidated=false;
            return cached;
        }
        else
        {
            return cached;
        }
    }
    void increment()
    {
        invalidated=true;
        ++(this->base_reference());
    }
    void decrement()
    {
        invalidated=true;
        --(this->base_reference());
    }
    void advance(typename super::difference_type n)
    {
        invalidated=true;
        (this->base_reference())+=n;
    }
};

template<typename Iterator> cached_iterator<Iterator> make_cached_iterator(Iterator it)
{
    return cached_iterator<Iterator>(it);
}

template< class R >
struct cached_range : public boost::iterator_range<cached_iterator<typename boost::range_iterator<R>::type> >
{
private:
    typedef boost::iterator_range<cached_iterator<typename boost::range_iterator<R>::type> > base;
public:
    typedef R source_range_type;
    cached_range( R& r )
        : base( make_cached_iterator(boost::begin(r)), make_cached_iterator(boost::end(r)) )
    { }
};

template<typename InputRange>
inline cached_range<const InputRange> cache(const InputRange& rng)
{
    return cached_range<const InputRange>(rng);
}

template<typename InputRange>
inline cached_range<InputRange> cache(InputRange& rng)
{
    return cached_range<InputRange>(rng);
}

struct cache_forwarder{};

cache_forwarder cached;

template< class InputRange >
inline cached_range<const InputRange>
operator|( const InputRange& r, cache_forwarder )
{
    return cache(r);
}

template< class InputRange >
inline cached_range<InputRange>
operator|( InputRange& r, cache_forwarder )
{
    return cache(r);
}

} // namespace impl

// ____________________________________________________________________________________________ //


struct OnlyEven
{
    typedef int argument_type;
    typedef std::pair<bool, int> result_type;
    result_type operator()(argument_type x) const
    {
        std::cout << "fun: " << x << std::endl;
        return std::make_pair(x % 2 == 0, x);
    }
} only_even;

int main()
{
    using namespace impl;
    using namespace boost::adaptors;
    using namespace std;

    int v[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto flt =  filtered([](std::pair<bool, int> x)->bool{ return x.first; });

    auto s = v | transformed(only_even) | cached | reversed | cached | flt | flt | flt | flt | flt | flt;

    boost::copy(s | map_values, ostream_iterator<int>(cout,"\n") );
    return 0;
}

输出是：

fun: 10
10
fun: 9
fun: 8
8
fun: 7
fun: 6
6
fun: 5
fun: 4
4
fun: 3
fun: 2
2
fun: 1

2017-11-09 02:21

是的，我只是通过查看代码后想出来的。这有意义吗？ transformed，打电话 fun 两次？考虑其他语言（Python，Haskell等等没有意义）。如果转型很昂贵怎么办？ - bruno nery

在这种情况下，您可以使用“缓存”适配器，如答案中所示。 - Evgeny Panasyuk

感谢缓存的适配器！它解决了问题:) - bruno nery

答案: