Iterator class using a square list

Question

I am trying to implement squarelist by using iteration that points to the head element. I've create this iterator class to make my iterator id directional. I just want to see if I implemented it correctly.

class iterator : public std::iterator<std::bidirectional_iterator_tag , Object , int>
    {

    public:
        iterator(Node* p=nullptr) : _node(p){}
        ~iterator(){}

        Node* getNode(){return _node;}

        Object operator * () { return _node->data; }
        iterator & operator ++()
        {
            _node = _node->next;
            return *this; 
        }

        iterator operator ++(int)
        {
            iterator  retVal = *this;
            ++this;
            return retVal;
        }
        bool operator < (iterator const& rhs) const
        { 
            return _node < rhs._node; 
        }
        bool operator != (iterator const& rhs) const
        {
            return _node != rhs._node;
        }
        bool operator == (iterator const& rhs) const 
        {
            return _node == rhs._node;
        }
    };

Answer 1

A couple of real issues (rather than the imaginary ones previously pointed out):

Your code does not fully implement the requirements of iterator.

• You have not implemented the operator-> as required by the iterator concept.
• operator* should return by reference.
  This is because *x = t is a requirement of iterator and without the reference this will not work as expected (or at all depending).

Without the container code its hard to tell if you can use the same iterator for both const and non-const iterator types. So sometimes its useful to provide const overloads of the above (but that will depend on usage).

see: http://www.sgi.com/tech/stl/trivial.html

You classify your iterator as

std::bidirectional_iterator_tag

This is an indication that you can go backwards and forwards with the iterator. In fact the concept means that your iterator must also support operator-- are well as operator++.

See: http://www.sgi.com/tech/stl/BidirectionalIterator.html

The link you provide indicates that a square list is circular. So moving forward all the time you may never reach the end. But without understanding (or seeing your implementation) it is hard to tell if the current implementation will work.

    iterator & operator ++()
    {
        _node = _node->next;   // Will this ever reach a NULL
                               // Or do you have a special version of
                               // iterator that marks the end.
                               //
                               // Note: end is one past the last element
                               //       Which makes this doubly hard to
                               //       implement with a circular list.
                               //       But can be done if you use a sentinel.
                               //
                               // The default constructor suggests that the
                               // end is marked by a NULL but hard to be sure.
        return *this; 
    }

No point in defining destructor the default version will work perfectly. (As a side note: since it is not virtual there can be no derived types with alternative behaviors so making things symmetric is doubly useless).

    ~iterator(){}

This is perfectly fine.

        iterator  retVal = *this;

But just as a personal preference I prefer:

        iterator  retVal(*this);

As mentioned above (but without the container code it is hard to tell). Well this test work for the end iterator.

    bool operator != (iterator const& rhs) const
    {
        return _node != rhs._node;
    }
    bool operator == (iterator const& rhs) const 
    {
        return _node == rhs._node;
    }

There is no requirement for bidirectional iterators to have a less than comparison. Unless you really want to store iterators in a sorted container I would leave this out.

Note: A random access iterator does have a requirement for a less than operator. But it has a precondition that it can only compare iterators that are reachable from each other.

see: http://www.sgi.com/tech/stl/RandomAccessIterator.html

    bool operator < (iterator const& rhs) const
    { 
        return _node < rhs._node; 
    }

The second thing to consider is the sort ordering correct?

1. You are defining the less than operator in term of pointer arithmetic. Unless the object are allocated by the same allocators from a known block this is actually undefined behavior. For pointer comparison to be valid they need to be in the same allocated block.
2. Is this a good ordering? Youre ordering is based on their address (not the position in the container). So things may be in a jumbled up state in relation to everything else. This may be perfectly fine but something you should keep in mind.

WHY The following answers is a complete waste of time and WRONG

So please stop voting for it.

I learnt about its importance following discussions on one of the C++ working groups. It's a good practice to follow smarter people.

