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

Question

I know find method finds the supplied key in std::map and return an iterator 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

Solution 1

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.

Solution 2

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

Solution 3

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

Solution 4

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.

Solution 5

What you are requesting is precisely what std::find does (not the member function)

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

View more solutions