C++ iterator and const_iterator problem for own container class

Question

I'm writing an own container class and have run into a problem I can't get my head around. Here's the bare-bone sample that shows the problem.

It consists of a container class and two test classes: one test class using a std:vector which compiles nicely and the second test class which tries to use my own container class in exact the same way but fails miserably to compile.

#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

template <typename T>
class MyContainer
{
public:

  class iterator
  {
  public:
    typedef iterator self_type;
    inline iterator() { }
  };

  class const_iterator
  {
  public:
    typedef const_iterator self_type;
    inline const_iterator() { }
  };

  iterator begin() {
    return iterator();
  }

  const_iterator begin() const {
    return const_iterator();
  }
};

// This one compiles ok, using std::vector
class TestClassVector
{
public:
  void test() {
    vector<int>::const_iterator I=myc.begin();
  }

private:
  vector<int> myc;
};

// this one fails to compile. Why?
class TestClassMyContainer
{
public:
  void test(){
    MyContainer<int>::const_iterator I=myc.begin();
  }

private:
  MyContainer<int> myc;
};


int main(int argc, char ** argv)
{
  return 0;
}

gcc tells me:

test2.C: In member function ‘void TestClassMyContainer::test()’:

test2.C:51: error: conversion from ‘MyContainer::iterator’ to non-scalar type ‘MyContainer::const_iterator’ requested

I'm not sure where and why the compiler wants to convert an iterator to a const_iterator for my own class but not for the STL vector class. What am I doing wrong?

Answer 1

When you call begin() the compiler by default creates a call to the non-const begin(). Since myc isn't const, it has no way of knowing you mean to use the const begin() rather than the non-const begin().

The STL iterator contains a cast operator which allows an iterator to be silently converted to a const_iterator. If you want this to work you need to add one as well like so:

class iterator
{
public:
    typedef iterator self_type;
    inline iterator() { }

    operator const_iterator() { return const_iterator(); }
};

or allow const_iterator to be constructed from an iterator like so:

class const_iterator
{
public:
    typedef const_iterator self_type;

    const_iterator(iterator& ) {}
    inline const_iterator() { }
};

Answer 2

In containers iterator type must be convertible to const_iterator. It is needed for the cases where you iterate through a mutable container using a non-mutable (const) iterator as this makes perfect sense. In your case myc is mutable (non-const), but you create a const iterator on that.

Answer 3

You should have a look to the Boost.Iterators library, especially the iterator_facade and iterator_adaptor sections. They contain a build-up of an iterator "from scratch".

It will show you how to write iterators without too much duplication, because most of the times the code the const and non-const versions is about the same, apart from the const qualification itself. Using templates it's possible to write it once, then declare two different types, and that's what the library documentation illustrates.