std :: map частичное совпадение для ключа - PullRequest
Новая
       3

std :: map частичное совпадение для ключа

22 голосов
/ 19 февраля 2012

У меня есть std :: map, и я хочу найти ключ, используя подстроку.Например, 

#include <iostream>
#include <map>
#include <string>
using namespace std;

typedef std::map<std::string, std::string> TStrStrMap;
typedef std::pair<std::string, std::string> TStrStrPair;

int main(int argc, char *argv[])
{
        TStrStrMap tMap;

        tMap.insert(TStrStrPair("John", "AA"));
        tMap.insert(TStrStrPair("Mary", "BBB"));
        tMap.insert(TStrStrPair("Mother", "A"));
        tMap.insert(TStrStrPair("Marlon", "C"));


        return 0;
}

Я хочу найти позицию, которая содержит подстроку "Marl", а не "Marlon"Является ли это возможным?Как?

РЕДАКТИРОВАТЬ: нет буст библиотеки!

Ответы [ 4 ]

22 голосов
/ 19 февраля 2012

Вы не можете эффективно искать подстроку, но вы можете ввести префикс : 

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

typedef map<string, string> TStrStrMap;
typedef pair<string, string> TStrStrPair;

TStrStrMap::const_iterator FindPrefix(const TStrStrMap& map, const string& search_for) {
    TStrStrMap::const_iterator i = map.lower_bound(search_for);
    if (i != map.end()) {
        const string& key = i->first;
        if (key.compare(0, search_for.size(), search_for) == 0) // Really a prefix?
            return i;
    }
    return map.end();
}

void Test(const TStrStrMap& map, const string& search_for) {
    cout << search_for;
    auto i = FindPrefix(map, search_for);
    if (i != map.end())
        cout << '\t' << i->first << ", " << i->second;
    cout << endl;
}

int main(int argc, char *argv[])
{
    TStrStrMap tMap;

    tMap.insert(TStrStrPair("John", "AA"));
    tMap.insert(TStrStrPair("Mary", "BBB"));
    tMap.insert(TStrStrPair("Mother", "A"));
    tMap.insert(TStrStrPair("Marlon", "C"));

    Test(tMap, "Marl");
    Test(tMap, "Mo");
    Test(tMap, "ther");
    Test(tMap, "Mad");
    Test(tMap, "Mom");
    Test(tMap, "Perr");
    Test(tMap, "Jo");

    return 0;
}

Это печатает: 

Marl    Marlon, C
Mo      Mother, A
ther
Mad
Mom
Perr
Jo      John, AA
8 голосов
/ 19 февраля 2012

Когда ваша подстрока имеет префикс , как в вашем примере, вы можете использовать lower_bound для поиска "Marl". 

    map<string,string>::const_iterator m = tMap.lower_bound("Marl");
    cerr << (*m).second << endl;

Это делаетне работает для подстрок без префиксов: в общем случае поиск по карте мало чем отличается от поиска в других контейнерах.

2 голосов
/ 19 февраля 2012

Чтобы найти подстроку ключа на карте, у вас нет выбора, кроме как использовать новую карту для ключа специального типа или выполнить поиск по карте в O (n). std::map использует (по умолчанию) operator<() для упорядочения ключей и поиска, и эта функция сравнения для std::string представляет собой простое лексикографическое сравнение.

Если вы создаете новую карту для специального типа ключа с operator<() сравнением на основе подстроки, учтите, что это также повлияет на решение о том, будет ли новый элемент для вставки дубликатом. Другими словами, такая карта будет иметь только элементы, которые не являются подстроками друг друга.

Поиск O (n) практически означает, что вы используете std::find() над картой с пользовательским предикатом, который принимает std::pair<std::string,std::string> и возвращает true, если второй элемент пары является подстрокой первого.

1 голос
/ 19 февраля 2012 
typedef TStrStrMap::value_type map_value_type;

struct key_contains_substring
   : std::binary_function<map_value_type, std::string, bool>
{
    bool operator()(const map_value_type& map_value, const std::string& substr)
    {
         return std::search(map_value.first.begin(), map_value.first.end(),
                    substr.begin(), substr.end() != map_value.first.end());  
    }
};

...


TStrStrMap::const_iterator it = std::find_if(tMap.begin(), tMap.end(), 
        std::bind2nd(key_contains_substring(), "Marl");
...