Comparar dos std::vector no ordenados.

Answer

1. 

   davy.ai

   July 22, 2023 at 11:05 pm

   El enfoque que estás utilizando actualmente con std::is_permutation es un método razonable para comparar dos std::vectors desordenados, y debería funcionar bien tanto para vectores pequeños como grandes. Sin embargo, hay algunas opciones alternativas que podrías considerar dependiendo de tu caso de uso específico y requisitos de rendimiento:

   1. Ordenar los vectores y compararlos
      Ordenar primero los vectores utilizando std::sort, y luego compararlos de esta manera:

   std::vector<int> v1 = {1, 2, 3, 4, 5};
   std::vector<int> v2 = {2, 3, 4, 5, 1};
   
   std::sort(v1.begin(), v1.end());
   std::sort(v2.begin(), v2.end());
   
   const auto is_similar = v1 == v2;
   

   Este enfoque tiene una complejidad temporal de O(nlogn) debido a la ordenación, pero puede ser más rápido para vectores muy grandes porque std::is_permutation tiene una complejidad temporal en el peor de los casos de O(n^2) y puede requerir memoria adicional.

   1. Utilizar una función hash
      Otro enfoque es crear un hash de los vectores y compararlos. Aquí tienes un ejemplo utilizando boost::hash_combine:

   #include <boost functional/hash.hpp="">
   
   std::vector<int> v1 = {1, 2, 3, 4, 5};
   std::vector<int> v2 = {2, 3, 4, 5, 1};
   
   size_t seed1 = 0;
   for (auto i : v1) {
       boost::hash_combine(seed1, i);
   }
   
   size_t seed2 = 0;
   for (auto i : v2) {
       boost::hash_combine(seed2, i);
   }
   
   const auto is_similar = seed1 == seed2;
   

   Este enfoque tiene una complejidad temporal de O(n), pero puede haber colisiones si la función hash no es lo suficientemente robusta.

   En general, el enfoque que estás utilizando actualmente con std::is_permutation es una opción razonable para comparar vectores desordenados, y es posible que no necesites considerar otros enfoques a menos que tengas requisitos de rendimiento o robustez específicos.

Comments are closed.