[Boost-users] [range] filtered dereferences underlying range elements twice

[Nathan Ridge]

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.
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Akira Takahashi]

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.range_adaptors.memoized

#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 <zerat...@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:faitha...@gmail.com
blog:http://d.hatena.ne.jp/faith_and_brave/

[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.

----------------------------------------
> Date: Tue, 31 May 2011 15:07:19 +0900
> From: faitha...@gmail.com
> To: boost...@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.range_adaptors.memoized
>
> #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 :

[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 <zerat...@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]

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 <faitha...@gmail.com>:

>>========================
Akira Takahashi
mailto:faitha...@gmail.com
blog:http://d.hatena.ne.jp/faith_and_brave/

[Nathan Ridge]

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: faitha...@gmail.com
> To: boost...@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 :

[Akira Takahashi]

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 <zerat...@hotmail.com>:

>
> How does memoized work? Does it make a copy of the element?
> Does it use dynamic allocation?
>