Re: [Boost-users] Iterator Range, sub range of a desired size

Subject: Re: [Boost-users] Iterator Range, sub range of a desired size
From: Neil Groves (neil_at_[hidden])
Date: 2012-10-30 18:40:07

On Tue, Oct 30, 2012 at 9:30 PM, David Kimmel <davidwkimmel_at_[hidden]>wrote:

> Nice, that pretty much does it.  Still had to add another range to make
> sure the final range contained the proper size requested (see r2)
>
> auto r = boost::make_iterator_range(
>       boost::next(boost::begin(v), start - 1),
>       boost::next(boost::begin(v), std::min(start - 1 + window,
>              static_cast<int>(boost::distance(v))))
>  );
>
>  auto r2 = boost::make_iterator_range(
> boost::prior(r.end(), std::min( static_cast<int>(r.end()-source.begin()),
> window)),
>  r.end());
>
> Now range r2 should have window number of elements as long as source has
> at least window number of elements.
>
> Finally, sounds like there is an issue with using distance for non random
> access containers or an input range but that should not be a problem in my
> case.
>
>
It isn't an 'issue'. It is well known and documented that distance is O(N)
for anything other than RandomAccessRanges. I was being lazy and didn't
bother reiterating the well-known / documented algorithm restrictions and
performance complexities of the various Range Concepts. It was a good thing
Nate brought this up so that I could make this explicit otherwise it might
have been a bit misleading to newbies. It seemed that your problem-space in
dealing with indices was inherently a world of random-access.

To make this stuff work on lesser Ranges is still possible but requires
either some wrapping of the underlying iterators, or replacing the use of
boost::distance with a different non-member function that gave the upper
limit of the advance offset.

Can you please confirm that your use-case is satisfied by the current
implementation? If you run into any limitations with the current
design/implementation please don't give up; I sometimes take a while to
understand the requirements.

Regards,
Neil Groves

> On Tue, Oct 30, 2012 at 11:05 AM, Neil Groves <neil_at_[hidden]>wrote:
>
>> On Tue, Oct 30, 2012 at 4:50 PM, David Kimmel <davidwkimmel_at_[hidden]>wrote:
>>
>>> I tried it out, yes you can get make_iterator_range with next to work.
>>>  I like boost::next but for what I wanted it does not seem to work
>>> appropriately.  Your example of "make_iterator_range(boost::next(b.begin,
>>> wSize), v.end())" will only skip the first "wSize" elements.  What I want
>>> is a range that contains at most wSize elements (if possible) - taking them
>>> from after (and containing) a start index.
>>>
>>>
>> boost::next absolutely shouldn't be checking against end(), that would
>> not be obeying the zero-overhead principle. For your requirements surely
>> you just alter the parameters to make_iterator_range?
>>
>>
>>> Even my second attempt with this approach (commented out lines) does not
>>> work because next does not check to see if it is past end.  Perhaps if
>>> there is a "min" method I could pass the "boost::next(v.begin() +
>>> (start-1), window)" and "v.end()".
>>>
>>>
>> std::min from <algorithm> ?
>>
>>
>>>  typedef vector<int> Vector;
>>> Vector v = { 1, 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11 };
>>>
>>> const int start = 10;
>>>  const int window = 4;
>>>
>>> auto r = boost::make_iterator_range(boost::next(v.begin(), start-1),
>>> v.end());
>>>  auto r2 = boost::make_iterator_range(boost::prior(r.end(), window),
>>> r.end());
>>>
>>> // auto r = boost::make_iterator_range(v.begin() + (start-1),
>>> boost::next(v.begin() + (start-1), window) );
>>> // auto r2 = boost::make_iterator_range(boost::prior(r.end(), window),
>>> r.end());
>>>
>>>
>>
>> // General solution for all iterator types - assume that source here is v
>> from your example
>> auto r = boost::make_iterator_range(
>>     boost::next(boost::begin(source), start - 1),
>>     boost::next(boost::begin(source), std::min(start - 1 + window,
>> static_cast<int>(boost::distance(source))))
>> );
>>
>> I'm not seeing a problem. Am I misunderstanding your question?
>>
>> Neil Groves
>>
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>