Using set_union for strings

Question

I have two vectors, I need their union in a third vector (without specifying the size of the third 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];

This compiles but gives an empty output.

Answer 1

The algorithm std::set_union requires ordered sequences. In your example of strings the first vector is ordered in the ascending order and the second one - in the descending order.

Moreover the vector c is empty so you may not use the expression c.begin() in the call of the algorithm. You need to use std::back_insert_iterator.

For your example of strings the call of the algorithm can look the following way as it is shown in the demonstrative program.

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

Its output is

a b c d 

Otherwise you need to sort vectors.

If you may not sort the original vectors then you can use the following approach

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

The program output is

a b c d

Answer 2

Two things wrong with your code:

1. you didn't read the requirements of std::set_union - the input ranges have to be sorted according to the given comparison function (operator< in your case) - this does not hold for b.
2. the algorithm cannot resize c through c.begin(); it remains empty and you write out of bounds. Use std::back_insert_iterator.

Answer 3

An alternative to using the std::set_union() algorithm would be to use either the std::set or std::unordered_set container for storing all the elements of both vectors and then initialising the resulting vector from that container.

The drawback to this approach is that the additional container requires linear space in the number of unique elements across the two vectors.

Which container you use, will depend on whether or not you need the resulting vector to be sorted. If you don't need the resulting vector to be sorted, you can just use 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());
}

Inserting an element into an std::unordered_set can be done in constant time on average.

If you need the resulting vector to be sorted, then you can use std::set instead:

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

These functions can be used as follows:

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

My output of this program is:

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