Search for specific value in std::map

Question

Possible Duplicates:
Checking value exist in a std::map - C++
How to traverse a stl map/vector/list/etc?

Hello,

Is it possible to search for specific value in std::map, not knowing the key? I know I could iterate over whole map, and compare values, but it is possible to do using a function from std algorithms?

For `std::map`, you'll have to iterate. Otherwise, use `boost::bimap` - http://stackoverflow.com/questions/535317/checking-value-exist-in-a-stdmap-c — wkl, Dec 06 '10 at 15:25

score 15 · Answer 1 · answered Dec 06 '10 at 15:29

15

Well, you could use std::find_if :

int main()
{
    typedef std::map<int, std::string> my_map;

    my_map m;
    m.insert(std::make_pair(0, "zero"));
    m.insert(std::make_pair(1, "one"));
    m.insert(std::make_pair(2, "two"));

    const std::string s("one");
    const my_map::const_iterator it = std::find_if(
        m.begin(), m.end(), boost::bind(&my_map::value_type::second, _1) == s
    );
}

But that's just slightly better than a hand-crafted loop : it's still O(n).

answered Dec 06 '10 at 15:29

icecrime

74,451
13
99
111

Great idea with bind! – Anton K Jun 18 '15 at 23:47
1

I needed some time to understand the usage of boost::bind. Here are some pointers if anyone needs them: [Binding Member Variables](http://www.boost.org/doc/libs/1_65_1/libs/phoenix/doc/html/phoenix/modules/bind/binding_member_variables.html) and [Overloaded Operators](http://www.boost.org/doc/libs/1_65_1/libs/bind/doc/html/bind.html#bind.purpose.overloaded_operators_new_in_boos) – guini Nov 29 '17 at 14:08

score 8 · Answer 2 · answered Dec 06 '10 at 15:27

8

You could use Boost.Bimap if you want to index on values as well as keys. Without this or similar, this will have to be done by brute force (=> scan the map by hand).

Boost.Bimap is a bidirectional maps library for C++. With Boost.Bimap you can create associative containers in which both types can be used as key.

answered Dec 06 '10 at 15:27

Steve Townsend

53,498
9
91
140

+1. Also, you may use two opposed STL maps, if it is not permissible to use Boost in your code. – Stas Dec 06 '10 at 15:47
1

@Stas - true, but this makes for more work - my usual response to people who are 'not allowed to use Boost' is to download the headers anyway and abstract out the code you need. – Steve Townsend Dec 06 '10 at 15:49

score 4 · Accepted Answer · answered Dec 06 '10 at 15:30

4

Will this help? STL find_if

You need to have some sort of predicate, either a function pointer or an object with operator() implemented. Said predicate should take just one parameter.

answered Dec 06 '10 at 15:30

Platinum Azure

45,269
12
110
134

score 2 · Answer 4 · answered Dec 06 '10 at 15:27

2

There are (awkward) ways to do this using standard functions (e.g., std::find_if), but these still involve iterating over the whole map. Boost.Bimap will provide efficient indexing in both directions, and you can go even further with Boost.Multi-Index.

answered Dec 06 '10 at 15:27

Marcelo Cantos

181,030
38
327
365

Search for specific value in std::map

4 Answers4

Linked