boost :: adapters :: transformedに続いてboost :: adapters :: filtered関数が2回呼び出されました

Question

私はboost::adaptors::transformed（mapとしましょう）をboost::adaptors::filtered（これをfilterとしましょう）にチェーンしようとしています。範囲を超えて「おそらく」（私の場合はstd::pair<bool, T>）を返し、結果の一部のみを出力するfunをマップします。私の最初の実装：

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がfunが2回呼び出され、trueです。これは予想される動作ですか？私は何か間違っているか、/これはBoost（私は1.48を使用しています）のバグですか？

編集：私はこれをブーストのトランクバージョンで試してみましたが、それでも起こります。

Answer 1

初めてフィルタに渡されたときに、インクリメント中に呼び出されます。

2回目は、範囲外の参照中に範囲ベースで呼び出されます。結果はキャッシュされません。

すなわち、ちょうど範囲を通して通過：

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

gives：filter_iteratorの

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

チェック実装（濾過は、それに基づいています）。キャッシングは一切行いません。

変換が高価な場合はどうなりますか？

フィルタリングは、入力がどこから来たのかを知らないでください。

結果をキャッシュするには、フィルタリングされたイテレータのサイズを大きくする必要があります。キャッシュされた結果を保存する場所を考えてください。フィルタリングされたイテレータのメンバーにコピーする必要があります。

基本的に、キャッシュのための領域と逆参照の数の間にトレードオフがあります。

---

編集：私は、概念実証cached_iteratorの間接参照の結果をキャッシュし、各進出でそれを無効にしてきました。また、対応するレンジアダプタを作っています。

ここでは、どのように使われるか：

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

あなたは結果をキャッシュしたいチェーンでをキャッシュされたを配置する必要があります。

live demo

#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