Implementing a Stride Iterator

Problem

You have a contiguous series of numbers and you want to iterate through the elements n at a time.

Solution

Example 11-24 presents a stride iterator class as a separate header file.

Example 11-24. stride_iter.hpp

#ifndef STRIDE_ITER_HPP
#define STRIDE_ITER_HPP

#include 
#include 

template
class stride_iter
{
public:
 // public typedefs
 typedef typename std::iterator_traits::value_type value_type;
 typedef typename std::iterator_traits::reference reference;
 typedef typename std::iterator_traits::difference_type
 difference_type;
 typedef typename std::iterator_traits::pointer pointer;
 typedef std::random_access_iterator_tag iterator_category;
 typedef stride_iter self;

 // constructors
 stride_iter( ) : m(NULL), step(0) { };
 stride_iter(const self& x) : m(x.m), step(x.step) { }
 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) {
 assert(x.step == y.step);
 return x.m == y.m;
 }
 friend bool operator!=(const self& x, const self& y) {
 assert(x.step == y.step);
 return x.m != y.m;
 }
 friend bool operator<(const self& x, const self& y) {
 assert(x.step == y.step);
 return x.m < y.m;
 }
 friend difference_type operator-(const self& x, const self& y) {
 assert(x.step == y.step);
 return (x.m - y.m) / x.step;
 }
 friend self operator+(const self& x, difference_type y) {
 assert(x.step == y.step);
 return x += y * x.step;
 }
 friend self operator+(difference_type x, const self& y) {
 assert(x.step == y.step);
 return y += x * x.step;
 }
private:
 Iter_T m;
 difference_type step;
};

#endif

Example 11-25 shows how to use the stride_iter from Example 11-24 to iterate over a sequence of elements two at a time.

Example 11-25. Using stride_iter

#include "stride_iter.hpp"

#include 
#include 
#include 

using namespace std;

int main( ) {
 int a[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
 stride_iter first(a, 2);
 stride_iter last(a + 8, 2);
 copy(first, last, ostream_iterator(cout, "
"));
}

The program in Example 11-25 produces the following output:

0
2
4
6

 

Discussion

Stride iterators are commonplace in matrix implementations. They provide a simple and efficient way to implement matricies as a sequential series of numbers. The stride iterator implementation presented in Example 11-24 acts as a wrapper around another iterator that is passed as a template parameter.

I wanted the stride iterator to be compatible with the STL so I had to choose one of the standard iterator concepts and satisfy the requirements. The stride iterator in Example 11-24 models a random-access iterator.

In Example 11-26, I have provided a separate implementation for stride iterators when the step size is known at compile time, called a kstride_iter. Since the step size is passed as a template parameter, the compiler can much more effectively optimize the code for the iterator, and the size of the iterator is reduced.

Example 11-26. kstride_iter.hpp

#ifndef KSTRIDE_ITER_HPP
#define KSTRIDE_ITER_HPP

#include 

template
class kstride_iter
{
public:
 // public typedefs
 typedef typename std::iterator_traits::value_type value_type;
 typedef typename std::iterator_traits::reference reference;
 typedef typename std::iterator_traits::difference_type difference_type;
 typedef typename std::iterator_traits::pointer pointer;
 typedef std::random_access_iterator_tag iterator_category;
 typedef kstride_iter self;

 // constructors
 kstride_iter( ) : m(NULL) { }
 kstride_iter(const self& x) : m(x.m) { }
 explicit kstride_iter(Iter_T x) : m(x) { }

 // operators
 self& operator++( ) { m += Step_N; 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_N; 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==(self x, self y) { return x.m == y.m; }
 friend bool operator!=(self x, self y) { return x.m != y.m; }
 friend bool operator<(self x, self y) { return x.m < y.m; }
 friend difference_type operator-(self x, self y) {
 return (x.m - y.m) / Step_N;
 }
 friend self operator+(self x, difference_type y) { return x += y * Step_N; }
 friend self operator+(difference_type x, self y) { return y += x * Step_N; }
private:
 Iter_T m;
};

#endif

Example 11-27 shows how to use the kstride_iter.

Example 11-27. Using kstride_iter

#include "kstride_iter.hpp"

#include 
#include 
#include 

using namespace std;

int main( ) {
 int a[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
 kstride_iter first(a);
 kstride_iter last(a + 8);
 copy(first, last, ostream_iterator(cout, "
"));
}