Checking value exist in a std::map - C++

Question

I know find method finds the supplied key in std::map and return an interator to the element. Is there anyway to find the value and get an iterator to the element? What I need to do is to check specified value exist in std::map. I have done this by looping all items in the map and comparing. But I wanted to know is there any better approach for this.

Here is what I have wrote

bool ContainsValue(Type_ value)
{
    bool found = false;
    Map_::iterator it = internalMap.begin(); // internalMap is std::map
    while(it != internalMap.end())
    {
     found = (it->second == value);
     if(found)
      break;
        ++it;
    }
    return found;
}

Edit

How about using another map internally which stores value,key combination. So I can call find on it? Is find() in std::map doing sequential search?

Thanks

Answer 1

No, you have to loop over the std::map and check all values manually. Depending on what you want to do, you could wrap the std::map in a simple class that also caches all of the values that are inserted into the map in something that's easily search-able and doesn't allow duplicates, like a std::set. Don't inherit from the std::map (it doesn't have a virtual destructor!), but wrap it so that you can do something like this:

WrappedMap my_map< std::string, double >;
my_map[ "key" ] = 99.0;
std::set< double > values = my_map.values(); // should give back a set with only 99.0 in it

An alternative to rolling your own would be to use the Boost bidirectional map, which is easily found in the posts below or by Google.

It really depends on what you want to do, how often you want to do it, and how hard it is to roll your own little wrapper class versus installing and using Boost. I love Boost, so that's a good way to go - but there's something nice and complete about making your own wrapper class. You have the advantage of understanding directly the complexity of operations, and you may not need the full reverse mapping of values => keys that's provided by the Boost bidirectional map.

Answer 2

You can use boost::multi_index to create a bidirectional map - you can use either value of the pair as a key to do a quick lookup.

Answer 3

Look into boost's bidirectional maps: http://www.boost.org/doc/libs/1_38_0/libs/bimap/doc/html/index.html

It lets both values act like a key.

Otherwise, iteration is the way to go.

Answer 4

How about using another map internally which stores value,key combination. So I can call find on it?

Yes: maintain two maps, with one map using one type of key and the other using the other.

Is find() in std::map doing sequential search?

No it's a binary search of a sorted tree: its speed is O(log(n)).

Answer 5

If you have access to the excellent boost library then you should be using boost::multi_index to create bidirectional map as Mark says. Unlike a std::map this allows you to look up by either the key or the value.

If you only have the STL to hand the following code will do the trick (templated to work with any kind of map where the mapped_type supports operator==):

#include <map>
#include <string>
#include <algorithm>
#include <iostream>
#include <cassert>

template<class T>
struct map_data_compare : public std::binary_function<typename T::value_type, 
                                                      typename T::mapped_type, 
                                                      bool>
{
public:
    bool operator() (typename T::value_type &pair, 
                     typename T::mapped_type i) const
    {
        return pair.second == i;
    }
};


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

    mapType map;

    map["a"] = 1;
    map["b"] = 2;
    map["c"] = 3;
    map["d"] = 4;
    map["e"] = 5;

    const int value = 3;

    std::map<std::string, int>::iterator it = std::find_if( map.begin(), map.end(), std::bind2nd(map_data_compare<mapType>(), value) );

    if ( it != map.end() )
    {
        assert( value == it->second);
        std::cout << "Found index:" << it->first << " for value:" << it->second << std::endl;
    }
    else
    {
        std::cout << "Did not find index for value:" << value << std::endl;
    }
}