std :: find_if, std :: binary_function для поиска std :: map по значению

Question

У моего std::map есть пара уникальных ключей и уникальное значение. Я обычно нахожу ключ для значения и нахожу значение для ключа, а также. Я уже знаю метод, который с помощью std::find_if + лямбда, однако я хочу знать, есть ли какие-нибудь лучшие способы.

После поиска я нашел this article, и я узнал, как использовать `std :: binary_function '. Используя оба подхода, я проверил «прошедшее время». Это мой код.

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

В моей машине, Метод 1 всегда быстрее, чем Method2. Это консоль результатов теста.

Итак, мой вопрос,

1. В моей ситуации (я имею в виду поиск карты по значению), find_if + лямбда является лучшим способом? (К сожалению, я не могу использовать библиотеку boost.)
2. Когда я использую std::binary_function?
3. Я знаю, что в C++ 11 `std :: binary_function 'устарел пчел. Могу ли я узнать причину?

Спасибо, что посмотрели эту тему и попытались помочь.

Answer 1

В моей ситуации (я имею в виду поиск карты по значению), find_if + lambda - лучший способ?

Это, безусловно, самый простой способ (если вы не можете использовать вторую карту, или, возможно, карту с несколькими индексами в ускоренном режиме, чтобы быстро находить значения). В принципе, использование эквивалентного функтора и/или bind не должно быть значительно медленнее, единственная разница заключается в том, что nick_name фиксируется по значению, а не по ссылке; возможно, вы не включили оптимизацию, или, возможно, ваш компилятор не оптимизирует bind2nd, а также можно надеяться.

Когда я использую std::binary_function?

Исторически, вы бы унаследовать от него вводить псевдонимы типа (first_argument_type, second_argument_type и result_type) в свой функтор, если вы не чувствуете, как определение их самостоятельно. Иногда это требовалось, например, при использовании адаптеров типа bind2nd (которые также устарели) для создания нового функтора на основе вашего.

Я знаю, что в C++ 11, std::binary_function пренебрегает пчелами. Могу ли я узнать причину?

Типы, которые он определяет, не являются необходимыми или достаточными для адаптеров нового типа, таких как bind, поэтому он больше ничего не делает.

Answer 2

Предполагая, что у вас есть 1y C++ функции прозрачных сравнений, вы можете создать std::set из std::map::iterator, который отсортирован по .second полю, и сделать компаратор прозрачным, так что вы можете сделать поиски в ней по типу .second поле.

Но это маловероятно.

Если у вас нет этого, и вы можете сделать ваше поле значения (разумно) дешево копировать, вы можете сделать std::map или std::unordered_map из поля значения для итераторов в std::map. Это предполагает, что вам нужен и поиск и заказать на главной карте.

Если вам не нужен порядок, прекратить использование map:

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

затем обернуть выше в некоторых шаблонного держать два синхронно.

Обратите внимание, что итераторы unordered_map не являются стойкими. std::map Итераторы очень стойкие. Таким образом, обратная карта отличается для случая с двойным unordered.

Что касается binary_function и bind2nd, он устарел.