boost :: adapters :: преобразуется с последующим boost :: adapters :: отфильтрованные вызовы дважды

Я пытаюсь связать 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, и это все еще происходит.

11

Решение

Первый раз вызывается при передаче в ваш фильтр — во время приращения.

Второй раз он вызывается в вашем диапазоне на основе — во время разыменования. Это не кеширует результат.

Т.е., просто проходя через диапазон:

++++++++++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 (фильтруется на основе этого). Это не делает никакого кеширования.

Что если трансформация дорогая?

отфильтрованные не используют знание, откуда поступает информация.

Кэширование результата потребовало бы увеличения размера фильтруемых итераторов. Просто подумайте, где должен храниться кэшированный результат. Он должен быть скопирован в некоторый член отфильтрованного итератора.

Таким образом, в основном, существует компромисс между пространством для кэширования и количеством разыменований.


РЕДАКТИРОВАТЬ: я сделал доказательство концепции 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
10

Другие решения

Других решений пока нет …