CODEWITHSUNDEEP
c++stldictionary
neel
neel

Reputation: 9061

Get all the keys which matches a query in a map

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++.

Upvotes: 0

Views: 3382

Answers (5)

James
James

Reputation: 9278

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);
        }
    });
}

Upvotes: 2

amaurea
amaurea

Reputation: 5067

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.

Upvotes: 0

Vaibhav Desai
Vaibhav Desai

Reputation: 2728

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.

Upvotes: 1

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153840

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
}

Upvotes: 1

Nahuel Fouilleul
Nahuel Fouilleul

Reputation: 19315

The only way is to iterate over map.

this link may be useful: Reverse map lookup

Upvotes: 1

Related Questions