Coincidencia parcial de la clave de un std::map

Yo tengo un std::map y quiero buscar una clave usando una subcadena. Por ejemplo, tengo el siguiente código:

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

Ahora, quiero buscar la posición que contiene la subcadena “Marl” y no “Marlon”, si “Marla” está almacenada en el mapa. Quiero encontrar algo que comience con “Marl”. Necesito encontrar como máximo una posición. es posible? ¿Si es así, cómo?

¡No quiero usar ninguna biblioteca de Boost!

no puedes eficientemente buscar subcadena, pero puede 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

Cuando su subcadena es una prefijo como en tu ejemplo, puedes usar lower_bound 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.

Me gustaría ampliar la respuesta de Sergey proporcionando una solución completa usando map::lower_bound(). Como se menciona en los comentarios sobre esa respuesta, debe verificar si lower_bound() devoluciones tMap.end(). De lo contrario, también debe verificar si la clave encontrada realmente tiene el prefijo de la cadena de búsqueda. Esto último se puede comprobar, por ejemplo, utilizando string::compare(). Como resultado, mi solución C++ 11 tiene el siguiente aspecto:

std::map<std::string, std::string> myMap{
    {"John", "AA"}, {"Mary", "BBB"}, {"Mother", "A"}, {"Marlon", "C"}, {"Marla", "D"}
};
std::string prefix("Marl");

auto it = myMap.lower_bound(prefix);
if (it != std::end(myMap) && it->first.compare(0, prefix.size(), prefix) == 0)
    std::cout << it->first << ": " << it->second << std::endl;

Producción:

Marla: D.

Sin embargo, si desea encontrar todas las claves en su mapa que tienen el prefijo con la cadena de búsqueda, puede usar el siguiente bucle:

for (auto it = myMap.lower_bound(prefix); it != std::end(myMap) && it->first.compare(0, prefix.size(), prefix) == 0; ++it)
    std::cout << it->first << ": " << it->second << std::endl;

Producción:

Marla: D.
Marlón: C.

Código en Ideone

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

Si crea un nuevo mapa en un tipo de clave especial que tiene operator<() compare sobre la base de una subcadena, tenga en cuenta que esto también afectará la decisión de si un nuevo elemento 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 usas std::find() sobre el mapa, con un predicado personalizado que toma un std::pair<std::string,std::string> y devuelve verdadero si el segundo elemento del par es una subcadena del primero.

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