具有不可复制类型的映射迭代器

Question

我正在尝试实现我自己的地图类型，我想要此地图的 iterator。我的理解是这个迭代器的value_type应该是pair<const K, V>（见https://en.cppreference.com/w/cpp/container/map）。现在，迭代器的 operator* 应该是 return 对这样一个对的引用。我认为这意味着我需要在名为 current_val 的迭代器中存储一个成员，以便我可以 return 引用它。我的问题是当 V 不可复制时如何让它工作。所以我的实现看起来像：

template<typename K, typename V>
class Map {
  class Iterator {
   public:
    pair<const K, V>& operator*() { return current_val_; }

    Iterator& operator++() {
      ++index_;
      // Now I need to update current_val_;
      current_val_ = std::make_pair(keys_[i], vals_[i]);
    }

   private:
    pair<const K, V> current_val_;
    int index_ = 0;
    K* keys_;
    V* vals_;
  };
 private:
   K* keys_;
   V* vals_;
};

在此代码片段中更新 current_val_ 不起作用，因为它将值复制到 current_val_ 但 V 不支持复制。

一种可能的解决方案是将数据存储为 std::pair<K, V>* 而不是单独存储键和值，但不幸的是我不能那样做。

Answer 1

您不应创建副本。迭代器应该提供一些方法来修改容器中的元素，而不是该元素的副本。

由于您必须将数据存储为 K* 和 V*，因此您不能简单地 return 对 std::pair<const K,V> 的引用，因为没有这样的元素开始与.

您可以看一下 std::vector<bool> 作为 container::reference 的示例（从迭代器取消引用的 return 类型）实际上并不是对元素的引用，而是一些代理类型。此代理类型应设计为表现得像 std::pair<const K,V>&.

您的迭代器只需要将索引存储到成员数组中，以及指向这些数组或整个映射的指针。然后你需要使用一个代理来实现你想要支持的方法：

class Iterator {
public:
    proxy operator*() { return *this; }
    Iterator& operator++() {
        ++index_;
        return *this;
    }

private:
   int index_ = 0;
   K* keys_;
   V* vals_;
};

struct proxy {
      K* key;
      V* val;
      proxy(const Iterator& it) : key(it.keys_+it.index), val(it.vals_+it.index) {}
      // make it look like a std::pair<const K,V>
      const K& first() { return *key; }
      V& second() { return *val; }
      // enable assignment of std::pair<const K,V>
      proxy& operator=(const std::pair<const K,V>&);
      // comparison with std::pair<const K,V>
      bool operator==(const std::pair<const K,V>&);
      // ... etc ...
};

未测试，但希望您能理解。

具有不可复制类型的映射迭代器

Iterator over map with uncopyable types

c++

iterator