Error with custom iterator and STL Algorithm

Question

I am working on a custom iterator for my linear algebra library. I have the following code (slight modification of http://www.cplusplus.com/reference/iterator/iterator/)

template<class T, std::size_t Increment = 1>
class iter: public std::iterator<std::random_access_iterator_tag, T>{   
private:
    T* m_pter;

public:

    iter(T* value):  m_pter(value){}
    iter(const iter& other_it): m_pter(other_it.m_pter){}
    iter& operator++() { m_pter+=Increment; return *this; }
    // iter& operator+() { m_pter += Increment; return *this; }
    bool operator!=(const iter& rhs) {return m_pter!=rhs.m_pter;}
    bool operator<(const iter& rhs) {return m_pter<rhs.m_pter;}
    T& operator*() { return *m_pter; }
};

in the main:

int main(int argc, char *argv[]){

     std::vector<int> a = {1,2,3,4,5,6,7,8,9};
     iter<int, 2> from( &a[0] );
     iter<int, 2> to( &a[8] + 1 );
     for(;from < to;++from){std::cout << *from << std::endl;}
     // std::for_each(from, to, [](int i){std::cout << i << " ";});
     std::cout << std::endl;
}

returns: $ ./main 1 3 5 7 9

which is exactly what I want. However using std::for_each... version returns:

$ ./main
1 3 5 7 9 135121 0 0 many zeros ...

I have no idea why the std algorithm "jumps over" my last element.

score 1 · Accepted Answer · answered Oct 20 '14 at 07:42

1

std::for_each use != but as you have an odd number of element, you never reach the equality.

You have the same error if you replace your loop

for(; from < to; ++from)

by

for(;from != to;++from)

answered Oct 20 '14 at 07:42

Jarod42

203,559
14
181
302

You are right. iter to( &a[8] + 2 ); Actually did the trick. – Vincent Oct 20 '14 at 07:47

score 1 · Answer 2 · answered Oct 20 '14 at 09:18

You need to provide a lot more functions if you declare the iterator as random access: all of the comparison operators, pre- and post-fix ++ and --, +=, -=, + and - with an integral type, and - between to iterators.

But that's not the immediate problem. The imediate problem is that the universally used end condition is ==, and that in a striding iterator, you have to protect against going beyond one past the end. Practically speaking, this means that you need two pointers, one at the current position, and one one past the end, and you need something like:

Iter& operator+=( ptrdiff_t n )
{
    m_current = std::min( m_end - m_current, n * stride );
    return *this;
}

Worse: to support subtraction from one past the end, you need to work out how much you would have incremented to get there, which means either keeping track of the last increment, or keeping the pointer passed to the iterator as well.

You might want to look at the hoops Boost jumps through in its filter_iterator. (In the end, a striding iterator is just a special case of a filtering iterator.) It's not pretty, but it's about the best you can do given the way C++ defines iterators.

Thank you Mr. Kanze. Indeed this is simplified version of the final iterator class. Indeed you are absolutely right: ensuring the iterator does not go end in undefined behaviour is the key issue to ensure proper implementation of the class. However I must also say, compared to a previous version I had (http://stackoverflow.com/questions/26314541/c-speed-comparison-iterator-vs-index) the performance gain is astonishing. So I am confident that I am on the right track. — Vincent, Oct 20 '14 at 09:33

score 0 · Answer 3 · edited Jan 05 '15 at 09:19

0

Can you try providing operator==()?

I'd think that this is the one used by std::foreach()

edited Jan 05 '15 at 09:19

Hemang

26,840
19
119
186

answered Oct 20 '14 at 07:33

lisu

2,213
14
22

... bool operator==(const iter& rhs) {return m_pter==rhs.m_pter;}... same result. – Vincent Oct 20 '14 at 07:38

Error with custom iterator and STL Algorithm

3 Answers3