Publi

Cómo buscar en un vector o una lista de mapas en C++

photo-1433357094834-cdeebc8e9dce_r

Una de las cosas que hacen mágico C++ es que podemos crear estructuras realmente grandes valiéndonos de las clases y estructuras de que disponemos. Vale, en otros lenguajes también podemos hacerlo, pero en C++ parece más grande aún dada la literatura de los tipos. Bueno, en Java podemos llegar a tener mucha más literatura, pero hoy el tema es C++.

¡ Una lista de mapas ! ¿Para qué?

Bueno, el primer paso es hacer un ejemplo práctico para el que una lista de mapas puede ser útil y, por ejemplo, puede ser para almacenar información estructurada. Por ejemplo, tengo que pasar una serie de tests a un sistema, cada test tiene un nombre interno, un título, un usuario responsable, un contenido y datos adicionales. Entonces cada test se describirá en un mapa de la siguiente manera:

1
std::map<std::string, std::string> test = { { "name", "divisionPorCero" }, { "title", "División por cero" }, { "user", "poetabinario" }, { "content", "{{x}}/0" }, { "severity", "high" } };

Eso sí, en nuestro sistema puede haber muchos tests, y estar definidos en tiempo de ejecución (imagina que lo miramos en un archivo de configuración, o lo descargamos de Internet…)

Otro ejemplo puede ser, el resultado de una consulta de base de datos, que nos ha devuelto un conjunto de filas y cada una contendrá un conjunto de claves y valores dependiendo de las columnas que existen en dicha tabla de nuestra base de datos.

O tal vez, una serie de redes sociales donde vamos a publicar nuestro último post, y para ello necesitamos saber unos datos básicos de cada una.

Lo más intuitivo

Lo dejo aquí como ejemplo anecdótico, porque es, creo yo, el que mejor se entiende, pero el que peor rendimiento da:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

template <typename K, typename V>
std::map<K, V> findMV(std::vector<std::map<K, V> > collection, K mykey, V myvalue)
{
  for (auto i : collection)
    {
      auto fi = i.find(mykey);
      if (fi == i.end())
    continue;
      if (fi->second == myvalue)
    return i;
    }
  return std::map<K,V>();
}

int main(int argc, char *argv[])
{
  std::vector<std::map<std::string, std::string> > mylist = {
    { { "network", "facebook" }, { "displayName", "Facebook" }, { "url", "https://facebook.com/" }, { "user", "gaspy" },     { "friends", "400" } },
    { { "network", "twitter" },  { "displayName", "Twitter" },  { "url", "https://twitter.com/" },  { "user", "gaspar_fm" }, { "followers", "500" } },
    { { "network", "github"},    { "displayName", "GitHub" },   { "url", "https://github.com/" },   { "user", "gasparfm" },  { "followers", "12" } },
    { { "network", "linkedin"},  { "displayName", "LinkedIn" }, { "url", "https://linkedin.com/" }, { "user", "gaspar-fernández-53756314" }, { "contacts", "150" } }
  };

  auto nw = findMV(mylist, (string)"network", (string)"github");

  for (auto i : nw)
    {
      cout << i.first << " = " << i.second<<endl;
    }

  return 0;
}

Dejo también el código eliminando las partes de C++11, queda un poco más feo, pero está bien si no dispones de un compilador actualizado:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

template <typename K, typename V>
std::map<K, V> findMV(std::vector<std::map<K, V> > collection, K mykey, V myvalue)
{
  for (typename std::vector<std::map<K, V> >::iterator i=collection.begin(); i!=collection.end(); ++i)
    {
      typename std::map<K, V>::iterator fi = i->find(mykey);
      if (fi == i->end())
    continue;
      if (fi->second == myvalue)
    return *i;
    }
  return std::map<K,V>();
}

