On 10/29/2012 8:14 AM, Thorsten Ottosen wrote:

On 29-10-2012 08:33, Neil Groves wrote:

...

On Mon, Oct 29, 2012 at 4:40 AM, David Kimmel mailto:davidwkimmel@gmail.com> wrote:

Is there a function in BOOST, given a starting point and a desired size, that returns iterators for a (sub) range?

There are two classes in Boost.Range that achieve this purpose. The first, boost::iterator_range<Iterator> can be used to hold sub-ranges. It is not directly constructible from the form firstIterator, count since this would either require that the Iterator is a model of the RandomAccessConcept or would provide sloppy performance guarantees.

We could consider to add an make_iterator_range which took the count, and then make a static assertion about random access iterators. It seems to me that iterator + count is a quite normal way of creating a range.

-Thorsten

The 'sliced' adaptor is almost there, with it's begin/end indices. http://www.boost.org/doc/libs/1_51_0/libs/range/doc/html/range/reference/ada... Jeff

Whoa fast responses! I like make_iterator_range and sliced but they don't quite seem to do it. Good point on the std::distance. No need to add a new make_iterator_range - I may consider rethinking my approach or just leaving as is. Thanks everyone! On Mon, Oct 29, 2012 at 11:35 AM, Bill Buklis wrote:

On 10/28/2012 11:40 PM, David Kimmel wrote:

...

Is there a function in BOOST, given a starting point and a desired size, that returns iterators for a (sub) range?

For example, given: a boost::circular_buffer which contains: 1 2 3 4 5 6 7 8 9 10 a starting point which is an iterator pointing to 5 and finally a desired size which is an int s = 4

The result of which would be iterators producing: 5 6 7 8

A possible implementation might be this (but I was hoping there was a BOOST version since I can't find an STD algorithm)

template <typename Itr> std::pair getWindowDown(Itr begin, Itr end, Itr start, const int windowSize) { // Down first, then up if need be const Itr bottom = (end - start > windowSize) ? (start + windowSize) : (end); const Itr top = (bottom - begin > windowSize) ? (bottom - windowSize) : (begin); return make_pair(top, bottom); }

Thanks,

Would using next or advance work?

For example, something like:

range = std::make_pair(first, std::next(first, 4));

I can't remember offhand if next is only c++11. If so, there might be a boost::next available. Or alternatively use advance, but it'll require an extra variable to hold the end iterator.

Also, from a purely generic standpoint using std::distance is better than end - start.

-- Bill

______________________________**_________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/**mailman/listinfo.cgi/boost-**usershttp://lists.boost.org/mailman/listinfo.cgi/boost-users

While respecting Thorsten's opinion and the wish to provide convenience functions to our users, I'm not keen on introducing make_iterator_range (iterator, size_type) it seems like an unnecessary addition that would not significantly improve syntax.

I have no strong preference for this, and as the responces show, there are plenty of ways do it. So I with you. -Thorsten

On Tue, Oct 30, 2012 at 4:50 PM, David Kimmel 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

On Tue, Oct 30, 2012 at 7:12 PM, Nathan Ridge wrote:

...

// 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?

The call to distance() will iterate over the range if it's not random-access (or worse, if it's an input range, it will consume it!).

I assume you mean SinglePassRange? We don't have none of those stinking conflated standard library concepts in Boost.Range! *lol* While it is true that my example was knowingly limited to working with ForwardRanges and above it was intended to be an unoptimised reasonably general example to ascertain understanding of the OPs requirements and his problem.

A hand-crafted solution could avoid this.

If you have a start index and a window it seemed pretty unlikely one would need anything other than support for RandomAccessRange to be honest. The context of the problem doesn't make much sense otherwise.

Regards, Nate

Cheers, Neil Groves

On Tue, Oct 30, 2012 at 9:30 PM, David Kimmel 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 wrote:

...

On Tue, Oct 30, 2012 at 4:50 PM, David Kimmel 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Tue, Oct 30, 2012 at 11:03 PM, David Kimmel wrote:

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

If one needs to solve this for iterators that are not random access I see two approaches: 1. Augment your container structure that produces the initial range to track the distance between the range you are building. This might or might not make any sense at all depending on the container and the requirements upon the sub-range. 2. Augment/wrap the iterators so that the wrapped iterator satisfies more requirements than a ForwardIterator by being able to calculate the distance in O(1). This can be achieved by maintaining an additional index. The wrapped iterator would still not model the RandomAccessIterator Concept since it would not need to provide O(1) advance etc. Each of these is probably too much additional work until a concrete use-case presents itself. 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.

Sweet.

Thanks to everyone.

You are very welcome. Thanks for your patience with my slow understanding of the problem. Regards, Neil Groves

On 10/30/2012 12:50 PM, David Kimmel 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.

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()".

typedef vector<int> Vector; Vector v = { 1, 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11 };

cout << "--" << endl; for(auto i : v) { cout << i << " "; } cout << "\n--\n" << endl;

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());

cout << "\n--\nr: "; for(auto i : r) { cout << i << " "; }

cout << "\n--\nr2: "; for(auto i : r2) { cout << i << " "; }

cout << "\n--\n" << endl;

Our application has lots of this type of index/range manipulation. So much in fact it was worth factoring out a open/closed integer range interval class(similar to boost ICL's): class Interval { public: static Interval makeInclusive(int first, int last); static Interval makeExclusive(int begin, int end); static Interval makeInclusiveNormalized(int val1, int val2); static Interval makeExclusiveNormalized(int val1, int val2); static Interval makeSized(int begin, int size); template<class CONTAINER> static Interval makeSized(const CONTAINER& c) { return makeSized(0, c.size()); } int indexBegin() const { return m_begin; } int indexEnd () const { return m_end; } bool empty() const { return m_end == m_begin; } std::size_t size() const { return m_end - m_begin; } ... }; Interval intersection(const Interval& lhs, const Interval& rhs); ... This separates the index math from the final range traversal while providing higher level expression of the intent. Then we can construct a boost::adaptors::sliced using: inline boost::adaptors::sliced slicedFrom(const Interval& i) { return boost::adaptors::sliced(i.indexBegin(), i.indexEnd()); } and use it: int main() { std::vector<float> v(42); Interval vi = Interval::makeSized(v); Interval i = Interval::makeExclusive(37, 93); boost::fill(v | slicedFrom(intersection(vi, i)), 123.456f); return 0; } Jeff