[range] filtered dereferences underlying range elements twice
Hello, It seems that the 'filtered' adaptor dereferences elements of the underlying range twice if they pass the filter. This is illustrated in the following example, where a range is first transformed and then filtered: #include <iostream> #include <boost/range/adaptor/transformed.hpp> #include <boost/range/adaptor/filtered.hpp> #include <boost/range/algorithm/copy.hpp> int transform(int i) { std::cout << "calling transform() on " << i << "\n"; return i + 1; } bool filter(int i) { return i % 2 == 0; } int main() { int a[] = {1, 2, 3, 4, 5, 6, 7, 8}; int b[8]; boost::copy(a | boost::adaptors::transformed(transform) | boost::adaptors::filtered(filter), b); return 0; } The output is: calling transform() on 1 calling transform() on 1 calling transform() on 2 calling transform() on 3 calling transform() on 3 calling transform() on 4 calling transform() on 5 calling transform() on 5 calling transform() on 6 calling transform() on 7 calling transform() on 7 calling transform() on 8 As you can see, the transform function is called twice for elements that pass the filter. Can this be avoided? In my real use case, the transformation performs a database lookup, and it should not be done twice. Thanks, Nate.
Hi, Nathan. Oven Library has solution for this problem. oven::memoized adaptor: http://p-stade.sourceforge.net/oven/doc/html/oven/range_adaptors.html#oven.r... #include <iostream> #include <vector> #include <boost/range/adaptor/transformed.hpp> #include <boost/range/adaptor/filtered.hpp> #include <boost/range/algorithm/copy.hpp> #include <pstade/oven/memoized.hpp> int transform(int i) { std::cout << "calling transform() on " << i << "\n"; return i + 1; } bool filter(int i) { return i % 2 == 0; } int main() { int a[] = {1, 2, 3, 4, 5, 6, 7, 8}; int b[8]; boost::copy(a | boost::adaptors::transformed(transform) | pstade::oven::memoized | boost::adaptors::filtered(filter), b); return 0; } results: calling transform() on 1 calling transform() on 2 calling transform() on 3 calling transform() on 4 calling transform() on 5 calling transform() on 6 calling transform() on 7 calling transform() on 8 2011/5/31 Nathan Ridge <zeratul976@hotmail.com>:
As you can see, the transform function is called twice for elements that pass the filter.
Can this be avoided? In my real use case, the transformation performs a database lookup, and it should not be done twice.
Thanks, Nate.
======================== Akira Takahashi mailto:faithandbrave@gmail.com blog:http://d.hatena.ne.jp/faith_and_brave/
Thanks Akira, it is good to know that there is a workaround. But I was wondering, is it necessary in the first place for filtered to dereference the underlying range elements twice? Thanks, Nate. ----------------------------------------
Date: Tue, 31 May 2011 15:07:19 +0900 From: faithandbrave@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [range] filtered dereferences underlying range elements twice
Hi, Nathan.
Oven Library has solution for this problem. oven::memoized adaptor:
http://p-stade.sourceforge.net/oven/doc/html/oven/range_adaptors.html#oven.r...
#include #include #include #include #include #include int transform(int i) { std::cout << "calling transform() on " << i << "\n"; return i + 1; } bool filter(int i) { return i % 2 == 0; } int main() { int a[] = {1, 2, 3, 4, 5, 6, 7, 8}; int b[8];
boost::copy(a | boost::adaptors::transformed(transform) | pstade::oven::memoized | boost::adaptors::filtered(filter), b);
return 0; }
results: calling transform() on 1 calling transform() on 2 calling transform() on 3 calling transform() on 4 calling transform() on 5 calling transform() on 6 calling transform() on 7 calling transform() on 8
2011/5/31 Nathan Ridge :
As you can see, the transform function is called twice for elements that pass the filter.
Can this be avoided? In my real use case, the transformation performs a database lookup, and it should not be done twice.
Thanks, Nate.
======================== Akira Takahashi mailto:faithandbrave@gmail.com blog:http://d.hatena.ne.jp/faith_and_brave/
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Nate, follow is filtered + transformed adaptor's internal behavior. [filtered] increment iterator behavior: while (!pred(*it)) ++it; dereference iterator behavior: *it; [transformed] increment iterator behavior: ++it; dereference iterator behavior: f(*it); [filtered | transformed] increment iterator behavior: while (!pred(*it)) ++it; dereference iterator behavior: f(*it); [transformed | filtered] increment iterator behavior: while (!pred(f(*it))) ++it; dereference iterator behavior: f(*it); oven::memoized is call once function by stored calculation. 2011/6/1 Nathan Ridge <zeratul976@hotmail.com>:
Thanks Akira, it is good to know that there is a workaround.
But I was wondering, is it necessary in the first place for filtered to dereference the underlying range elements twice?
Thanks, Nate.
High cost sometime if filtered always store dereferenced-value. I think memoized adaptor was better to external store design. or add stored_filtered adaptor. 2011/6/1 Akira Takahashi <faithandbrave@gmail.com>:
Nate, follow is filtered + transformed adaptor's internal behavior.
[filtered] increment iterator behavior: while (!pred(*it)) ++it;
dereference iterator behavior: *it;
[transformed] increment iterator behavior: ++it;
dereference iterator behavior: f(*it);
[filtered | transformed] increment iterator behavior: while (!pred(*it)) ++it;
dereference iterator behavior: f(*it);
[transformed | filtered] increment iterator behavior: while (!pred(f(*it))) ++it;
dereference iterator behavior: f(*it);
oven::memoized is call once function by stored calculation.
2011/6/1 Nathan Ridge <zeratul976@hotmail.com>:
Thanks Akira, it is good to know that there is a workaround.
But I was wondering, is it necessary in the first place for filtered to dereference the underlying range elements twice?
Thanks, Nate.
======================== Akira Takahashi mailto:faithandbrave@gmail.com blog:http://d.hatena.ne.jp/faith_and_brave/
How does memoized work? Does it make a copy of the element? Does it use dynamic allocation? Thanks, Nate. ----------------------------------------
Date: Wed, 1 Jun 2011 12:39:51 +0900 From: faithandbrave@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [range] filtered dereferences underlying range elements twice
High cost sometime if filtered always store dereferenced-value. I think memoized adaptor was better to external store design. or add stored_filtered adaptor.
2011/6/1 Akira Takahashi :
Nate, follow is filtered + transformed adaptor's internal behavior.
[filtered] increment iterator behavior: while (!pred(*it)) ++it;
dereference iterator behavior: *it;
[transformed] increment iterator behavior: ++it;
dereference iterator behavior: f(*it);
[filtered | transformed] increment iterator behavior: while (!pred(*it)) ++it;
dereference iterator behavior: f(*it);
[transformed | filtered] increment iterator behavior: while (!pred(f(*it))) ++it;
dereference iterator behavior: f(*it);
oven::memoized is call once function by stored calculation.
2011/6/1 Nathan Ridge :
Thanks Akira, it is good to know that there is a workaround.
But I was wondering, is it necessary in the first place for filtered to dereference the underlying range elements twice?
Thanks, Nate.
======================== Akira Takahashi mailto:faithandbrave@gmail.com blog:http://d.hatena.ne.jp/faith_and_brave/
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
memoized current implementation use std::deque. Return stored value reference by random access iterator position, in memoized iterator dereference. and not been store to store(push_back). 2011/6/1 Nathan Ridge <zeratul976@hotmail.com>:
How does memoized work? Does it make a copy of the element? Does it use dynamic allocation?
participants (4)
-
Akira Takahashi -
Nathan Ridge