find() problems

Question

I've got an error while using find() function. Here is the code:

#include <iostream>
#include <map>

#define N 100000

using namespace std;

int main (int argc, char * const argv[]) {

    map<int,int> m;

    for (int i=0; i<N; i++) m[i]=i;

    find(m.begin(), m.end(), 5);

    return 0;
}

I'm getting an compiller error:

error: no match for 'operator==' in '__first. __gnu_debug::_Safe_iterator<_Iterator, _Sequence>::operator* [with _Iterator = std::_Rb_tree_iterator<std::pair<const int, int> >, _Sequence = __gnu_debug_def::map<int, int, std::less<int>, std::allocator<std::pair<const int, int> > >]() == __val'

Including 'algorithm' nothing changes. Compiling in VS2008 shows similar error.

I know about m.find(), but I realy need to use find() too.

Thanks a lot for your assistance!

P.S. Actualy, the task is to compare speed of m.find(5) and find(m.begin(), m.end(), 5), so I need to make both of them work properly.

Answer 1

begin() and end() on all STL containers provide access to elements of those collections. Type of those elements is known as value_type of the container. For std::map<Key, Value>, its value_type is std::pair<Key, Value>. Therefore, your find function is trying to find a pair<int, int> which is equal to 5. Since there's no operator== defined to compare pair<int, int> and int, you get the error.

The correct way to do this (so long as you want to avoid member find()) is to use std::find_if:

template <class First>
struct first_equal
{
   const First value;

   first_equal(const First& value)
        : value(value)
   {
   }

   template <class Second>
   bool operator() (const std::pair<First, Second>& pair) const
   {
        return pair.first == value;
   }
};

...

find_if(m.begin(), m.end(), first_equal<int>(5));

You could also overload operator== for pair and int to do what you want, but it's a very hackish way (because it will affect all your code, and because such a comparison has no meaning in general).