Re: [boost] [range] Best way to count the elements in a filtered range?

Subject: Re: [boost] [range] Best way to count the elements in a filtered range?
From: Gonzalo Brito Gadeschi (g.brito_at_[hidden])
Date: 2013-06-19 11:08:21

Ok, it seems that both threads have been merged now.

I think boost::size() is what you want.
> size_t s = boost::size(range | filter);

boost::size attempts the following:

boost::end(range) - boost::begin(range)

There are multiple problems with this:
- boost::filtered_iterators which are bidirectional at best (i.e. not
random access, boost::size doesn't work).
- boost::size has constant time complexity. As far as I know, it is
impossible to find the number of elements in a filtered range in constant
time. Thus it cannot be made to work.

This _problems_ are intended behavior. size is associated with constant
time and random access iterators, breaking that is not acceptable.

On the other hand, boost::count has constant time complexity. That is,
overloading it for a single range parameter would allow determining the
elements in a range in linear time without breaking old semantics. This
overload could be specialized to call boost::size when it make sense for
extra performance (complexity is linear time, or better).

On Wed, Jun 19, 2013 at 1:30 PM, Gonzalo Brito Gadeschi <
g.brito_at_[hidden]> wrote:

> Someone suggested to use boost::size in the other thread, but size does
>
> boost::end(rng) - boost::begin(rng)
>
> which is not the number of elements in the filtered range.
>
>
> On Wed, Jun 19, 2013 at 1:04 PM, Gonzalo Brito Gadeschi <
> g.brito_at_[hidden]> wrote:
>
>>
>> I'm not quite sure I'm understanding the question! Does
>>> boost::count( filtered_range );
>>> not do exactly what you want?
>>
>>
>> boost::count takes a value (just like the STL), there is no version of
>> boost::count that simply takes a range.
>>
>> Also, I don't understand why you'd like am rvalue ref version of count
>>> when the argument is const
>>
>>
>> E.g.
>>
>> boost::cout( range | filter );
>>
>> would bind to an rvalue.
>>
>
>