Проверка значения существует в std :: map - C ++ - PullRequest
Новая
       21

Проверка значения существует в std :: map - C ++

30 голосов
/ 11 февраля 2009

Я знаю, find метод находит указанный ключ в std :: map и возвращает итератор для элемента. Есть ли способ найти значение и получить итератор для элемента? Что мне нужно сделать, это проверить, что указанное значение существует в std :: map. Я сделал это путем зацикливания всех элементов на карте и сравнения. Но я хотел знать, есть ли лучший подход к этому.

Вот что я написал 

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

Редактировать

Как насчет использования другой карты для хранения значения и комбинации клавиш? Так я могу позвонить найти по нему? find () в std :: map выполняет последовательный поиск?

Спасибо

Ответы [ 10 ]

20 голосов
/ 11 февраля 2009

Вы можете использовать boost :: multi_index для создания двунаправленной карты - вы можете использовать любое значение пары в качестве ключа для быстрого поиска.

16 голосов
/ 25 мая 2009

Если у вас есть доступ к превосходной библиотеке boost , тогда вы должны использовать boost :: multi_index , чтобы создать двунаправленную карту , как говорит Марк. В отличие от std :: map это позволяет вам искать либо по ключу, либо по значению.

Если у вас есть только STL для передачи, следующий код сделает свое дело (шаблон для работы с любым видом карты, где mapped_type поддерживает 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;
    }
}
15 голосов
/ 11 февраля 2009

Как насчет использования другой карты внутри, которая хранит значение, комбинацию клавиш. Так я могу позвонить найти по нему?

Да: ведение двух карт: одна карта использует один тип ключа, а другая - другой.

Является ли find () в std :: map последовательным поиском?

Нет, это двоичный поиск отсортированного дерева: его скорость равна O (log (n)).

6 голосов
/ 11 февраля 2009

Посмотрите на двунаправленные карты повышения: http://www.boost.org/doc/libs/1_38_0/libs/bimap/doc/html/index.html

Позволяет обоим значениям действовать как ключи.

В противном случае итерация - это путь.

4 голосов
/ 13 июля 2011

попробуйте эту функцию: 

template <class Map, class Val> typename Map::const_iterator MapSearchByValue(const Map & SearchMap, const Val & SearchVal)
{
    Map::const_iterator iRet = SearchMap.end();
    for (Map::const_iterator iTer = SearchMap.begin(); iTer != SearchMap.end(); iTer ++)
    {
        if (iTer->second == SearchVal)
        {
            iRet = iTer;
            break;
        }
    }
    return iRet;
}

я думаю, что это полезно

2 голосов
/ 11 февраля 2009

Нет, вы должны перебрать std :: map и проверить все значения вручную. В зависимости от того, что вы хотите сделать, вы можете обернуть std :: map в простой класс, который также кэширует все значения, которые вставляются в карту, во что-то, что легко доступно для поиска и не допускает дублирования, как std ::задавать. Не наследуйте от std :: map (у него нет виртуального деструктора!), Но оберните его так, чтобы вы могли сделать что-то вроде этого: 

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

В качестве альтернативы использованию собственной карты можно использовать двунаправленную карту Boost, которую легко найти в сообщениях ниже или в Google.

Это действительно зависит от того, что вы хотите сделать, как часто вы хотите это делать, и от того, насколько сложно катить свой собственный небольшой класс-обертку по сравнению с установкой и использованием Boost. Я люблю Boost, так что это хороший путь, но есть кое-что приятное и полное в создании собственного класса-обёртки. У вас есть преимущество в непосредственном понимании сложности операций, и вам может не потребоваться полное обратное сопоставление значений => ключей, предоставляемое двунаправленной картой Boost.

1 голос
/ 08 марта 2017

То, что вы запрашиваете, это именно то, что std :: find делает (не функция-член) 

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );
0 голосов
/ 16 ноября 2018

Я добавляю этот ответ, если кто-то приходит сюда и ищет c ++ 11 и выше .. 

    //DECLARE A MAP
    std::map<int, int> testmap;

    //SAMPLE DATA
    testmap.insert(std::make_pair(1, 10));
    testmap.insert(std::make_pair(2, 20));
    testmap.insert(std::make_pair(3, 30));
    testmap.insert(std::make_pair(4, 20));

    //ELEMENTS WITH VALUE TO BE FOUND
    int value = 20;

    //RESULTS
    std::map<int, int> valuesMatching;

    //ONE STEP TO FIND ALL MATCHING MAP ELEMENTS
    std::copy_if(testmap.begin(), testmap.end(), std::inserter(valuesMatching, valuesMatching.end()), [value](const auto& v) {return v.second == value; });
0 голосов
/ 06 апреля 2017

Не самый лучший вариант, но может быть полезен в тех случаях, когда пользователь назначает значение по умолчанию, например 0 или NULL, при инициализации. 

Ex.
< int , string >
< string , int > 
< string , string > 

consider < string , string >
mymap["1st"]="first";
mymap["second"]="";
for (std::map<string,string>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
{
       if ( it->second =="" ) 
            continue;
}
0 голосов
/ 01 декабря 2010

Возможно, я не до конца понимаю, чего вы пытаетесь достичь. Но чтобы просто проверить, содержит ли карта значение, я думаю, вы можете использовать встроенный std::map find. 

bool ContainsValue(Type_ value)
{
    return (internalMap.find(value) != internalMap.end());
}
...