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, "
"));
}


Building C++ Applications

Code Organization

Numbers

Strings and Text

Dates and Times

Managing Data with Containers

Algorithms

Classes

Exceptions and Safety

Streams and Files

Science and Mathematics

Multithreading

Internationalization

XML

Miscellaneous

Index

show all menu



C++ Cookbook
Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More
ISBN: 0596003943
EAN: 2147483647
Year: 2006
Pages: 241
Similar book on Amazon

Flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net