int main(int argc, char *argv[])
{
  std::vector<std::map<std::string, std::string> > mylist;

  mylist.push_back(map<string, string>());
  mylist.push_back(map<string, string>());
  mylist.push_back(map<string, string>());
  mylist.push_back(map<string, string>());

  mylist[0]["network"] = "facebook";
  mylist[0]["displayName"] = "Facebook";
  mylist[0]["url"] = "https://facebook.com/";
  mylist[0]["user"] = "gaspy";
  mylist[0]["friends"] = "400";

  mylist[1]["network"] = "twitter";
  mylist[1]["displayName"] = "Twitter";
  mylist[1]["url"] = "https://twitter.com/";
  mylist[1]["user"] = "gaspar_fm";
  mylist[1]["followers"] = "500";

  mylist[2]["network"] = "github";
  mylist[2]["displayName"] = "GitHub";
  mylist[2]["url"] = "https://github.com/";
  mylist[2]["user"] = "gasparfm";
  mylist[2]["followers"] = "12";

  mylist[3]["network"] = "linkedin";
  mylist[3]["displayName"] = "LinkedIn";
  mylist[3]["url"] = "https://linkedin.com/";
  mylist[3]["user"] = "gaspar-fernández-53756314";
  mylist[3]["contacts"] = "150";

  map<string, string> nw = findMV(mylist, (string)"network", (string)"github");

  for (map<string, string>::iterator i= nw.begin(); i!=nw.end(); ++i)
    {
      cout << i->first << " = " << i->second<<endl;
    }

  return 0;
}

Bueno, la función que importa aquí es findMV() a la cual le pasamos un vector de mapas cuyo primer elemento es de tipo K y segundo de tipo V (en realidad, al usar el template da igual que los tipos sean string, o un string y un int, o incluso si metemos valores de tipo clase o struct.

El objetivo será buscar en todos los elementos de la lista, para cada elemento buscar la clave mykey en el mapa, y si existe, comparar su valor con myvalue, en el caso en el que coincidan, devolveremos el mapa actual. Podremos ganar mucho rendimiento si pasamos collection por referencia.

Usando std::find_if

La biblioteca algorithm es muy completa en estas cosas y tiene funciones muy rápidas para hacer muchas tareas, aunque no siempre son cómodas de usar. Para el resto de los ejemplos, sólo usaré C++ moderno. Aunque find_if() está disponible en versiones anteriores y podréis adaptar el código si es necesario.

Para realizar la búsqueda anterior bastaría con hacer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
  std::vector<std::map<std::string, std::string> > mylist = {
    { { "network", "facebook" }, { "displayName", "Facebook" }, { "url", "https://facebook.com/" }, { "user", "gaspy" },     { "friends", "400" } },
    { { "network", "twitter" },  { "displayName", "Twitter" },  { "url", "https://twitter.com/" },  { "user", "gaspar_fm" }, { "followers", "500" } },
    { { "network", "github"},    { "displayName", "GitHub" },   { "url", "https://github.com/" },   { "user", "gasparfm" },  { "followers", "12" } },
    { { "network", "linkedin"},  { "displayName", "LinkedIn" }, { "url", "https://linkedin.com/" }, { "user", "gaspar-fernández-53756314" }, { "contacts", "150" } }
  };
  auto found = std::find_if(mylist.begin(), mylist.end(), [] (std::map<std::string, std::string> current) {
      return (current["network"] == "facebook");
    });

  cout << " ------------------\n";
  for (auto i : *found)
    {
      cout << i.first << " = " << i.second<<endl;
    }

  return 0;
}

Es decir, a find_if() le pasamos los iteradores de inicio y fin y una función callback que usaremos para hacer la comparación. Es este caso, podemos utilizar una lambda. La salvedad ahora es que los elementos de clave y valor, tenemos que ponerlos dentro de la lambda, en muchos casos, no resultará incómodo, pero en otras ocasiones puede que sí. Por tanto, vamos a completar la función findMV() con el nuevo método de uso (find_if()).

Tal y como hace find_if(), vamos a devolver un iterador apuntando al elemento del vector, por lo que en un entorno real debemos comprobar antes de utilizar el elemento que éste existe (en el primer ejemplo, si el elemento no existía devolvíamos un mapa vacío). Para comprobar dicha existencia bastaría con hacer (y no estoy descubriendo nada):

1
2
3
4
  if (found == mylist.end())
     cout << "NO EXISTE" << endl;
  else
     cout << "EXISTE" << endl;

Aquí dejo la función findMV definitiva:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename K, typename V>
typename std::vector< std::map <K, V> >::iterator findMV(std::vector<std::map<K, V> > &collection, K mykey, V myvalue)
{
  auto found = std::find_if(collection.begin(), collection.end(), [mykey, myvalue] (std::map<std::string, std::string> current) {
      auto it = current.find(mykey);
      if (it == current.end())
    return false;
     
      return (it->second == myvalue);
    });

  return found;
}

