Boost logo

Boost Users :

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

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?

Brian Wood
Ebenezer Enterprises

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at