CODEWITHSUNDEEP
c++iterator
Klaus
Klaus

Reputation: 25613

own iterator class not working with std::binary_search

I found a lot of answers here to the topic, but I couldn't get my code to run.

EDIT: The posted example now works after introducing the missing things. In hope some one can use the example as basis for own experiments. I also introduced the missing things to use this example as random access iterator. It works much more efficient with binary_search algos.

If I have to write my own iterator I struggle with value_type and other "specials" to operate with .

I read a lot of articles here how to NOT write iterators but could not get any working example. Especially I read that I should not derive from iterator. So I will ask stupid again:

How can I define the value_type of my iterator. It did not work with in class definition and also did not work with defining manually over type_traits struct. No idea how to continue... 

     #include <iostream>
     #include <algorithm>
     #include <type_traits>
     #include <iterator>

    using namespace std;

    int data[]= { 1,4,7,9,11,20,28 }; //Sorted data

    template < typename T >
    class MyIter
    {
        int offset;
        T* base;

        public:
        typedef int value_type;

        //add the following lines after reading the answers -> it works! 
        typedef std::ptrdiff_t difference_type;
        typedef T * pointer;
        typedef T & reference;
        typedef std::forward_iterator_tag iterator_category;

        // if you want to use as random access iterator:
        // typedef std::random_access_iterator_tag iterator_category;

        public:
        MyIter( T* _base, int _offset) : base(_base), offset(_offset) {}
        MyIter() {}

        bool operator !=( const MyIter& rhs) 
        {
            T* tmp1= base+offset;
            T* tmp2= rhs.base + rhs.offset;

            return tmp1 != tmp2;
        } 

        MyIter operator++(int)
        {
            MyIter tmp(*this);
            offset++;
            return tmp;
        }

        T operator*()
        {
            return *(base+offset);
        }

        // Addition: if used as random access iterator you must provide:
        int operator-(const MyIter& rhs)
        {
            return offset-rhs.offset;
        }

        MyIter operator+=(int off)
        {
            offset+=off;
            return *this;
        }


    };

    typedef MyIter<int> iterType ;

    int main()
    {
        cout << "ok" << endl;

        pair<iterType, iterType> bounds;

        MyIter<int> start( data,0);
        MyIter<int> ende ( data,7);

        bounds = equal_range( start, ende, 28 );

        for ( iterType it= bounds.first; it!=bounds.second; it++)
        {
            cout << "Found " << *it << endl;
        }


        return 0;
    }

Upvotes: 2

Views: 511

Answers (3)

TemplateRex
TemplateRex

Reputation: 70526

You are missing several essential type members and the pre-increment operator (as well as a bunch of other dereference and comparison operators as pointed out by @MikeSeymour). Add thise to your class definition (note that I rewrote the post-increment operators in terms of the currently missing pre-increment operator) to get your binary_search going

typedef std::forward_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;

MyIter& operator++()
{
    ++offset;
    return *this;                      
}

MyIter operator++(int)
{
    MyIter tmp(*this);
    ++*this; // NOTE this will call the other operator++
    return tmp;
}

Output on LiveWorkSpace As pointed out by @JamesKanze, these missing typedefs are provided by inheriting from std::iterator<std::forward_iterator_tag, T>.

Upvotes: 1

Mike Seymour
Mike Seymour

Reputation: 254471

You are missing a few definitions in addition to value_type that the standard library requires from iterators:

typedef std::ptrdiff_t difference_type;
typedef T * pointer;
typedef T & reference;
typedef std::forward_iterator_tag iterator_category;

Alternatively, inheriting from std::iterator<std::forward_iterator_tag, T> will give you these. I don't know where you read that you shouldn't do that, but that's exactly what std::iterator is for.

Additionally, you're missing a pre-increment operator:

MyIter operator++()
{
    ++offset;
    return *this;
}

and also -> and == operators. Also, the dereference operator should probably return a reference to allow *it = 42, with a const overload returning a value or const reference.

Upvotes: 3

James Kanze
James Kanze

Reputation: 153929

std::binary_search requires a random access iterator. Which means that the iterator must support addition and subtraction (+, +=, - and -=), with exactly the same semantics as a pointer. And any number of algorithms will also expect a number of typedef in the iterator: deriving from std::iterator is the easiest way to get them. (Technically, what the standard requires is that std::iterator_traits yield the correct values, so you could explicitly instantiate it for your iterator. But its default implementation picks up typedef in the iterator class.)

EDIT:

Rereading your post: you definitly should publically derive from std::iterator. Whoever says otherwise is wrong.

Upvotes: 1

Related Questions