Aunque he visto varias preguntas al respecto, me sigue quedando dudas. He de decir que mis conocimientos de los contenedores de la STL son muy limitados. De hecho, sólo he usado std::list para otra cosa que no sean ejemplos.
A ver si soy capaz de exponer bien mi problema. Tengo un programa que representa un grafo por el método de lista de adyacencia. Cada nodo guarda un campo llamado Código, y nunca puede haber dos nodos con el mismo código en cada grafo. Cuando manejo el programa no hay problemas, insertar un nuevo nodo implica recorrer la lista para ver si ya hay un nodo con un código igual, de forma que si no existe hay que crearlo y enlazarlo, pero si existe sólo hay que enlazarlo donde corresponda. Esta es una operación costosa, pero que cuando se trata de insertar uno o unos pocos nodos, es imperceptible,
El problema me viene cuando he de leer un fichero con el formato estandar de intercambio, y este contiene alguna base de datos con unos 60.000 nodos y del orden de entre 3 y 5 relaciones por cada nodo. Abrir una base de datos se puede demorar más de 10 minutos, y entiendo que eso no es ni normal ni aceptable.
He hecho, como ya digo no tengo ni idea de usar contenedores que no sean listas, un programa (es muy malo pero me sirve para comprobar las diferencias de rendimiento) que me compara una búsqueda de un elemento en un std::list y en un std::map . Aunque he leído que la función clock() no es muy precisa, al menos me da resultados coherentes (en una lista de 10 m de int, me tarda 10 veces mas cuando el valor a buscar está al final que al principio, por ejemplo). La diferencia es tan abismal que entiendo que mi solución pasa por ahí. Al menos a la hora de leer los archivos con el formato estandar de intercambio.
Mi idea es implementar un std::map junto a la lista de adyacencia, cuya clave sea el código y cuyo valor sea el nodo. Algo como std::map<std::string, nodo>mapa, que inserte valores a la vez que inserto en la lista, y que cuando haya de buscar un código use el mapa.
En fin, y en resumidas cuentas, estas son mis preguntas:
- ¿Mantener una lista y un mapa funcionando en paralelo es una idea aceptable o es una idiotez mía?
- Para lo que quiero hacer, ¿existe otro contenedor más apropiado?
También pongo el código del programa que he hecho para evaluar los tiempos por si alguien ve alguna incoherencia (es un refrito de lo que ya hay por ahí):
#include <iostream>
#include <list>
#include <ctime>
#include <map>
using namespace std;
bool existe(const list<long unsigned int>&lista, long unsigned int valor);
bool existe(const std::map<std::string,long unsigned int> &mapa, std::string valor);
std::string numToString(long unsigned int num);
const long unsigned int total= 10000000;
const int multiplicador = 1000;
int main()
{
std::list<long unsigned int>lista;
std::map<std::string,long unsigned int> mapa;
//lista de int
for (long unsigned int i=0; i<total; i++)
{
lista.push_back(i);
}
//map de char-int
for (long unsigned int i=0; i<total; i++)
{
mapa.insert (std::pair<std::string,long unsigned int>(numToString(i),i));
}
long unsigned int valor;
std::string cadena;
do
{
cout<<"Ingresa un valor a buscar entre 0 y "<<total<<endl;
cin>>valor;
std::string cadena = numToString(valor);
if (existe(lista,valor))
{
cout<<"La lista contiene el valor: "<<valor<<endl;
}
else
{
cout<<"La lista NO contiene el valor: "<<valor<<endl;
}
if (existe(mapa,cadena))
{
cout<<"El mapa contiene el valor: "<<cadena<<endl;
}
}
while (valor!=-1);
return 0;
}
bool existe(const list<long unsigned int>&lista, long unsigned int valor)
{
clock_t t_ini, t_fin;
double secs;
t_ini=clock();
for (auto elem:lista)
{
if (elem == valor)
{
t_fin = clock();
secs = (double)(t_fin - t_ini) / CLOCKS_PER_SEC;
cout<<"Tiempo: "<<secs*multiplicador<<endl;
return true;
}
}
t_fin = clock();
secs = (double)(t_fin - t_ini) / CLOCKS_PER_SEC;
cout<<"Tiempo: "<<secs*multiplicador<<endl;
return false;
}
bool existe(const std::map<std::string,long unsigned int> &mapa, std::string valor)
{
clock_t t_ini, t_fin;
double secs;
t_ini=clock();
auto it = mapa.find(valor);
std::cout<<"El valor: "<<mapa.at(valor)<<std::endl;
t_fin = clock();
secs = (double)(t_fin - t_ini) / CLOCKS_PER_SEC;
cout<<"Tiempo: "<<secs*multiplicador<<endl;
if (it!=mapa.end())
{
return true;
}
return false;
}
std::string numToString(long unsigned int num)
{
long unsigned aux,indice=0,D;
string numstr;
while(num!=0)
{
D = num % 10;
char var = D+48;
auto it = numstr.begin();
numstr.insert(it,var);
indice++;
num/=10;
}
return numstr;
}