Yes but you have to also understand when to apply these principles. Some ideas contradict other ideas if you just use them bluntly. You need to understand each idea but also when to apply it.

The concept of operator symmetry is an important concept when used in the correct situation (no argument there). The problem is that iterators are not the correct situation and it plays no part.

But we have two competing concepts at play here. One: is symmetry is good. Two: auto conversion of types by the compiler is bad.

You have to balance the two concepts. In terms of iterators auto converting iterators is a very bad idea. You want to make the user of the iterator be explicit about any conversions (as the STL designers did (see below)). As a result the symmetry concept can not be used (as it requires auto conversion).

Why it makes no sense for auto conversion

 Container    x;
 AltCont      y;

 // You can not compare iterators
 // From different containers.
 if (x.begin() < y.end()) {
     // At best this is undefined
     // At worst this is undefined behavior.
 }

 // There is no logic to that situation.
 // SO because you should not compare iterators from different
 // containers the type of the iterator when being tested will
 // ***ALWAYS*** be the same type.

 // The type of the iterator is always `Container::iterator`
 // Its a required property of a container.
 Container::iterator  begin = x.begin();
 Container::iterator  end   = x.end(); 

Q: A but you can create other types of iterator from your iterator.
A: Yes. But this new type is not comparable to the old type.

typedef std::reverse_iterator<Container::iterator> reverse_iterator;
reverse_iterator rbegin(end);
reverse_iterator rend(begin);

The types are still not comparable.

 if (begin < rbegin) {  // Compile time error
 }                      // For a good reason
                        // there is no logical reason for the ranges
                        // to be equivalent. 

You will also note it does not work the other way around.

 if (rbegin < begin) {
 }

Why you ask is this second case a big deal. Well there is no constructor on Cont::iterator to create an object of type std::reverse_iterator<Cont::iterator>. So in the first test above there was no way to convert rbegin into the correct type.

BUT there is a constructor on std::reverse_iterator<Cont::iterator> that takes an object of Cont::iterator so in the second condition we could be in a situation where begin is auto converted into std::reverse_iterator<Cont::iterator> and the expression would compile. But luckily for us the designers of the STL decided that was a bad idea and made the constructor explicit to prevent auto conversion and thus prevent the code from compiling.

OK so why is in Dangerous

Its also hides errors. The above code will generally generate a compiler error (so you spot it and correct it quickly). But lets dig in and build the code as suggested by @vinipsmaker.

For this to work there either has to be a conversion from one iterator to the other or as he suggests a base class and a derived type.

 class IterBase
 {  /* Define iterator */ }

 class IterDerivedForCont1: public IterBase
 {  /* Define iterator */ }

 class IterDerivedForCont2: public IterBase
 {  /* Define iterator */ }

 class Cont1 {
     typedef IterDerivedForCont1 iterator;
     /* Other Stuff */
 }

 class Cont2 {
     typedef IterDerivedForCont2 iterator;
     /* Other Stuff */
 }

 bool operator<(IterBase const& l, IterBase const& r)
 { return TEST(l,r);}

 Cont1   a;
 Cont2   b;

 if (a.begin() < b.end()) {
     // You want this to compile?
     // Not really. But it will
 }

 // So in this case you are hiding errors from the user.
 // That could have been easily spotted by the compiler.

Answer 2

You almost got the bool operator < (iterator const& rhs) const (same for other operators overloading) right.

The idea is to make the left operand behave semantically equals to the right operand.

You went one step forward with this idea by defining the argument type as const&. Then, if I create a class that inherits from your class, the following would work:

iterator i;
derived j;
i < i;
j < i;
j < j;
i < j;

The problem lies on objects implicitly convertible to iterator. They cannot be used as a left-argument for the expression. You loses the symmetry property.

Define as non-member functions and everything is gonna be alright. Declare it as friend if needed.

I learnt about its importance following discussions on one of the C++ working groups. It's a good practice to follow smarter people.