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

Question

I have consulted many answers, but I still haven’t found the best way to implement it.

Now my case is to implement a multi map container, code below:

    #include <unordered_map>
    #include <utility>
    
    static const size_t MAP_NUM_BITS = 5;
    static const size_t MAP_NUM = (size_t)1 << MAP_NUM_BITS;
    
    
    template<typename K, typename V>
    class MultiMap {
      using MapType = std::unordered_map<K, V>;
      using MapIter = typename MapType::iterator;
      using MapRef = typename MapType::reference;
    
    public:
      struct iterator {
        MapIter it;
        size_t idx;
        MapType *multi_maps;
    
        bool operator==(const iterator &rhs) const {
          return it == rhs.it;
        }
    
        bool operator!=(const iterator &rhs) const {
          return it != rhs.it;
        }
    
        iterator& operator++() {
          ++it;
          while (it == multi_maps[idx].end() &&
                 idx + 1 < MAP_NUM) {
            it = multi_maps[++idx].begin();
          }
          return *this;
        }
    
        iterator operator++(int) {
          iterator ret = *this;
          ++*this;
          return ret;
        }
    
        MapIter& operator->() {
          return it;
        }
    
        MapRef operator*() {
          return *it;
        }
      };
    
      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_};
      }
    
      iterator find(const K &key) {
        size_t hash = hasher_(key);
        size_t idx = compute_idx(hash);
        auto it = multi_maps_[idx].find(key);
        if (it == multi_maps_[idx].end()) {
          return end();
        }
        return {it, idx, multi_maps_};
      }
    
      std::pair<iterator, bool> insert(const std::pair<K, V> &data) {
        size_t hash = hasher_(data.first);
        size_t idx = compute_idx(hash);
        auto res = multi_maps_[idx].insert(data);
        return {{res.first, idx, multi_maps_}, res.second};
      }
    
      size_t size() const {
        size_t total_size = 0;
        for (auto &m : multi_maps_) {
          total_size += m.size();
        }
        return total_size;
      }
    
      void clear() {
        for (auto &m : multi_maps_) {
          m.clear();
        }
      }
    
    private:
      size_t compute_idx(size_t hash) const {
        if (MAP_NUM == 1) {
          return 0;
        } else {
          return hash >> (sizeof(size_t) * 8 - MAP_NUM_BITS);
        }
    
      }
    
    private:
      MapType multi_maps_[MAP_NUM];
      std::hash<K> hasher_;
    };

Now it works in my test:

#include <iostream>
#include "multi_map.h"

int main() {

  MultiMap<int, int> mm;
  for (size_t i = 0; i < 5; ++i) {
    mm.insert({2*i, i*i});
  }

  std::cout << "Map size is: " << mm.size() << std::endl;

  for (size_t i = 0; i < 10; ++i) {
    auto it = mm.find(i);
    if (it != mm.end()) {
      std::cout << "Found: " << i << std::endl;
    } else {
      std::cout << "Not found: " << i << std::endl;
    }
  }

  for (auto it = mm.begin(); it != mm.end(); ++it) {
    std::cout << it->first << " : " << it->second << std::endl;
  }

  return 0;
}

But when It refer to const type, thing goes bad!

So I have to implement a const_iterator, so the code is:

include <unordered_map>
#include <utility>

static const size_t MAP_NUM_BITS = 5;
static const size_t MAP_NUM = (size_t)1 << MAP_NUM_BITS;


template<typename K, typename V>
class MultiMap {
  using MapType = std::unordered_map<K, V>;
  using MapIter = typename MapType::iterator;
  using MapConstIter = typename MapType::const_iterator;
  using MapRef = typename MapType::reference;
  using MapConstRef = typename MapType::const_reference;

public:
  struct iterator {
    MapIter it;
    size_t idx;
    MapType *multi_maps;

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

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

    iterator& operator++() {
      ++it;
      while (it == multi_maps[idx].end() &&
             idx + 1 < MAP_NUM) {
        it = multi_maps[++idx].begin();
      }
      return *this;
    }

    iterator operator++(int) {
      iterator ret = *this;
      ++*this;
      return ret;
    }

    MapIter& operator->() {
      return it;
    }

    MapRef operator*() {
      return *it;
    }
  };

  struct const_iterator {
     MapConstIter it;
     size_t idx;
     const MapType *multi_maps;

     bool operator==(const const_iterator &rhs) const {
       return it == rhs.it;
     }

     bool operator!=(const const_iterator &rhs) const {
       return it != rhs.it;
     }

     const_iterator& operator++() {
       ++it;
       while (it == multi_maps[idx].end() &&
              idx + 1 < MAP_NUM) {
         it = multi_maps[++idx].begin();
       }
       return *this;
     }

     const_iterator operator++(int) {
       const_iterator ret = *this;
       ++*this;
       return ret;
     }

     MapConstIter& operator->() {
       return it;
     }

     MapConstRef operator*() {
       return *it;
     }

  };

  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_};
  }

  const_iterator begin() const {
    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_};
  }

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

  iterator find(const K &key) {
    size_t hash = hasher_(key);
    size_t idx = compute_idx(hash);
    auto it = multi_maps_[idx].find(key);
    if (it == multi_maps_[idx].end()) {
      return end();
    }
    return {it, idx, multi_maps_};
  }

  const_iterator find(const K &key) const {
    size_t hash = hasher_(key);
    size_t idx = compute_idx(hash);
    auto it = multi_maps_[idx].find(key);
    if (it == multi_maps_[idx].end()) {
      return end();
    }
    return {it, idx, multi_maps_};
  }

  std::pair<iterator, bool> insert(const std::pair<K, V> &data) {
    size_t hash = hasher_(data.first);
    size_t idx = compute_idx(hash);
    auto res = multi_maps_[idx].insert(data);
    return {{res.first, idx, multi_maps_}, res.second};
  }

  size_t size() const {
    size_t total_size = 0;
    for (auto &m : multi_maps_) {
      total_size += m.size();
    }
    return total_size;
  }

  void clear() {
    for (auto &m : multi_maps_) {
      m.clear();
    }
  }

private:
  size_t compute_idx(size_t hash) const {
    if (MAP_NUM == 1) {
      return 0;
    } else {
      return hash >> (sizeof(size_t) * 8 - MAP_NUM_BITS);
    }

  }

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

The code duplication is unbearable.

For const and non-const function, const_cast will be help:

const_iterator begin() const {
  return const_cast<MultiMap *>(*this)->begin();
}

To do that, I have to add a construct in const_iterator:

const_iterator(const iterator &it) {
  this->it = it.it;
  this->idx = it.idx;
  this->multi_maps = it.multi_maps;
}

There is still too much code duplication here.

Is there a best solution to avoid code duplication in my case?

Answer 1

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
}