Re: [Boost-users] Distance/size of boost ranges for std::set.

Subject: Re: [Boost-users] Distance/size of boost ranges for std::set.
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2010-10-11 08:36:28

On 11.10.2010 11:32, Matthew Gwynne wrote:
> Hi,
>
> I'm working within a C++ library which makes extensive use of the
> range concept, and also of boost::size. The current version of the
> library makes use of boost 1_38, however, updating to the newer
> versions of boost, I've had to replace boost::size with
> boost::distance as some of the ranges involved, such as std::set don't
> have random access iterators.
>
> However, this presents a problem - it's not really acceptable within
> our application to have linear time complexity for the size operation
> on sets when the size member function of the set container is constant
> time, so I'm looking for some advice.
>
> Are we misusing the range concept here and should be using something
> else?
>    
Well, either you're expecting constant-time size for subsets of set, or 
you're using range to represent the entire set. The former is a wrong 
expectation, the latter could be called a misuse, yes. The alternative 
depends on what exactly you're doing currently that requires the size.

Sebastian