Re: [Boost-users] [Range] sub_range and list not working together

Subject: Re: [Boost-users] [Range] sub_range and list not working together
From: Brian Wood (woodbrian77_at_[hidden])
Date: 2011-07-13 16:24:28

Neil Groves:
> This compiler error is to be expected because your code is calling the
> size() member function. The size() member function requires that the
> underlying range is a model of the RandomAccessRange Concept. Since you
are
> using a sub_range of a std::list and the std::list has bidirectional
> iterators, the sub_range is a model of the BidirectionalRange Concept.
>
> This has changed between boost versions. The boost::size(Range&) function
> was modified to only work with ranges that model the RandomAccessRange
> Concept because the performance complexity was inconsistent with typical
> expectations. For example, in your case the sub_range size would have been
> O(N) despite the container probably having an O(1) implementation of
size().
> The complexity of std::list size() is not mandated by the standard to be
> O(1), even though it is recommended. If one wishes to pay the price and
> wishes to have a more general 'size' calculation I recommend using
> boost::distance(Range&).

Thanks.  I found this thread which is closely related to what I'm wondering.
http://boost.2283326.n4.nabble.com/Distance-size-of-boost-ranges-for-std-set-td2989642.html

I haven't checked into this much, but would using boost::distance
when the underlying container is a deque or vector, be slower than
using the container's size?

Regards,
Brian Wood
Ebenezer Enterprises
http://webEbenezer.net