# [C++] Simple code using unordered_multimap.

• I'm sharing my C++ code using `unordered_multimap`. Actually, I haven't used unordered_multimap before so I had to learn how to use it. First, the difference between `unordered_map` and `unordered_multimap` is that the latter supports multiple values to be stored with the same key.

I found these links useful to learn how to iterate through multi map.
http://stackoverflow.com/questions/9046922/c-unordered-multimap
http://stackoverflow.com/questions/19716202/boost-unordered-multimap-loop-over-the-unique-keys

The most essential function in using `unordered_multimap` is the `equal_range()` function. It gives iterator to elements from the first and the last+1 th element with the query key. Note also, we need to be careful on how we iterate over unique keys without using extra storage.

Since this is my first time using this container, I might be very suboptimal. I'm open to any suggestions to make the code more elegant and readable.

``````class Solution {
public:
vector<string> anagrams(vector<string> &strs) {

vector<string> result;
unordered_multimap<string, string> dict;

// put everything into multimap
for (int i=0; i<strs.size(); i++){
string key = strs[i];
sort(key.begin(), key.end());
dict.insert( {key, strs[i]} );
}

// loop over unique keys
for (auto iter=dict.begin(); iter!=dict.end(); iter=dict.equal_range(iter->first).second){
auto unique_key = iter->first;
if (dict.count(unique_key) > 1){ // if count is greater than 1, push the values to the result.
auto it_bounds = dict.equal_range(unique_key);
for (auto it=it_bounds.first; it!=it_bounds.second; it++){
result.push_back(it->second);
}
}
}
return result;
}
};
``````

• Good to see the multimap version. You don't need to use `strs[i]` as the second value, just `i` is enough.

I've modified your code to suit my taste. :p

``````class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
vector<string> result;
if (strs.size() < 2) return result;
unordered_multimap<string, int> collections;
for (int i = 0; i < strs.size(); i++){
string s = strs[i];
sort(s.begin(), s.end());
collections.insert({s, i});
}
auto it = collections.begin();
while (it != collections.end()) {
string s = it->first;
if (collections.count(s) > 1) {
auto range = collections.equal_range(s);
for (auto it = range.first; it != range.second; it++){
result.push_back(strs[it->second]);
}
}
it = collections.equal_range(s).second;
}
return result;
}
};
``````

And here is my one-pass `unordered_map` version.

``````class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
vector<string> result;
if (strs.size() < 2) return result;
unordered_map<string, int> cache;
for (int i = 0; i < strs.size(); i++) {
string s = strs[i];
sort(s.begin(), s.end());
auto it = cache.find(s);
if (it == cache.end()) {
cache[s] = i;
} else {
result.push_back(strs[i]);
if (it->second >= 0) {
result.push_back(strs[it->second]);
it->second = -1;
}
}
}
return result;
}
};``````

• BTW, if I remove `if (dict.count(unique_key) > 1){`, it will get Output Limit Exceeded. Seems like a bug of gcc.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.