std::find_if , std::binary_function for searching std::map by value

Question

My std::map has pair of 'unique key' and 'unique value'. I usually find a key for a value and find a value for a key as well as. I already know the method which by using std::find_if + lambda, however I want to know if there are any better ways.

After searching, I've found this article and I've learned how to use `std::binary_function'. Using both approach, I've checked 'elapsed time'. This is my code.

typedef int                                 USER_ID;
typedef std::string                         USER_NICK_NAME;
typedef std::map<USER_ID, USER_NICK_NAME>   USER_MAP;

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 _tmain(int argc, _TCHAR* argv[])
{
  USER_MAP user_map;
  string nick_prefix = "test";

  //make test map
  for (int i = 0; i < 100000; i++)
  {
    std::ostringstream stream;
    stream << i;
    user_map.insert(USER_MAP::value_type(i, nick_prefix + stream.str()));
  }

  const USER_NICK_NAME nick_name = "test99999";
  clock_t t;

  //Method 1 : using find_if + lambda
  cout << "Method 1 : using find_if + lambda" << endl;
  t = clock();
  auto it = std::find_if(user_map.begin(), user_map.end(), [&](const USER_MAP::value_type& user)
  {
    return nick_name == user.second;
  });
  if (it != user_map.end())
  {
    cout << "found nickname " << nick_name.c_str() << ", at index " << it->first << endl;
  }
  t = clock() - t;
  cout << "elapsed " << ((float)t)/CLOCKS_PER_SEC << " seconds" << endl;

  cout << endl << endl;

  //Method 2 : using find_if + binary_function
  cout << "Method 2 : using using find_if + binary_function" << endl;
  t = clock();
  it = std::find_if(user_map.begin(), user_map.end(), std::bind2nd(map_data_compare<USER_MAP>(), nick_name));
  if (it != user_map.end())
  {
    cout << "found nickname " << nick_name.c_str() << ", at index " << it->first << endl;
  }
  t = clock() - t;
  cout << "elapsed " << ((float)t)/CLOCKS_PER_SEC << " seconds" << endl;

  return 0;
}

In my machine, Method 1 is always faster than Method2. This is test result console.

So, My question is,

1. In my situation(I mean searching map by value), find_if + lambda is the best way? (Unfortunately, I can't use boost library.)
2. When I use std::binary_function?
3. I know that in C++ 11, `std::binary_function' has bee deprecated. Could I know the reason?

Thank you for your time to view this thread and for trying to help.

Answer 1

Assuming you have the C++1y feature of transparent comparisons, you can create a std::set of std::map::iterator that is sorted by the .second field, and make the comparator transparent so you can do lookups in it by the type of the .second field.

But that is unlikely.

If you do not have this, and you can make your value field (reasonably) cheap to copy, you can make a std::map or std::unordered_map from the value field to iterators into the std::map. This assumes you need both lookup and order in the main map.

If you do not need order, stop using map:

typedef std::unordered_map< int, std::string > main_map;
typedef std::unordered_map< std::string, int > backwards_map;

then wrap the above in some boilerplate to keep the two in sync.

Note that unordered_map iterators are non-persistent. std::map iterators are highly persistent. So the backwards map is different for the double-unordered case.

As for binary_function and bind2nd, it is deprecated.

Answer 2

In my situation(I mean searching map by value), find_if + lambda is the best way?

It's certainly the neatest way (assuming you can't use a second map, or perhaps a boost-style multi-index map, to find values quickly). In principle, using an equivalent functor and/or bind shouldn't be significantly slower, the only difference here being that nick_name is captured by value rather than reference; perhaps you haven't enabled optimisations, or perhaps your compiler doesn't optimise bind2nd as well as one might hope.

When I use std::binary_function?

Historically, you'd inherit from it to inject type aliases (first_argument_type, second_argument_type and result_type) into your functor, if you didn't feel like defining them yourself. These were sometimes required, for example when using adapters like bind2nd (which are also deprecated) to create a new functor based on your one.

I know that in C++ 11, std::binary_function has bee deprecated. Could I know the reason?

The types it defines are neither necessary or sufficient for the new-style variadic adapters like bind, so it no longer does anything useful.