How to Avoid Code Duplication Implementing Const and Non-Const Iterators

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

[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.

Removing code duplication from const and non-const methods that return iterators

I believe, it is only possible with the helper

typedef int Z;

class X
{
    std::vector<Z> vecZ;    
public:
    std::vector<Z>::iterator foo(size_t index)
    {
        return helper(*this);
    }
    std::vector<Z>::const_iterator foo(size_t index) const
    {
        return helper(*this);
    }

    template <typename T>
    static auto helper(T& t) -> decltype(t.vecZ.begin())
    {
        return t.vecZ.begin();
    }
};

EDIT
Same can be implemented without c++11

template <typename T>
struct select
{
    typedef std::vector<Z>::iterator type;
};
template <typename T>
struct select<const T&>
{
    typedef std::vector<Z>::const_iterator type;
};

template <typename T>
static
typename select<T>::type
helper(T t) 
{
    return t.vecZ.begin();
}

But, well, I think you should think twice before using this approcach

How do I remove code duplication between similar const and non-const member functions?

Yes, it is possible to avoid the code duplication. You need to use the const member function to have the logic and have the non-const member function call the const member function and re-cast the return value to a non-const reference (or pointer if the functions returns a pointer):

class X
{
   std::vector<Z> vecZ;

public:
   const Z& z(size_t index) const
   {
      // same really-really-really long access 
      // and checking code as in OP
      // ...
      return vecZ[index];
   }

   Z& z(size_t index)
   {
      // One line. One ugly, ugly line - but just one line!
      return const_cast<Z&>( static_cast<const X&>(*this).z(index) );
   }

 #if 0 // A slightly less-ugly version
   Z& Z(size_t index)
   {
      // Two lines -- one cast. This is slightly less ugly but takes an extra line.
      const X& constMe = *this;
      return const_cast<Z&>( constMe.z(index) );
   }
 #endif
};

NOTE: It is important that you do NOT put the logic in the non-const function and have the const-function call the non-const function -- it may result in undefined behavior. The reason is that a constant class instance gets cast as a non-constant instance. The non-const member function may accidentally modify the class, which the C++ standard states will result in undefined behavior.

Avoid literally duplicating code for const and non-const with auto keyword?

Ok, so after a bit of tinkering I came up with the following two solutions that allow you to keep the auto return type and only implement the getter once. It uses the opposite cast of what Meyer's does.

C++ 11/14

This version simply returns both versions in the implemented function, either with cbegin() or if you don't have that for your type this should work as a replacement for cbegin(): return static_cast<const A&>(*this).examples.begin(); Basically cast to constant and use the normal begin() function to obtain the constant one.

// Return both, and grab the required one
struct A
{
private:
    // This function does the actual getter work, hiding the template details
    // from the public interface, and allowing the use of auto as a return type
    auto get_do_work()
    {
        // Your getter logic etc.
        // ...
        // ...

        // Return both versions, but have the other functions extract the required one
        return std::make_pair(examples.begin(), examples.cbegin());
    }

public:
    std::vector<int> examples{ 0, 1, 2, 3, 4, 5 };

    // You'll get a regular iterator from the .first
    auto get()
    {
        return get_do_work().first;
    }

    // This will get a const iterator
    auto get() const
    {
        // Force using the non-const to get a const version here
        // Basically the inverse of Meyer's casting. Then just get
        // the const version of the type and return it
        return const_cast<A&>(*this).get_do_work().second;
    }

};

C++ 17 - Alternative with if constexpr

This one should be better since it only returns one value and it is known at compile time which value is obtained, so auto will know what to do. Otherwise the get() functions work mostly the same.

// With if constexpr
struct A
{
private:
    // This function does the actual getter work, hiding the template details
    // from the public interface, and allowing the use of auto as a return type
    template<bool asConst>
    auto get_do_work()
    {
        // Your getter logic etc.
        // ...
        // ...

        if constexpr (asConst)
        {
            return examples.cbegin();

            // Alternatively
            // return static_cast<const A&>(*this).examples.begin();
        }
        else
        {
            return examples.begin();
        }
    }

public:
    std::vector<int> examples{ 0, 1, 2, 3, 4, 5 };

    // Nothing special here, you'll get a regular iterator
    auto get()
    {
        return get_do_work<false>();
    }

    // This will get a const iterator
    auto get() const
    {
        // Force using the non-const to get a const version here
        // Basically the inverse of Meyer's casting, except you get a
        // const_iterator as a result, so no logical difference to users
        return const_cast<A&>(*this).get_do_work<true>();
    }
};

This may or may not work for your custom types, but it worked for me, and it solves the need for code duplication, although it uses a helper function. But in turn the actual getters become one-liners, so that should be reasonable.

The following main function was used to test both solutions, and worked as expected:

int main()
{    
    const A a;
    *a.get() += 1; // This is an error since it returns const_iterator

    A b;
    *b.get() += 1; // This works fine

    std::cout << *a.get() << "\n";
    std::cout << *b.get() << "\n";

    return 0;
}

avoid code duplication when writing iterator and const_iterator

The ternary operator doesn't work like that on types. You can use std::conditional instead:

typedef typename std::conditional<c ,const T*, T*>::type pointer; 

avoiding code duplication in const and non-const member functions

Scott Meyers solved a similar problem in Item 3 of Effective C++ by calling the const version inside the non-const version and then casting the const result back to non-const:

const_iterator find(const T& value) const
{
    // actual implementation of find
}

iterator find(const T& value)
{
    return const_cast<iterator>(static_cast<const container*>(this)->find(value));
}

Best practice for avoiding code duplication while implementing iterator and const_iterator classes

I don't have any experience with implementing iterators, although I think this is similar to other projects. Refactor common code, etc.

Looking at GNU libstdc++'s implementation of std::vector::iterator

#include <bits/stl_iterator_base_funcs.h>
// ...
template ... class vector : ... {
    typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
    typedef __gnu_cxx::__normal_iterator<const_pointer, vector> const_iterator;
};

How to remove code duplication const_iterator and iterator in my case?

One way is to implement the bulk in const_iterator and to let iterator inherit from that. Some const_casts is bound to be required.

Another way is implement the iterator as a template, iterator_impl<> and then add two typedefs:

using iterator = iterator_impl<value_type>;
using const_iterator = iterator_impl<const value_type>;

I've opted for the latter in this answer and made it possible to convert an iterator to a const_iterator, but not the other way around. I have commented on my changes in the code:

#include <cstddef>
#include <iterator>
#include <numeric>
#include <unordered_map>
#include <utility>

template<typename K, typename V>
class MultiMap {
private:
    // these constants can be hidden in here as private:
    static constexpr size_t MAP_NUM_BITS = 5;
    static constexpr size_t MAP_NUM = 1ULL << MAP_NUM_BITS;

    using MapType = std::unordered_map<K, V>;

public:
    // some of the common public typedef's one expects:
    using value_type = typename MapType::value_type;
    using reference = typename MapType::reference;
    using const_reference = typename MapType::const_reference;
    using pointer = typename MapType::pointer;
    using const_pointer = typename MapType::const_pointer;

private:
    using MapIter = typename MapType::iterator;
    using MapConstIter = typename MapType::const_iterator;

    // The iterator template - it's private since it doesn't need to be
    // seen from the outside.

    template<class Type>
    struct iterator_impl {
        // Added a default and a converting constructor - this became necessary
        // when I added the constructor to convert from an iterator to a const_iterator
        iterator_impl() = default;
        iterator_impl(MapIter It, size_t Idx, MapType* mm) :
            it(It), idx(Idx), multi_maps(mm) {}

        // Convert from iterator to const_iterator
        template<class O, std::enable_if_t<std::is_same_v<O, value_type> &&
                                               !std::is_same_v<O, Type>,
                                           int> = 0>
        iterator_impl(const iterator_impl<O>& rhs) :
            it(rhs.it), idx(rhs.idx), multi_maps(rhs.multi_maps) {}

        // these should probably be made into free friend functions
        bool operator==(const iterator_impl& rhs) const { return it == rhs.it; }
        bool operator!=(const iterator_impl& rhs) const { return it != rhs.it; }

        // I didn't modify operator++

        // I made operator->() return a pointer type directly:
        auto operator->() { return &*it; }
        const_pointer operator->() const { return &*it; }

        auto operator*() { return *it; }
        const_reference operator*() const { return *it; }

        // conditionally selecting the underlying iterator type:
        std::conditional_t<
            std::is_same_v<Type, const value_type>,
            MapConstIter, MapIter> it{};

        size_t idx{};
        MapType* multi_maps{};
    };

public:
    // The actual public iterator types a user will use:
    using iterator = iterator_impl<value_type>;
    using const_iterator = iterator_impl<const value_type>;

    // Added cbegin() and cend():
    const_iterator cbegin() const {
        // Since finding the beginning isn't a simple task, I've chosen to
        // reuse the non-const begin() + the conversion to const_iterator here.
        // This should simplify maintenance. Note the safe const_cast here:
        return const_cast<MultiMap*>(this)->begin();
    }

    const_iterator cend() const {
        // same as above for consistency
        return const_cast<MultiMap*>(this)->end();
    }

    // Now these just call cbegin() and cend():
    const_iterator begin() const { return cbegin(); }
    const_iterator end() const { return cend(); }

    iterator begin() {
        size_t idx = 0;
        auto it = multi_maps_[idx].begin();
        while(it == multi_maps_[idx].end() && idx + 1 < MAP_NUM) {
            it = multi_maps_[++idx].begin();
        }
        return {it, idx, multi_maps_};
    }

    iterator end() {
        return {multi_maps_[MAP_NUM - 1].end(), MAP_NUM - 1, multi_maps_};
    }

    // I didn't modify find(), insert(), clear() or compute_idx()

    size_t size() const {
        // Just en example of using a standard algoritm (from <numeric>):
        return std::accumulate(
            std::begin(multi_maps_), std::end(multi_maps_), size_t(0),
            [](size_t current, const auto& m) { return current + m.size(); });
    }

private:
    MapType multi_maps_[MAP_NUM];
    std::hash<K> hasher_{};
};

Copy construction and conversion from iterator to const_iterator now works, but conversion from const_iterator to iterator fails to compile:

int main() {
    MultiMap<int, int>::iterator it1;
    MultiMap<int, int>::iterator it2 = it1;
    it1 = it2;
    MultiMap<int, int>::const_iterator cit1;
    MultiMap<int, int>::const_iterator cit2 = cit1;
    cit1 = cit2;

    cit2 = it1;
    // it1 = cit2; // error: no conversion from const_iterator to iterator
}

How to avoid code duplication between similar const and non-const member functions which pass class members to callbacks?

You can use a static member function template to forward *this to a generic function parameter:

template<typename Self, typename F>
static void for_each_hurg(Self& s, F&& f) {
    for (auto& h : s.hurgs) {
        f(h);
    }
}

template<typename F>
void for_each_hurg(F&& f) { for_each_hurg(*this, forward<F>(f))); }

