Guarantees about key uniqueness in std::unordered_multimap

Question

I was wondering about uniqueness of a key object inside an std::unordered_multimap when dealing with iteration.

I'll try to explain the point: I need to associate some data with the key type in the map, this data should not be considered in Hash or KeyEqual elements, but I need it to avoid storing a separate map with it (for optimization purposes).

So the code associated with my idea is the following:

struct Key {
  void* data;
  mutable bool attribute;

  Key(void* data) : data(data), attribute(false) { }
  bool operator==(const Key& other) const {
    return data == other.data;
  }
};

struct KeyHash {
  size_t operator()(const Key& key) const {
    return std::hash<void*>()(key.data);
  }
};

class Foo {
public:
  int i;
  Foo(int i) : i(i) { }
};

std::unordered_multimap<Key, Foo, KeyHash> map;

The problem arises from the fact that although this works fine, there are no guarantees about the fact that the key retrieved as the first element of the std::pair<const Key, Foo> mapping to a single element is always the same. Being a pair of const Key it sounds like that every element in the map has its copy of the key by value, so that if I do

void* target = new int();
map.emplace(std::make_pair(target, Foo(1)));
map.emplace(std::make_pair(target, Foo(2)));


auto pit = map.equal_range(target);
pit.first->first.attribute = true;  
std::cout << std::boolalpha << (++pit.first)->first.attribute << endl;

This yields false which is confirming what I was thinking. So there is indeed a lot of space wasted to store keys if you have multiple values with the same key (which is what you want since you are using an std::unordered_map).

I don't see any other solution rather than something like

struct Value
{
  std::vector<Foo> foos;
  bool attribute;
};

std::unordered_map<void*, Value> map;

Which allows me to pair the attribute with the key but makes everything less clean since it requires working with two levels of iterators.

Are there other solutions I'm not seeing?

Answer 1

23.5.5.1 Class template unordered_multimap overview [unord.multimap.overview]

1 An unordered_multimap is an unordered associative container that supports equivalent keys (an instance of unordered_multimap may contain multiple copies of each key value) and that associates values of another type mapped_type with the keys. The unordered_multimap class supports forward iterators.

An unordered_multimap may contain multiple copies of the key, if you would like a single copy of the key then potentially a unordered_map<K, vector<V>> might be more appropriate.