Ahora, como en el primer ejemplo podríamos hacer:

1
  auto nw = findMV(mylist, (string)"network", (string)"linkedin");

Y, cuidado, que nw, como ya dije antes devolverá un iterador, que podemos aprovechar también para modificar el elemento de la lista.

Varios resultados de búsqueda

Pero las búsquedas, nunca son sencillas, y puede que, en ocasiones, necesitemos devolver varios resultados. Este no es el mejor ejemplo, al tratarse de un vector de mapas de cadenas de caracteres, pero… y si queremos sacar las redes sociales con más de 200 amigos/contactos/seguidores?
Podemos hacerlo de forma sencilla de la siguiente manera:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
  std::vector<std::map<std::string, std::string> > mylist = {
    { { "network", "facebook" }, { "displayName", "Facebook" }, { "url", "https://facebook.com/" }, { "user", "gaspy" },     { "friends", "400" } },
    { { "network", "twitter" },  { "displayName", "Twitter" },  { "url", "https://twitter.com/" },  { "user", "gaspar_fm" }, { "followers", "500" } },
    { { "network", "github"},    { "displayName", "GitHub" },   { "url", "https://github.com/" },   { "user", "gasparfm" },  { "followers", "12" } },
    { { "network", "linkedin"},  { "displayName", "LinkedIn" }, { "url", "https://linkedin.com/" }, { "user", "gaspar-fernández-53756314" }, { "contacts", "150" } }
  };

  std::vector<std::map<std::string, std::string> > result(mylist.size());

  auto nw = std::copy_if(mylist.begin(), mylist.end(), result.begin(), [] (std::map<std::string, std::string> current) {
      auto people = current.find("friends");
      if (people == current.end())
    people = current.find("followers");
      if (people == current.end())
    people = current.find("contacts");
      if (people == current.end())
    return false;       /* No tenemos amigos/seguidores/contactos */

      int peopleQty = std::stoi(people->second);
      return (peopleQty>200);
    });
  result.resize(std::distance(result.begin(), nw));

  for (auto ii : result)
    {
      for (auto i : ii)
    cout << i.first << " = " << i.second<<endl;
      cout << "--------" << endl;
    }

  return 0;
}

En lugar de find_if() utilizaremos copy_if(), ésta sí que está disponible sólo desde C++11. En este caso, siempre se recorrerá el vector por completo y se copiarán a otro vector de mapas resultante sólo aquellos elementos que cumplan la condición del callback. En este caso, al tener varias claves que designan la gente con la que tenemos contacto en las diferentes redes sociales, tenemos que incluir todos y cada uno de ellos (como son 3 mensajes diferentes, no nos complicaremos la vida más de lo necesario), luego, como los números vienen expresados como cadena de caracteres llamamos a std::stoi() para hacer la conversión y por último comparamos con el número que queremos.

El gran problema es que, al pasarle la lista donde queremos almacenar los resultados como un iterador, la propia lista tiene que tener previamente el tamaño necesario para almacenar los resultados, y por ello, cuando la declaramos decimos:

1
  std::vector<std::map<std::string, std::string> > result(mylist.size());

Le damos el tamaño de la lista, es decir, como máximo, esta lista de resultados, tendrá tantos elementos como la lista original. Aunque, nada más hacer la búsqueda, reducimos su tamaño al número de elementos que hemos ocupado, liberando así espacio en memoria.

Un apunte más

Aunque en el título dije que esto es para un vector de mapas, en realidad copy_if() y find_if() podemos utilizarlas con las estructuras que queramos, ya que internamente también usan templates, y, mientras la estructura a recorrer maneje iteradores y vayamos creando una función callback adecuada todo funcionará a las mil maravillas.

Podéis probar el rendimiento de estas funciones haciendo un bucle de búsquedas, por ejemplo, realizar 1000000 (un millón) de búsquedas en un programa y ejecutarlo con la orden time, por ejemplo:

$ time ./vecmap
displayName = GitHub
followers = 12
network = github
url = https://github.com/
user = gasparfm

real 0m2.483s
user 0m2.482s
sys 0m0.004s

Foto: Joey Sforza

También podría interesarte....

Only 1 comment left Ir a comentario

  1. Pingback: Cómo buscar en un vector o una lista de mapas en C++ | PlanetaLibre /

Leave a Reply