template<typename F>
void for_each_hurg(F&& f) const { for_each_hurg(*this, forward<F>(f))); }

Since the advent of reference qualifiers for member functions, the general solution is to perfectly forward *this. This doesn't always matter, since you often don't want member functions to be called on rvalues anyway. I'll add this here since I think it is part of a more general solution.

Unfortunately, *this is always an lvalue, so you need additional manual care in the member function wrappers:

template<typename Self, typename F>
static void for_each_hurg(Self&& s, F&& f) {
    /* ... */
}

template<typename F>
void for_each_hurg(F&& f) && { for_each_hurg(move(*this), forward<F>(f))); }

template<typename F>
void for_each_hurg(F&& f) & { for_each_hurg(*this, forward<F>(f))); }

Which is unfortunately not symmetric :(

---

It is also possible to implement the above via a friend function template. This can have two benefits:

• You can move the friend function template to namespace scope, which in the case of furg being a class template reduces the amount of function templates the compiler has to deal with (one per class template, instead of one per instantiation). This typically requires some boilerplate code and forward-declarations, though.
• You can call the function with the same name either as a free function or as a member function, e.g. furg f; for_each_hurg(furg, [](hurg){}); furg.for_each_hurg([](hurg){}); (When unqualified lookup finds a member function, it doesn't perform / ignores the results of ADL. Therefore, you'd have to put the friend function in namespace scope, in order to be able to refer to it via a qualified-id from within the non-static member function wrappers.)

Additionally, you'd have to protect that function template from being to greedy; either by putting it into some namespace detail or adding an enable-if clause. It's probably not worth the effort.

---

Related Topics