c++ - example - std:: mapea coincidencia parcial para la clave

set c++

Question

Tengo un std :: map 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 de impulso!

Answer 1

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 las subcadenas que no son de prefijo: en el caso general, buscar un mapa no es muy diferente de buscar en otros contenedores.

Answer 2

No puede buscar de forma eficiente la subcadena, pero puede buscar el 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

Answer 3

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) el operator<() para ordenar claves y 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 el operator<() comparación con una subcadena, tenga en cuenta que esto también afectará la decisión de si un elemento nuevo para insertar sería un duplicado. En otras palabras, dicho mapa solo tendrá elementos que no sean subcadenas entre sí.

La búsqueda O (n) prácticamente significa que 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 de El par es una subcadena de la primera.

Answer 4

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