Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p ) I would suggest that we introduce a mini-library simply for stride iterators (and k-stride iterators, where the stride factor is a compile-time constant.) Any interest in seeing the following stride iterators submitted to boost as a mini-library? // public domain by Christopher Diggins #ifndef CDIGGINS_STRIDE_ITER_HPP #define CDIGGINS_STRIDE_ITER_HPP #include <iterator> namespace cdiggins { template<class Iter_T> class stride_iter { public: // public typedefs typedef typename std::iterator_traits<Iter_T>::value_type value_type; typedef typename std::iterator_traits<Iter_T>::reference reference; typedef typename std::iterator_traits<Iter_T>::difference_type difference_type; typedef typename std::iterator_traits<Iter_T>::pointer pointer; typedef std::random_access_iterator_tag iterator_category; typedef stride_iter self; // constructors stride_iter() : m(null), step(0) { }; explicit stride_iter(Iter_T x, difference_type n) : m(x), step(n) { } // operators self& operator++() { m += step; return *this; } self operator++(int) { self tmp = *this; m += step; return tmp; } self& operator+=(difference_type x) { m += x * step; return *this; } self& operator--() { m -= step; return *this; } self operator--(int) { self tmp = *this; m -= step; return tmp; } self& operator-=(difference_type x) { m -= x * step; return *this; } reference operator[](difference_type n) { return m[n * step]; } reference operator*() { return *m; } // friend operators friend bool operator==(const self& x, const self& y) { return x.m == y.m; } friend bool operator!=(const self& x, const self& y) { return x.m != y.m; } friend bool operator<(const self& x, const self& y) { return x.m < y.m; } friend difference_type operator-(const self&x, const self& y) { return x.m - y.m; } friend self operator+(const self&x, difference_type y) { return stride_iter(x) += y; } friend self operator+(difference_type x, const self& y) { return stride_iter(y) += x; } private: Iter_T m; difference_type step; }; template<class Iter_T, int Step_N> class kstride_iter { public: // public typedefs typedef typename std::iterator_traits<Iter_T>::value_type value_type; typedef typename std::iterator_traits<Iter_T>::reference reference; typedef typename std::iterator_traits<Iter_T>::difference_type difference_type; typedef typename std::iterator_traits<Iter_T>::pointer pointer; typedef std::random_access_iterator_tag iterator_category; typedef kstride_iter self; // constructors kstride_iter() : m(NULL) { } explicit kstride_iter(Iter_T x) : m(x) { } // operators self& operator++() { m += step(); return *this; } self operator++(int) { self tmp = *this; m += Step_N; return tmp; } self& operator+=(difference_type x) { m += x * Step_N; return *this; } self& operator--() { m -= step(); return *this; } self operator--(int) { self tmp = *this; m -= Step_N; return tmp; } self& operator-=(difference_type x) { m -= x * Step_N; return *this; } reference operator[](difference_type n) { return m[n * Step_N]; } reference operator*() { return *m; } // friend operators friend bool operator==(const self& x, const self& y) { return x.m == y.m; } friend bool operator!=(const self& x, const self& y) { return x.m != y.m; } friend bool operator<(const self& x, const self& y) { return x.m < y.m; } friend difference_type operator-(const self&x, const self& y) { return x.m - y.m; } friend self operator+(const self&x, difference_type y) { return stride_iter(x) += y; } friend self operator+(difference_type x, const self& y) { return stride_iter(y) += x; } private: Iter_T m; }; } #endif Christopher Diggins http://www.cdiggins.com
christopher diggins wrote:
Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p )
You did look at the iterators library, didn't you? http://www.boost.org/libs/iterator/doc/index.html Jonathan
----- Original Message ----- From: "Jonathan Turkanis" <technews@kangaroologic.com> To: <boost@lists.boost.org> Sent: Friday, June 03, 2005 2:00 PM Subject: [boost] Re: stride iterators and matricies
christopher diggins wrote:
Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p )
You did look at the iterators library, didn't you?
Yes. The only thing I saw resembling a stride iterator was permutation iterator. However I did not understand how to make a stride iterator using it. Perhaps it is trivial to create a stride iterator using the iterator library and you could show me how? -Christopher Diggins
christopher diggins wrote:
----- Original Message ----- From: "Jonathan Turkanis" <technews@kangaroologic.com> To: <boost@lists.boost.org> Sent: Friday, June 03, 2005 2:00 PM Subject: [boost] Re: stride iterators and matricies
christopher diggins wrote:
Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p )
You did look at the iterators library, didn't you?
Yes. The only thing I saw resembling a stride iterator was permutation iterator. However I did not understand how to make a stride iterator using it. Perhaps it is trivial to create a stride iterator using the iterator library and you could show me how?
Here's my version: // arch-tag: dc0a48cf-c241-4480-b722-6e181cbd9fca /* * (C) Copyright Neal D. Becker (2004) * Permission to copy, use, modify, sell and distribute this software * is granted provided this copyright notice appears in all copies. * This software is provided "as is" without express or implied * warranty, and with no claim as to its suitability for any purpose. */ #ifndef strided_iterator_hpp #define strided_iterator_hpp #include <boost/iterator/iterator_adaptor.hpp> #include <iterator> namespace boost { template<typename BaseIterator> class strided_iterator : public boost::iterator_adaptor< strided_iterator<BaseIterator>, BaseIterator> { friend class iterator_core_access; public: typedef typename boost::iterator_adaptor<strided_iterator<BaseIterator>,BaseIterator> super_t; typedef typename std::iterator_traits<BaseIterator>::difference_type difference_type; strided_iterator() {} explicit strided_iterator (BaseIterator _base, size_t _stride) : super_t (_base), stride (_stride) {} void increment() { this->base_reference() += stride; } void decrement() { this->base_reference() -= stride; } void advance(difference_type n) { this->base_reference() += n*stride; } difference_type distance_to(strided_iterator<BaseIterator> const& y) const { return (y.base_reference()-this->base_reference())/stride; } private: const int stride; }; template<typename BaseIterator> strided_iterator<BaseIterator> make_strided_iterator(BaseIterator const& begin, int stride) { return strided_iterator<BaseIterator> (begin, stride); } } // namespace boost #endif
----- Original Message ----- From: "Neal Becker" <ndbecker2@gmail.com>
Here's my version:
[snip] That code looks great! Any reason it can't go into boost as is? I would like to see that and a version which takes the step as a template parameter, to improve efficiency when the step size is known at compile-time. -Christopher Diggins
christopher diggins <cdiggins@videotron.ca> writes:
----- Original Message ----- From: "Neal Becker" <ndbecker2@gmail.com>
Here's my version:
[snip]
That code looks great! Any reason it can't go into boost as is? I would like to see that and a version which takes the step as a template parameter, to improve efficiency when the step size is known at compile-time.
A. there are no tests B. What about the undefined behavior that results when you stride off the end of a container? -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
christopher diggins <cdiggins@videotron.ca> writes:
----- Original Message ----- From: "Neal Becker" <ndbecker2@gmail.com>
Here's my version:
[snip]
That code looks great! Any reason it can't go into boost as is? I would like to see that and a version which takes the step as a template parameter, to improve efficiency when the step size is known at compile-time.
A. there are no tests
B. What about the undefined behavior that results when you stride off the end of a container?
Is there any reasonable way to detect this? If it is feasible without significantly increasing cost, I'll add it - but offhand I don't know that it is generally feasible.
Neal Becker <ndbecker2@gmail.com> writes:
David Abrahams wrote:
christopher diggins <cdiggins@videotron.ca> writes:
----- Original Message ----- From: "Neal Becker" <ndbecker2@gmail.com>
Here's my version:
[snip]
That code looks great! Any reason it can't go into boost as is? I would like to see that and a version which takes the step as a template parameter, to improve efficiency when the step size is known at compile-time.
A. there are no tests
B. What about the undefined behavior that results when you stride off the end of a container?
Is there any reasonable way to detect this? If it is feasible without significantly increasing cost, I'll add it - but offhand I don't know that it is generally feasible.
If it's random access you can store a base iterator and an index. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 06/03/2005 02:47 PM, David Abrahams wrote:
Neal Becker <ndbecker2@gmail.com> writes:
David Abrahams wrote: [snip]
B. What about the undefined behavior that results when you stride off the end of a container?
Is there any reasonable way to detect this? If it is feasible without significantly increasing cost, I'll add it - but offhand I don't know that it is generally feasible.
If it's random access you can store a base iterator and an index. ^^^^^ Would "offset" be a better word? An index, i, to me, implies something satisfying:
0 <= i < shape[axis] where axis satisfies: 0 <= axis < rank where rank is the number of dimensions in the array and shape[axis] is the length of the axis-th dimension. With this defintion, I understand what you mean, i.e. instead of the stride iterator incrementing the pointer, it would just store the beginning of the object: X* px0; and increment the offset. Then dereferencing would simply: return *(px0+offset); Is that you're meaning?
Larry Evans <cppljevans@cox-internet.com> writes:
On 06/03/2005 02:47 PM, David Abrahams wrote:
Neal Becker <ndbecker2@gmail.com> writes:
David Abrahams wrote: [snip]
B. What about the undefined behavior that results when you stride off the end of a container?
Is there any reasonable way to detect this? If it is feasible without significantly increasing cost, I'll add it - but offhand I don't know that it is generally feasible.
If it's random access you can store a base iterator and an index. ^^^^^ Would "offset" be a better word? An index, i, to me, implies something satisfying:
0 <= i < shape[axis]
where axis satisfies:
0 <= axis < rank
where rank is the number of dimensions in the array and shape[axis] is the length of the axis-th dimension.
Sure, whatever.
With this defintion, I understand what you mean, i.e. instead of the stride iterator incrementing the pointer, it would just store the beginning of the object:
X* px0;
and increment the offset. Then dereferencing would simply:
return *(px0+offset);
Is that you're meaning?
Yep. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Neal Becker wrote:
Here's my version:
[...] One interesting problem with strided iterators is coming up with end values. Suppose you have int x[ 4 ]; and you want to iterate over x[1] and x[3] with stride 2. Your begin iterator will be x+1, and your end iterator will be x+5 - an invalid address.
Peter Dimov wrote:
Neal Becker wrote:
Here's my version:
[...]
One interesting problem with strided iterators is coming up with end values. Suppose you have
int x[ 4 ];
and you want to iterate over x[1] and x[3] with stride 2. Your begin iterator will be x+1, and your end iterator will be x+5 - an invalid address.
Yup. Simple solution: Don't do that.
Neal Becker wrote:
Peter Dimov wrote:
Neal Becker wrote:
Here's my version:
[...]
One interesting problem with strided iterators is coming up with end values. Suppose you have
int x[ 4 ];
and you want to iterate over x[1] and x[3] with stride 2. Your begin iterator will be x+1, and your end iterator will be x+5 - an invalid address.
Yup. Simple solution: Don't do that.
Don't do what? Use a strided iterator?
Christopher Diggins http://www.cdiggins.com ----- Original Message ----- From: "Peter Dimov" <pdimov@mmltd.net> To: <boost@lists.boost.org> Sent: Friday, June 03, 2005 3:07 PM Subject: Re: [boost] Re: Re: stride iterators and matricies
Neal Becker wrote:
Here's my version:
[...]
One interesting problem with strided iterators is coming up with end values. Suppose you have
int x[ 4 ];
and you want to iterate over x[1] and x[3] with stride 2. Your begin iterator will be x+1, and your end iterator will be x+5 - an invalid address.
I am very confused, isn't x+4 also an invalid address? What is the difference between x+4 and x+5 or any other address not within the range x to x+3 ? - Christopher
christopher diggins wrote:
From: "Peter Dimov" <pdimov@mmltd.net>
Neal Becker wrote:
Here's my version:
[...]
One interesting problem with strided iterators is coming up with end values. Suppose you have
int x[ 4 ];
and you want to iterate over x[1] and x[3] with stride 2. Your begin iterator will be x+1, and your end iterator will be x+5 - an invalid address.
I am very confused, isn't x+4 also an invalid address? What is the difference between x+4 and x+5 or any other address not within the range x to x+3 ?
x+4 is valid but not dereferenceable. x+5 is invalid, it can't be copied or used in comparisons. None of today's platforms enforce this for pointers, but other random access iterators might.
christopher diggins wrote:
Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p ) I would suggest that we introduce a mini-library simply for stride iterators (and k-stride iterators, where the stride factor is a compile-time constant.) Any interest in seeing the following stride iterators submitted to boost as a mini-library?
That would be useful, however your sample code has a problem with the end iterator. To iterate over every second element of a container that has an even length, the one-past-the-end stride-2 iterator is actually TWO past the end of the original container. Unless you have a special container where incrementing beyond the one-past-the-end is allowed, you need another solution (indexing?). [...]
template<class Iter_T> class stride_iter
[...]
template<class Iter_T, int Step_N> class kstride_iter
May I suggest struct VariableStride {}; template <class Iter_T, class Stride /* = VariableStride ? */ > class stride_iterator // ... use as stride_iterator<T, VariableStride> x; stride_iterator<T, boost::mpl::int_<2> > y; Cheers, Ian
----- Original Message ----- From: "Ian McCulloch" <ianmcc@physik.rwth-aachen.de> To: <boost@lists.boost.org> Sent: Friday, June 03, 2005 2:09 PM Subject: [boost] Re: stride iterators and matricies
christopher diggins wrote:
Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p ) I would suggest that we introduce a mini-library simply for stride iterators (and k-stride iterators, where the stride factor is a compile-time constant.) Any interest in seeing the following stride iterators submitted to boost as a mini-library?
That would be useful, however your sample code has a problem with the end iterator. To iterate over every second element of a container that has an even length, the one-past-the-end stride-2 iterator is actually TWO past the end of the original container. Unless you have a special container where incrementing beyond the one-past-the-end is allowed, you need another solution (indexing?).
Would indexing not lead to a similar problem? I would have thought the only way out is to pass a size parameter to the iterator. Do any iterators exist which do not allow incrementing past one past the end? How about if == was defined as : friend bool operator==(const self& x, const self& y) { return (y - x) < step; } and similarly for operator<() ?
[...]
template<class Iter_T> class stride_iter
[...]
template<class Iter_T, int Step_N> class kstride_iter
May I suggest
struct VariableStride {};
template <class Iter_T, class Stride /* = VariableStride ? */ > class stride_iterator // ...
use as
stride_iterator<T, VariableStride> x; stride_iterator<T, boost::mpl::int_<2> > y;
Interesting idea, and more elegant. I would not do it that way, but I would be willing to be it would be more popular to implement as you suggest. -Christopher Diggins
christopher diggins <cdiggins@videotron.ca> writes:
That would be useful, however your sample code has a problem with the end iterator. To iterate over every second element of a container that has an even length, the one-past-the-end stride-2 iterator is actually TWO past the end of the original container. Unless you have a special container where incrementing beyond the one-past-the-end is allowed, you need another solution (indexing?).
Would indexing not lead to a similar problem? I would have thought the only way out is to pass a size parameter to the iterator. Do any iterators exist which do not allow incrementing past one past the end?
When the step size is 3 you go 2 past the end. -- Dave Abrahams Boost Consulting www.boost-consulting.com
christopher diggins wrote:
----- Original Message ----- From: "Ian McCulloch" <ianmcc@physik.rwth-aachen.de> To: <boost@lists.boost.org> Sent: Friday, June 03, 2005 2:09 PM Subject: [boost] Re: stride iterators and matricies
christopher diggins wrote:
Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p ) I would suggest that we introduce a mini-library simply for stride iterators (and k-stride iterators, where the stride factor is a compile-time constant.) Any interest in seeing the following stride iterators submitted to boost as a mini-library?
That would be useful, however your sample code has a problem with the end iterator. To iterate over every second element of a container that has an even length, the one-past-the-end stride-2 iterator is actually TWO past the end of the original container. Unless you have a special container where incrementing beyond the one-past-the-end is allowed, you need another solution (indexing?).
Would indexing not lead to a similar problem? I would have thought the only way out is to pass a size parameter to the iterator. Do any iterators exist which do not allow incrementing past one past the end?
The solution using indexing is to store an integer index and a base iterator. Then operator== on the stride iterator simply checks whether the indices are equal, although it gets more 'interesting' if it is allowed to have such iterators pointing to the same container but with different bases. In principle, incrementing beyond one past the end is disallowed for all iterators. In practice you can probably get away with it for pointers (I think POSIX guarantees it too [unless it overflows], but not sure of that). I would not be surprised at all if it failed for deque::iterator.
How about if == was defined as :
friend bool operator==(const self& x, const self& y) { return (y - x) < step; }
and similarly for operator<() ?
The more fundamental problem is how to avoid incrementing beyond one past the end.
[...]
template<class Iter_T> class stride_iter
[...]
template<class Iter_T, int Step_N> class kstride_iter
May I suggest
struct VariableStride {};
template <class Iter_T, class Stride /* = VariableStride ? */ > class stride_iterator // ...
use as
stride_iterator<T, VariableStride> x; stride_iterator<T, boost::mpl::int_<2> > y;
Interesting idea, and more elegant. I would not do it that way, but I would be willing to be it would be more popular to implement as you suggest.
The reason I suggested that is because for algorithms that you might want to provide specialized implementations for stride iterators, you probably want to work for both compile-time and runtime strides, and to avoid having to write the algorithm twice (or more). template <typename T, typename Stride> void fill(stride_iterator<T, Stride> first, stride_iterator<T, Stride> last) { // optimized implementation using first.base(), first.stride(), ... } and if you really do want to restrict it to compile-time strides you can still do that: template <typename T, int N> void foo(stride_iterator<T, boost::mpl::int_<N> > iter) // ... Cheers, Ian
participants (7)
-
christopher diggins -
David Abrahams -
Ian McCulloch -
Jonathan Turkanis -
Larry Evans -
Neal Becker -
Peter Dimov