Ordenando por datos de estructura dentro de un unordered_map

Answer

1. 

   davy.ai

   July 25, 2023 at 7:33 pm

   Sí, hay una solución más eficiente utilizando el algoritmo std::sort y una función comparadora personalizada. Puedes crear un vector de pares, donde el primer elemento es la distancia y el segundo elemento es el identificador. Luego, puedes usar std::sort con una función lambda para ordenar el vector basado en las distancias. Finalmente, puedes iterar a través del vector ordenado y extraer los identificadores en un nuevo vector.

   Aquí tienes un código de ejemplo:

   std::vector<><int, id="">> distancias;
   distancias.reserve(data.size());
   
   for (const auto& [id, ciudad] : data) {
       distancias.emplace_back(ciudad.distancia, id);
   }
   
   std::sort(distancias.begin(), distancias.end(),
             [](const auto& a, const auto& b) {
                 return a.first < b.first;
             });
   
   std::vector<id> ids_ordenados;
   ids_ordenados.reserve(data.size());
   
   for (const auto& [distancia, id] : distancias) {
       ids_ordenados.push_back(id);
   }
   

   Este código crea un vector de pares llamado distancias, donde cada par contiene la distancia y el identificador. El vector se reserva inicialmente con el tamaño de data para evitar realocaciones innecesarias. Luego, recorre data y utiliza la función emplace_back para añadir cada par de distancia e identificador al vector distancias.

   A continuación, el código utiliza std::sort para ordenar el vector distancias basándose en las distancias. Pasa una función lambda al algoritmo sort para comparar dos elementos del vector distancias. La función lambda compara los primeros elementos (es decir, las distancias) de los dos pares.

   Finalmente, el código crea un nuevo vector llamado ids_ordenados y reserva espacio para él. Recorre el vector distancias ordenado y añade los identificadores al vector ids_ordenados.

   Esta solución tiene una complejidad de tiempo de O(n log n), donde n es el número de elementos en el mapa data. Esta complejidad se debe al uso de std::sort, que tiene una complejidad de tiempo promedio de O(n log n). Sin embargo, esta solución evita la creación de un std::map intermedio y la copia de elementos a un nuevo vector, lo cual debería ser más rápido que el enfoque original.</int,>

Comments are closed.