c++ - que - wcag

mapa complejo encontrar operación

Question

Quiero hacer lo siguiente:
Defina un mapa entre una cadena y cualquier tipo de objeto (puede ser una lista, un entero, cualquier cosa).
Las claves del mapa pueden ser las siguientes (los valores son, una vez más, no importantes):
"AAA / 123" ==> 1
"AAA / " ==> 2
"BBB / " ==> 3
"CCC / *" ==> 4
"CCC / 123" ==> 5
Ahora, el truco es que quiero encontrar los valores correctos con las siguientes cadenas:
"AAA / 123" debería dar 1.
"AAA / 111" debería dar 2.
"CCC / 111" debería dar 4.
"CCC / 123" debería dar 5.
"BBB / AAA / 123" debería dar 3.

¿Alguna idea de cómo hago eso con C ++ y posiblemente con STL / boost?

Answer 1

¿Qué tal usar dos mapas?

std::map<std::string, std::map<int, object> >

Si quieres buscar aaa / * lo haces

a.find("aaa") => you get an iterator to the map with all "aaa" prefix

Si quieres buscar aaa / 123 lo haces

a.find("aaa")->find(123) 

(por supuesto, DEBE validar que no se termina, esto es solo por el ejemplo)

Answer 2

A partir de su requerimiento, parece que realmente no desea la estructura de datos del mapa, pero puede establecerse o algo muy simple.

Creo que una estructura como este std :: map podría ayudarte. Boost :: any podrá almacenar cualquier cosa, pero es necesario que sepa que el tipo de valor es leerlo.

La clave es cadena y, por lo tanto, también puede ser una expresión regular. Con esta estructura necesitarás dos algoritmos de pase como:

std::map<std::string, boost::any> _map;
if (_map.find(key) != _map.end)
{
   // exact match
}
else
{
   // Have to do sequential regex (use boost::regex) matching
}

Dado que la evaluación de expresiones regulares en el tiempo de ejecución puede ser costosa, puede usar std :: vector>, de modo que para los patrones de expresiones regulares almacene expresiones regulares compiladas en uno de los campos.

Puede ser útil dar más información acerca de lo que desea lograr, ya que puede ayudar a decidir sobre la estructura de datos correcta y el algoritmo de búsqueda.

Answer 3

Aquí hay una variante de la respuesta literal (que de alguna manera se eliminó de la lista de respuestas) que podría funcionar dado que se eliminó el "*":

template<typename Map> typename Map::const_iterator
find_prefix(Map const& map, typename Map::key_type const& key)
{
    typename Map::const_iterator it = map.upper_bound(key);
    while (it != map.begin())
    {
        --it;
        if(key.substr(0, it->first.size()) == it->first)
            return it;
    }

    return map.end(); // map contains no prefix
}

Olvidé agregar el código que lo usa:

std::map<std::string, int> smap;
smap["AAA/"] = 1;
smap["BBB/"] = 2;
smap["AAA/AA"] = 3;

find_prefix(smap, "AAA/AB")->second; // ==> 1
find_prefix(smap, "AAA/AA")->second; // ==> 3
find_prefix(smap, "BBB/AB")->second; // ==> 2
find_prefix(smap, "CCC/AB"); // ==> smap.end()

algún comentario (y gracias a litb)?