Is it possible to have an unordered_map with a non-const key?
Basically, I want a container in which one item can be accessed by many keys. This can be done by defining some kind of multi-cluster class that will be used as the map key type, but since this solution does not allow changing the keys of already inserted elements, I cannot create new aliases for existing records.
I understand that when std::map
keys have to be constant for ordering purposes, but why does this constraint exist with std::unordered_map
?
If need be, I suppose I can just use a pointer map, but is there a better, more elegant solution?
Edit: Thanks for freeing Andrew, Xeo. Nicole, any suggestions as to which container should I use?
source to share
Well, the reason why std::unordered_map
it won't let you change the key is almost the same as the reason why other associative containers won't let you change it: it will mess up the internal organization of this data structure.
The unordered_map
key is used to get the hash, and that hash tells the container where the bucket is putting your item in (and which bucket is retrieving it, of course). If you change the key, you change the hash, which means your item should be moved to a different bucket. It's like deleting it and inserting it again, basically.
The whole idea of an associative container, on the other hand, is that any element is represented by a single value that is fixed, so that its position in the container can be quickly computed as a function of that value. If multiple keys are allowed, which one would you use to quickly determine where an item is stored or should be stored?
What you want is probably a custom data structure with a different complexity than the standard library.
Personally, it seems to me that you are just looking for reference semantics because you intend to share multiple views of the same object. This would naturally lead me to use (smart) pointers, especially when I hear the world "alias". I suggest you go to the map with shared_ptr
both values.
source to share
The associative containers (e.g. map
, unordered_map
) value key
defines the position of the element in the data structure. In non-multi-associative containers, keys are also required to be unique.
If the modification is key
allowed, it will jeopardize the above design invariants.
-
C
map
placing an item in a binary search tree -
B
unordered_map
, associating an item with a hash bucket
If I understand the OP's requirement, then this can be achieved by writing a wrapper in a container insert()
, for example the following C ++ pseudocode - ish:
Iterator insert_wrapper( Container & cont, Element const & elem ) {
if elem in cont {
cont.erase( elem );
}
return cont.insert( elem );
}
source to share
Would you find a map of links more tasteful than a map of pointers?
int value = 6;
std::unordered_map<int, int&> m;
for(int i=0; i<5; ++i)
m.emplace(i, value);
value = 4;
for(auto const& i: m)
std::cout<<i.second<<' ';
Of course, you have to store the actual values somewhere else, as shown in the example.
source to share