CODEWITHSUNDEEP
c++stliterator
nwknoblauch
nwknoblauch

Reputation: 568

Strided iterator incompatible with stl::sort

I've copied some code from a C++ cookbook to implement a strided iterator. The iterator seems to work with other stl functions like copy, but won't work with sort. My guess is that it has something to do with there being some operators missing. Here's my header file for the strided iterator (From the Oreilly C++ cookbook)

#define STRIDEITER_HPP

#include <iterator>
#include <cassert>

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) { };
  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+=(const 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-=(const difference_type x) { m -= x * step; return *this; }
  reference operator[](const 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

I call is using 

#include "strideiter.hpp"
#include <algorithm>
#include <iterator>
#include <iostream>

using namespace std;

int main( ) {

  int *a;
  a =(int*) malloc(10*sizeof(int));

  for(int i=0; i<10; i++)
    {
      a[i]=10-i;
    }

  int skip=2;

  stride_iter<int*> first(a+2, skip);
  stride_iter<int*> last(a + 2+8, skip);
  sort(first,last);
}

I get several errors, the first one is:

strideiter.hpp(52): error: expression must have class type
  assert(x.step == y.step);

Do I need multiple implementations for +=?

Upvotes: 2

Views: 899

Answers (2)

dyp
dyp

Reputation: 39121

Fixing operator+ and providing an operator-(self, difference_type) and it compiles fine. The RandomAccessIterator "concept" and std::sort have a vast amount of requirements, which you can find here in another question involving iterators.

friend self operator+(const self& x, difference_type y) {
  // do not modify `x`, but return a modified copy
  return self(x.m + (y * x.step), x.step);
  // idiomatically:
  // self temp(x);
  // temp += y;
  // return temp;
}
friend self operator+(difference_type x, const self& y) {
  return y+x;
}

friend self operator-(const self& x, difference_type y) {
  return self(x.m - (y * x.step), x.step);
}

For this usage:

int main( ) {

  int a[10];
  //a =(int*) malloc(10*sizeof(int));

  for(int i=0; i<10; i++)
    {
      a[i]=10-i;
    }

  for(int e : a) std::cout << e << ", ";
  std::cout << std::endl;

  int skip=2;

  stride_iter<int*> first(a+2, skip);
  stride_iter<int*> last(a + 2+8, skip);
  sort(first,last);

  for(int e : a) std::cout << e << ", ";
  std::cout << std::endl;
}

The output is:

10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
10, 9, 2, 7, 4, 5, 6, 3, 8, 1,

Which seems reasonable to me.

Upvotes: 4

James Kanze
James Kanze

Reputation: 153939

The problem is that you're declaring the iterator to be a random_access_iterator, but you're not providing the operator+ and operator- functions.

Having said that, your iterator is playing with fire, since it will only work if the size of the container is an exact multiple of the stride. If you have a container with, say, 100 elements, and you ask for a stride of 3, you'll have undefined behavior. To be useful, your iterator will have to pick up both the start and end of the range, so that it can avoid striding over the end (or the beginning, when striding backwards).

Upvotes: 1

Related Questions