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
> 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
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?
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net