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

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 local_messages_d.cg.o
> local_messages_d.cg.cc
> 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 ./local_messages_d.cg.hh:5,
>                  from local_messages_d.cg.cc:1:
> /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]’
> local_messages_d.cg.cc:22:33:   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
boost::distance(Range&).

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

> 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
> http://webEbenezer.net
>
>
>