c++ - ordenar - Usando set_union para cadenas

sort string c++

Question

Tengo dos vectores, necesito su unión en un tercer vector (sin especificar el tamaño del tercer vector)

std::vector<std::string> a = {"a","b"};
std::vector<std::string> b = {"d","c"};

std::vector<std::string> c;

std::set_union(a.begin(),a.end(),b.begin(),b.end(),c.begin());
std::cout<<c[1];

Esto compila pero da una salida vacía.

Answer 1

Dos cosas están mal con tu código:

1. no leyó los requisitos de std::set_union : los rangos de entrada deben ordenarse de acuerdo con la función de comparación dada ( operator< en su caso), esto no se cumple para b .
2. el algoritmo no puede cambiar el tamaño de c a c.begin() ; permanece vacío y escribes fuera de los límites. Utilice std::back_insert_iterator .

Answer 2

El algoritmo std::set_union requiere secuencias ordenadas. En su ejemplo de cadenas, el primer vector está ordenado en orden ascendente y el segundo, en orden descendente.

Además, el vector c está vacío, por lo que no puede usar la expresión c.begin() en la llamada del algoritmo. Necesita usar std::back_insert_iterator .

Para su ejemplo de cadenas, la llamada del algoritmo puede verse de la siguiente manera como se muestra en el programa demostrativo.

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>


int main() 
{
    std::vector<std::string> a = { "a", "b" };
    std::vector<std::string> b = { "d", "c" };

    std::vector<std::string> c;

    std::set_union( std::begin( a ), std::end( a ), 
                    std::rbegin( b ), std::rend( b ),
                    std::back_inserter( c ) );

    for ( const auto &s : c ) std::cout << s << '' '';
    std::cout << ''/n'';

    return 0;
}

Su salida es

a b c d 

De lo contrario, debe ordenar los vectores.

Si no puede ordenar los vectores originales, puede usar el siguiente enfoque

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>


int main() 
{
    std::vector<std::string> a = { "a", "b" };
    std::vector<std::string> b = { "d", "c", "a" };

    std::vector<std::string> c( a );
    c.insert( std::end( c ), std::begin( b ), std::end( b ) );

    std::sort( std::begin( c ), std::end( c ) );

    c.erase( std::unique( std::begin( c ), std::end( c ) ), std::end( c ) );

    for ( const auto &s : c ) std::cout << s << '' '';
    std::cout << ''/n'';

    return 0;
}

La salida del programa es

a b c d

Answer 3

Una alternativa al uso del algoritmo std::set_union() sería usar el contenedor std::set o std::unordered_set para almacenar todos los elementos de ambos vectores y luego inicializar el vector resultante desde ese contenedor.

El inconveniente de este enfoque es que el contenedor adicional requiere un espacio lineal en el número de elementos únicos en los dos vectores.

El contenedor que use dependerá de si necesita o no el vector resultante para ordenarlo. Si no necesita que se ordene el vector resultante, puede usar std::unordered_set :

std::vector<std::string> make_unsorted_union(const std::vector<std::string>& a,
                                             const std::vector<std::string>& b)
{
   std::unordered_set<std::string> st;

   for (auto& str: a)
      st.insert(str);

   for (auto& str: b)
      st.insert(str);

   return std::vector<std::string>(st.begin(), st.end());
}

Insertar un elemento en un std::unordered_set se puede hacer en tiempo constante en promedio.

Si necesita que se ordene el vector resultante, puede usar std::set lugar:

std::vector<std::string> make_sorted_union(const std::vector<std::string>& a,
                                            const std::vector<std::string>& b)
{
   std::set<std::string> st;

   for (auto& str: a)
      st.insert(str);

   for (auto& str: b)
      st.insert(str);

   return std::vector<std::string>(st.begin(), st.end());
}

Estas funciones se pueden usar de la siguiente manera:

int main() {
   std::vector<std::string> a = {"a", "z", "z", "b", "z"};
   std::vector<std::string> b = {"d", "v", "c", "x", "e"};

   std::vector<std::string> c = make_unsorted_union(a, b);

   for (auto& str: c)
      std::cout << str << '' '';
   std::cout << ''/n'';

   c = make_sorted_union(a, b);

   for (auto& str: c)
      std::cout << str << '' '';
   std::cout << ''/n'';
}

Mi salida de este programa es:

e c x b v d z a 
a b c d e v x z