如何消除自定义MultiMap中iterator与const_iterator的代码重复

核心思路：迭代器逻辑模板化 #

从根源消除iterator和const_iterator的重复代码，再配合const_cast复用成对的const/非const成员函数逻辑，整体代码重复率可以降到极低。

具体实现 #

1. 通用迭代器模板实现 #

把迭代器的公共逻辑抽成带const属性参数的模板，通过编译期类型推导适配const和非const场景：

#include <unordered_map>
#include <utility>
#include <type_traits>

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;

  // 通用迭代器模板，IsConst参数区分是否为const迭代器
  template<bool IsConst>
  struct IterBase {
    using IterType = std::conditional_t<IsConst, MapConstIter, MapIter>;
    using RefType = std::conditional_t<IsConst, MapConstRef, MapRef>;
    using MapPtrType = std::conditional_t<IsConst, const MapType*, MapType*>;

    IterType it;
    size_t idx;
    MapPtrType multi_maps;

    // 支持非const迭代器转const迭代器
    IterBase(const IterBase<false>& other) requires (IsConst)
      : it(other.it), idx(other.idx), multi_maps(other.multi_maps) {}

    IterBase(IterType i, size_t index, MapPtrType maps) 
      : it(i), idx(index), multi_maps(maps) {}

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

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

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

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

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

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

public:
  using iterator = IterBase<false>;
  using const_iterator = IterBase<true>;

  // 非const版本只实现一次
  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_};
  }

  // const版本直接复用非const逻辑
  const_iterator begin() const {
    return const_cast<MultiMap*>(this)->begin();
  }

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

  const_iterator find(const K& key) const {
    return const_cast<MultiMap*>(this)->find(key);
  }

  // 其余原有逻辑保持不变
  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_;
};

2. 实现说明 #

• 迭代器逻辑只需要编写一次，编译期会自动生成const和非const两个版本的实例，没有运行时开销
• const成员函数复用非const逻辑时，因为begin、find等操作本身是只读的，使用const_cast是完全安全的
• 迭代器的转换构造符合STL容器的常规行为，支持iterator隐式转为const_iterator

内容的提问来源于stack exchange，提问作者dancedpipi