Handling duplicate keys as collisions in unordered_map?

[jaffe15]

Hi,
New to using hash_tables and unordered_map. I was wondering if there was a way to handle inserting duplicate keys the same way unordered_map handles collisions. In other words to link/chain the duplicate key element under the original element in the container. And if there is, what is the easiest way to implement that in code.

[seeplus]

What's wrong with using std:::unordered_multimap? This allows duplicate keys.

https://cplusplus.com/reference/unordered_map/unordered_multimap/

[jaffe15]

My assignment specefied using unordered_map unfortunately.

[kigar64551]

If you can't use std::unordered_multimap, which would be the natural choice, you can still use:

1. std::unordered_map<std::string, std::vector<std::string>>

2. std::unordered_map<std::string, std::list<std::string>>


For example:

std::unordered_map<std::string, std::vector<std::string>> map;

void append(const std::string& key, const std::string& value)
{
    map[key].push_back(value); // <-- get (or create) the vector for 'key' and then append 'value' to it
}

const std::vector<std::string>& get_values(const std::string& key)
{
    static const std::vector<std::string> EMPTY;
    auto iter = map.find(key);
    return (iter != map.end()) ? iter->second : EMPTY;
}

[keskiverto]

The (unordered_)map has {Key,Value} pairs. Each Key in it is unique.

std::unordered_map<int,int> myumm;
myumm.emplace( 3, 42 );
myumm.emplace( 3, 7 );
for (auto& x: myumm)
  std::cout << x.first << ": " << x.second << std::endl;

Prints:

3: 42

The multimap can have more than one entry with identical Key.

std::unordered_multimap<int,int> myumm;
myumm.emplace( 3, 42 );
myumm.emplace( 3, 7 );
for (auto& x: myumm)
  std::cout << x.first << ": " << x.second << std::endl;

Prints:

3: 42
3: 7

You know the type of your Key and the type of your Value, but you want more than one value for each Key in the map. You want a collection of Values.

If you can't have std::unordered_map<T,U> due to multiple values
and can't have std::unordered_multimap<T,U> due to "because",
then there is std::unordered_map<T,C<U>> (where C is a suitable collection).

[jonnin]

you are going to have to detect it yourself.
so when you get a key, use 'contains()' or 'at()' members to see if it is there without inserting it. If it isn't there, and you want to insert, ok. If it is there, and you want to insert, you can doctor the key and repeat until you find a key that has not been used. Appending a number is probably sufficient for classroom, eg if the key is 'joebob' then try joebob1, joebob2, ...

and, whatever you do here, you have to match it on your lookup so if you look something up and the key is there, you may want to find all the ones with doctored keys, so ...

another way is to make your map a map of containers, and add duplicates to the container when you get one. This is a little more complex. This sounds like what you want, so when you get a duplicate, just add it to the container under that key, don't mess with the map itself beyond fetching. This is as simple as if (.. .contains(key) ) mymap[key].data.push_back(value); assuming a map of vectors or whatnot that supports push back.

[Duthomhas]

Yes, just push back.

std::unordered_map <std::string, std::vector <std::string> > dictionary;

dictionary["Hello"].emplace_back( "Hello" );
dictionary["Hello"].emplace_back( "Bonjour" );
dictionary["Hello"].emplace_back( "Hola" );
dictionary["Hello"].emplace_back( "Dia dhuit" );

Remember that operator [] automatically adds a key if not present. If it matters, ask whether the key is present before using it.

Since C++20 you can ask if a key is present with .contains(); before that just use the idiomatic .count():

if (dictionary.count( "Hello" )) ...

Hope this helps.