How to avoid code duplication implementing const and non-const iterators?

Question

I'm implementing a custom container with an STL-like interface. I have to provide a regular iterator and a const iterator. Most of the code for the two versions of the iterators is identical . How can I avoid this duplication?

For example, my container class is Foo, and I'm implementating FooIterator and FooConstIterator. Both of the iterators have to provide methods like operator++() which are identical.

My question is similar to How do I remove code duplication between similar const and non-const member functions?, but the answer to that one is specific to const and non-const methods, especially accessors. I don't see how that might generalize to the iterator problem.

Should I have FooIterator derive from FooConstIterator and extend it with additional non-const methods? That either leads to virtual methods or method hiding, which seem inappropriate here.

Perhaps FooIterator should contain a FooConstIterator. Although that approach does reduce implementation duplication, it seems to re-introduce a lot of boilerplate method definitions.

Is there clever template technique for generating the two iterators from a single definition? Or perhaps there's a way to--shudder--use the preprocessor to stamp out these nearly identical classes.

I've tried looking at my local STL implementation to see how it handle this. There are so many helper classes that I'm having trouble grokking the design, but it looks like the functionality is simply duplicated.

In previous projects, my custom container was built on top of a standard STL container, so I didn't have to provide my own iterators. That's not an option in this case.

Answer 1

[The best answer was, unfortunately, deleted by a moderator because it was a link-only answer. I understand why link-only answers are discouraged; deleting it, however, has robbed future seekers of very useful information. The link has remained stable for more than seven years and continues to work at the time of this writing.]

I strongly recommend the original Dr. Dobb's Journal article by Matt Austern entitled "The Standard Librarian: Defining Iterators and Const Iterators", January 2001. Should that link go bad, now that Dr. Dobb's has ceased operating, it's also available here.

To prevent this replacement answer from being deleted, I will summarize the solution.

The idea is to implement the iterator once as a template that takes an extra template parameter, a boolean that says whether or not this is the const version. Anywhere in the implementation where the const and non-const versions differ, you use a template mechanism to select the correct code. Matt Austern's mechanism was called choose. It looked like this:

template <bool flag, class IsTrue, class IsFalse>
struct choose;

template <class IsTrue, class IsFalse>
struct choose<true, IsTrue, IsFalse> {
   typedef IsTrue type;
};

template <class IsTrue, class IsFalse>
struct choose<false, IsTrue, IsFalse> {
   typedef IsFalse type;
};

If you had separate implementations for const and non-const iterators, then the const implementation would include typedefs like this:

typedef const T &reference;
typedef const T *pointer;

and the non-const implementation would have:

typedef T &reference;
typedef T *pointer;

But with choose, you can have a single implementation that selects based on the extra template parameter:

typedef typename choose<is_const, const T &, T &>::type reference;
typedef typename choose<is_const, const T *, T *>::type pointer;

By using the typedefs for the underlying types, all the iterator methods can have an identical implementation. See Matt Austern's complete example.