c++ - Использование set_union для строк




algorithm sorting (2)

У меня есть два вектора, мне нужно их объединение в третий вектор (без указания размера третьего вектора)

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];

Это компилируется, но дает пустой вывод.


Алгоритм std::set_union требует упорядоченных последовательностей. В вашем примере строк первый вектор упорядочен в порядке возрастания, а второй - в порядке убывания.

Более того, вектор c пуст, поэтому вы не можете использовать выражение c.begin() при вызове алгоритма. Вам нужно использовать std::back_insert_iterator .

Для вашего примера строк вызов алгоритма может выглядеть следующим образом, как это показано в демонстрационной программе.

#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;
}

Его вывод

a b c d 

В противном случае вам нужно отсортировать векторы.

Если вы не можете отсортировать исходные векторы, вы можете использовать следующий подход

#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;
}

Выход программы

a b c d

Альтернативой использованию алгоритма std::set_union() было бы использование std::set или std::unordered_set для хранения всех элементов обоих векторов и последующей инициализации результирующего вектора из этого контейнера.

Недостаток этого подхода заключается в том, что дополнительный контейнер требует линейного пространства в количестве уникальных элементов по двум векторам.

Какой контейнер вы используете, будет зависеть от того, нужен ли вам результирующий вектор для сортировки. Если вам не нужно сортировать полученный вектор, вы можете просто использовать 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());
}

Вставка элемента в std::unordered_set может быть выполнена в среднем за постоянное время.

Если вам нужно отсортировать полученный вектор, вы можете использовать вместо него std::set :

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());
}

Эти функции могут быть использованы следующим образом:

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';
}

Мой вывод этой программы:

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




stl