boost :: adattatori :: trasformati seguito da boost :: adattatori :: chiamate chiamate filtrate due volte

Question

Sto provando a concatenare un boost::adaptors::transformed (chiamiamolo map) a boost::adaptors::filtered (chiamiamolo filter) - l'idea è di mappa un fun che restituisce un "Forse" (nel mio caso, un std::pair<bool, T>) su un intervallo e restituisce solo una parte dei risultati. La mia prima implementazione:

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; 
} 

Quando eseguo questo, ottengo:

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 

Ogni volta che il predicate è true, fun è chiamato due volte. È questo comportamento previsto? Sto facendo qualcosa di sbagliato, o è/era un bug in Boost (sto usando 1.48)?

Modifica: Ho provato questo sulla versione tronco di Boost e succede ancora.

Answer 1

La prima volta che viene chiamato quando viene passato al filtro - durante l'incremento.

La seconda volta che viene chiamato nel vostro intervallo basato su - durante il trasferimento. Non memorizza i risultati nella cache.

cioè solo di passaggio gamma:

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

gives:

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

Verifica attuazione filter_iterator (filtrato è basata su esso). Non fa alcun caching.

Cosa succede se la trasformazione è costosa?

filtrato non utilizzare knowladge da cui proviene l'input.

La memorizzazione nella cache del risultato richiederebbe la dimensione crescente degli iteratori filtrati. Basti pensare a dove deve essere memorizzato il risultato della cache. Dovrebbe essere copiato in qualche membro di iteratore filtrato.

Quindi, fondamentalmente, c'è un compromesso tra lo spazio per il caching e il conteggio del dereferenziamento.

---

EDIT: ho fatto proof-of-concept di cached_iterator che memorizza nella cache risultato di dereference, e invalida su ogni avanzamento. Inoltre, ho realizzato un adattatore per campo corrispondente.

Ecco come viene utilizzato:

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

È necessario posizionare cache a catena in cui si desidera memorizzare nella cache risultato.

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; 
} 

uscita è:

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