Overloading Iterator: C++ Semantics Question

Question

Please note this code was not written by me. Otherwise I would not be asking this question. Full credit goes to Jerry Coffin. Anyways the code generates a sequence of numbers by overloading std::iterator< >.

I will first post the code, then I will give my interpretation of what I am seeing. If an expert C++ member could correct me if I am wrong I would greatly appreciate it.

Code

static const int N = 10;
template <class T>
class sequence : public std::iterator<std::forward_iterator_tag, T>
{
private:
    T val;
public:
    sequence(T init) : val(init) { }
    T operator *( ) { return val; }
    sequence &operator++( ) { ++val; return *this; }
    bool operator != ( const sequence &other ) { return val != other.val; }
};

void foo( )
{
    typedef std::vector<int> graph;
    graph id1( gen_seq(0), gen_seq( N ) );
    display( id1 );                             /* Not declared */
}

/* displays: 0 1 2 3 4 5 6 7 8 9 */

So when looking at this I see that you create a class which contains a value. Now we pass two of those to vector's constructor, which can takes two iterators. Now each time vector's constructor uses the ++ operator on the "sequence" it increments the value inside of the iterator. Technically, you could write:

graph id1( gen_seq( 0 ), gen_seq( 0 ) );

and this would generate the same sequence correct? Or is it the != operator that checks to make sure 0 has not gone to N. Any input on this would help greatly. I just finished reading Stroustrup's C++ Programming Language 3rd edition where he touched upon iterators, however inheriting from them was not a big topic and something I am not fully understanding. Kind of whish I would have done all his exercises, because I remember him asking to overload an iterator a few times.

For completeness sake, note also that a forward iterator must provide the following operations as well: default construction, postfix ++, and equality (==). All three of those can easily be defined in terms of the operators that you've already defined. — James McNellis
– James McNellis, Commented Aug 20, 2011 at 5:29

James McNellis · Accepted Answer · 2011-08-20 05:14:51Z

5

You aren't really overloading an iterator; you're writing your own iterator, which involves overloading a few operators.

That std::vector constructor effectively looks like this:

template <typename ForwardIterator>
vector(ForwardIterator first, ForwardIterator last)
{
    for (ForwardIterator it = first; it != last; ++it)
        push_back(*it);
}

(In reality, it's more complex than that because it needs to handle random-accessible ranges more efficiently, but for a forward iterable range, this is what it does.)

As you can see, that constructor performs three operations on your iterator: it dereferences it (*it), it increments it (++it), and it performs an inequality comparison (it != last). Where it does each of these things, it calls the corresponding operator that you've defined in your custom iterator class.

graph id1( gen_seq( 0 ), gen_seq( 0 ) ); would work, but it would not give the same result: it would leave id1 empty. Based on the explanation in the previous paragraphs, do you see why?

answered Aug 20, 2011 at 5:14

James McNellis

357k76 gold badges934 silver badges983 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Seth Carnegie Over a year ago

I would add that you don't even have to inherit from iterator for this to work.

James McNellis Over a year ago

Right: inheriting from std::iterator just gives your class the typedefs that all iterators are required to have; you could just as easily define them yourself. You can look at your Standard Library implementation's implementation of std::iterator to see what, exactly, it does.

Matthew Hoggan Over a year ago

I do see it, and your post helps, it would not work becuase the for loop would never execute with it!=last would compare the values in my class.

john · Accepted Answer · 2011-08-20 05:19:12Z

3

No graph id1( gen_seq( 0 ), gen_seq( 0 ) ); would generate a zero size vector. Your second explanation using != is closer. Might help if you understood the vector ctor code. It is something like this

template <class II>
vector::vector(II first, II last)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}

As you can see != is being used to determine when to stop adding items to the vector.

(For various technical and efficiency reasons the actual vector ctor code is likely to be much more complex than this, but the above gives the essense as it applies to your case).

answered Aug 20, 2011 at 5:19

john

88.3k5 gold badges61 silver badges95 bronze badges

Collectives™ on Stack Overflow

Overloading Iterator: C++ Semantics Question

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related