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

Subject: Re: [Boost-users] Iterator Range, sub range of a desired size
From: David Kimmel (davidwkimmel_at_[hidden])
Date: 2012-10-30 19:03:10

Understood.  I was just wondering if the two issues you raised about using
distance hinted at a possible better solution.

Yes, at this point though the solution (make_iterator_range, next,
distance, with two ranges) completely satisfies the problem.  It is
definitely a RandomAccessRange type problem.

Thanks to everyone.

On Tue, Oct 30, 2012 at 3:40 PM, Neil Groves <neil_at_[hidden]>wrote:

> 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
>>
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>