Iterator over map with uncopyable types-CodePudding

I am trying to implement my own map type and I want an iterator for this map. My understanding is that the value_type of this iterator should be pair<const K, V> (see https://en.cppreference.com/w/cpp/container/map). Now, the iterator's operator* is supposed to return a reference to such a pair. I think this means that I need to store a member in my iterator called current_val so that I can return a reference to it. My question is how to get this to work when V is not copyable. So my implementation looks something like:

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

In this code snippet updating current_val_ doesn't work because it is copying the value into current_val_ but V doesn't support copying.

One possible solution would be to store the data as std::pair<K, V>* instead of storing the keys and values separately, but unfortunately I can't do that.

CodePudding user response：

You should not create a copy. The iterator should provide some means to modify the element in the container, not a copy of that element.

As you are bound to storing the data as K* and V* you cannot simply return a reference to a std::pair<const K,V> because there is no such element to begin with.

You can take a look at std::vector<bool> as an example of container::reference (the type returned from the iterators dereference) not actually being a reference to the element, but some proxy type. This proxy type should be designed to behave like a std::pair<const K,V>&.

Your iterators merely need to store the index into the member arrays, and either a pointer to those arrays or to the whole map. Then you need to use a proxy that implements the methods you want to support:

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

Not tested, but I hope you get the idea.