Get all the keys which matches a query in a map

Question

Say I have more than one key with the same value in a map. Then in that case how do I retrieve all keys that matches a query.

Or, Is there any possibility to tell find operation to search after a specific value.
I am using an std::map, C++.

I suspect that you might be confusing the term "value". Maps are said to map from keys to value, but I think you are saying value as in "the value of the key", not "the value the key maps to". If this is the case, a `std::map` will overwrite the old entry if you reuse the same key twice. `std::multimap` supports multiple uses of the same key. — Yakk - Adam Nevraumont, Nov 02 '12 at 21:00

James · Answer 1 · 2012-11-02T21:12:38.837

2

Would something like this work for you:

void FindKeysWithValue(Value aValue, list<Key>& aList)
{
    aList.clear();

    for_each(iMap.begin(), iMap.end(), [&] (const pair<Key, Value>& aPair)
    {
        if (aPair.second == aValue)
        {
            aList.push_back(aPair.first);
        }
    });
}

edited Nov 02 '12 at 21:12

answered Nov 02 '12 at 20:56

James

9,064
3
31
49

I suggest using `const pair&` here. – Mikhail Nov 02 '12 at 21:01

score 1 · Answer 2 · edited May 23 '17 at 11:55

1

The only way is to iterate over map.

this link may be useful: Reverse map lookup

edited May 23 '17 at 11:55

Community

1
1

answered Nov 02 '12 at 20:56

Nahuel Fouilleul

18,726
2
31
36

score 1 · Accepted Answer · answered Nov 02 '12 at 20:57

The associative containers probably won't help you too much because for std::map<K, V> the key happens to be unique and chances that your chosen query matches the ordering relation you used may not be too high. If the order matches, you can use the std::map<K, V> members lower_bound() and upper_bound(). For std::multimap<K, V> you can also use equal_range().

In general, i.e., if you query isn't really related to the order, you can use std::copy_if() to get a sequence of objects matching a predicate:

Other other;
// ...
std::vector<Other::value_type> matches;
std::copy_if(other.begin(), other.end(), 
             std::back_inserter(matches), predicate);

When copying the elements is too expensive, you should probably consider using std:find_if() instead:

for (auto it(other.begin());
    other.end() != (it = std::find_if(it, other.end(), predicate));
    ++it) {
   // do something with it
}

score 1 · Answer 4 · answered Nov 02 '12 at 21:01

Provided you want quick access and you don't mind using some more space, then you maintain another map that gets stored as value, key. In your case, you would need to handle the duplicate values (that you will be storing as keys).

Not a great idea but definitely an option.

score 0 · Answer 5 · answered Nov 02 '12 at 21:02

A map is meant for efficient lookup of keys. Lookup based on values is not efficient, and you basically have to iterate through the map, extracting matches yourself:

for(map<A,B>::iterator i = m.begin(); i != m.end(); i++)
    if(i->second == foo)
        you_found_a_match();

If you intend to do this often, you can build up a multimap mapping the other way, so you can efficiently perform a value-based lookup:

multimap<B,A> reverse;
for(map<A,B>::iterator i = m.begin(); i != m.end(); i++)
    reverse.insert(pair<B,A>(i->second,i->first));

You can now easily find the keys with a given value value:

matches = reverse.equal_range(value);
for(multimap<B,A>::iterator i = matches.first; i != matches.second; i++)
    A & key = i->second;

If these maps aren't going to grow continuously, it may be more efficient to simply maintain a vector > instead, define a comparator for it based on the value, and use equal_range on that instead.

Get all the keys which matches a query in a map

5 Answers5