std::map partial match for the key

Question

std::map partial match for the key

Tengo un mapa std::y quiero buscar una clave usando una subcadena. Por ejemplo

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

Quiero buscar la posición que contiene la subcadena "Marl" y no "Marlon". Es posible? ¿Cómo?

EDITAR: no hay bibliotecas boost!

22

c++stdmap

Author: cateof, 2012-02-19

Source

4 answers

Cuando su subcadena es un prefijo como en su ejemplo, puede usar lower_bound para buscar "Marl".

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

Esto no funciona para subcadenas sin prefijo: en el caso general, buscar en un mapa no es muy diferente de buscar en otros contenedores.

8

Author: dasblinkenlight,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-02-19 14:15:56

Para buscar una subcadena de una clave en un mapa, no tiene más remedio que usar un nuevo mapa en un tipo especial de clave o buscar su mapa en O(n). std::map usa (por defecto) operator<() para ordenar las claves y para buscar, y esa función de comparación para std::string es una comparación lexicográfica simple.

Si crea un nuevo mapa en un tipo de clave especial que tiene operator<() comparar sobre la base de una subcadena, tenga en cuenta que esto también afectará la decisión de si se debe insertar un nuevo elemento sería un duplicado. En otras palabras, tal mapa solo tendrá elementos que no sean subcadenas entre sí.

La búsqueda O(n) prácticamente significa que se usa std::find() sobre el mapa, con un predicado personalizado que toma un std::pair<std::string,std::string> y devuelve true si el segundo elemento del par es una subcadena del primero.

2

Author: wilhelmtell,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-02-19 14:18:16

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");

1

Author: Armen Tsirunyan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-02-19 14:05:42

score 22 · Accepted Answer

No puedes de manera eficiente buscar subcadena, pero puedes para prefijo :

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

Esto imprime:

Marl    Marlon, C
Mo      Mother, A
ther
Mad
Mom
Perr
Jo      John, AA