Boost logo

Boost Users :

Subject: Re: [Boost-users] [Range] sub_range and list not working together
From: Neil Groves (neil_at_[hidden])
Date: 2011-07-13 04:49:57

On Tue, Jul 12, 2011 at 3:43 AM, Brian Wood <woodbrian77_at_[hidden]> wrote:

> B"H
> I've been testing my marshalling support for sub_range and have a
> question.
> In reviewing some old posts and notes, it looks like the following used to
> compile:
> boost::sub_range<std::list<int32_t> > rng;
boost::sub_range<std::list<int32_t> > still works on Boost 1.47.0. I
retested this explicitly after your report and found no defects.

> Today though I get the following error message:
> g++ -Os -s -W -Wall -I. -I ./loki-0.1.7/include/loki/flex -I
> /home/brian/boost_1_47_0_beta1 -c -o
> In file included from
> /home/brian/boost_1_47_0_beta1/boost/range/iterator_range.hpp:13:0,
> from
> /home/brian/boost_1_47_0_beta1/boost/range/sub_range.hpp:23,
> from ./,
> from
> /home/brian/boost_1_47_0_beta1/boost/range/iterator_range_core.hpp: In
> member function ‘boost::iterator_range<IteratorT>::difference_type
> boost::iterator_range<IteratorT>::size() const [with IteratorT =
> std::_List_iterator<int>, boost::iterator_range<IteratorT>::difference_type
> = int]’:
> /home/brian/boost_1_47_0_beta1/boost/range/sub_range.hpp:117:58:
> instantiated from ‘boost::sub_range<ForwardRange>::difference_type
> boost::sub_range<ForwardRange>::size() const [with ForwardRange =
> std::list<int>, boost::sub_range<ForwardRange>::difference_type = int]’
> instantiated from here
> /home/brian/boost_1_47_0_beta1/boost/range/iterator_range_core.hpp:252:32:
> error: no match for ‘operator-’ in ‘((const
> boost::iterator_range<std::_List_iterator<int>
> >*)this)->boost::iterator_range<std::_List_iterator<int> >::m_End - ((const
> boost::iterator_range<std::_List_iterator<int>
> >*)this)->boost::iterator_range<std::_List_iterator<int> >::m_Begin’
> /usr/lib/gcc/i686-redhat-linux/4.5.1/../../../../include/c++/4.5.1/bits/stl_bvector.h:179:3:
> note: candidate is: ptrdiff_t std::operator-(const std::_Bit_iterator_base&,
> const std::_Bit_iterator_base&)
> /home/brian/boost_1_47_0_beta1/boost/range/iterator_range_core.hpp:253:13:
> warning: control reaches end of non-void function
> Is this to be expected? I don't know if a specialization for std::list
> in this regard would be useful, but seems possible.
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

> If I change the list to a vector, everything compiles fine.
> boost::sub_range<std::vector<int32_t> > rng;
> Yes it would, since the sub_range is now a model of the RandomAccessRange

> The following sentence from the docs doesn't make sense to me.
> "counting_range is a function to generator that generates an
> iterator_range wrapping a counting_iterator (from Boost.Iterator). "
> That's because it doesn't make any sense! Thanks for highlighting this
documentation defect. I meant to state that counting_range wraps the range
passed as a parameter using counting_iterator instances. The
counting_iterator implementation comes from Boost.Iterator.

I hope this helps,

Neil Groves

> Regards,
> Brian Wood
> Ebenezer Enterprises

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