Union with map?

Question

I am trying to Union two sets with map. I have two sets and would like to combine them into a third one. I get an error for this code in the push_back. Is there a way to do this?

map<char, vector<char> > numbers;
map<char, vector<char> >::iterator it;
numbers['E'].push_back('a');//set1
numbers['E'].push_back('b');
numbers['E'].push_back('c');
numbers['G'].push_back('d');//set2
numbers['G'].push_back('e');


void Create::Union(char set1, char set2, char set3)
{
    for (it = numbers.begin(); it != numbers.end(); ++it)
    {
     numbers[set3].push_back(it->second);
    }
}

Answer 1

I think you might want:

void Create::Union(char set1, char set2, char set3)
{
    vector<char> &target = numbers[set3];
    for (it = numbers.begin(); it != numbers.end(); ++it)
    {
        if (&it->second == &target)
            continue; // Don't insert into ourselves
        target.insert(target.end(), it->second.begin(), it->second.end());
    }
}

push_back was trying to add the item->second vector itself to the target vector; this way explicitly copies the contents only.

Answer 2

numbers is a load of vectors, keyed by character. So it->second is a vector. You can't push_back a vector into a vector of char.

You should be iterating over numbers[set1] and numbers[set2], not iterating over numbers. Or as bdonlan says, you could insert a range, although he's taking a union of everything in numbers, not just set1 and set2.

Also: where's item defined? Do you mean it?

Also, note that push_back doesn't check whether the value is in the vector already. So once you get the details of this general approach sorted out, your example case will work and the union of 'E' and 'G' will be a vector containing 'a','b','c','d','e'. But if you took the union of 'a','b','c' with 'c','d','e' you'd get 'a','b','c','c','d','e', which probably isn't what you want from a union.

Assuming your vectors are always going to be sorted, you could instead use the standard algorithm set_union:

#include <algorithm>
#include <iterator>

...

numbers[set3].clear();
std::set_union(numbers[set1].begin(), numbers[set1].end(),
               numbers[set2].begin(), numbers[set2].end(),
               std::back_inserter(numbers[set3]));

If you want to take the union of everything in numbers, I would probably go with either:

vector<char> sofar;
map<char, vector<char> >::iterator it;
for (it = numbers.begin(); it != numbers.end(); ++it) {
    // new, empty vector
    vector<char> target;
    // merge everything so far with the next item from the map,
    // putting the results in target
    set_union(sofar.begin(), sofar.end(),
              it->second.begin(), it->second.end(),
              back_inserter(target));
    // the result is the new "everything so far"
    // note that this operation is very fast. It doesn't have to
    // copy any of the contents of the vector, just exchange some pointers.
    swap(target, sofar);
}
// replace numbers[set3] with the final result
swap(numbers[set3], sofar);

Or:

set<char> sofar;
map<char, vector<char> >::iterator it;
for (it = numbers.begin(); it != numbers.end(); ++it) {
    // let std::set remove the duplicates for us
    sofar.insert(it->second.begin(), it->second.end());
}
// replace numbers[set3] with the final result
numbers[set3].clear();
numbers[set3].insert(numbers[set3].end(), sofar.begin(), sofar.end());

This is less code and might be faster, or might thrash the memory allocator too much. Not sure which is better, and for small collections performance almost certainly doesn't matter at all.

The version with set also doesn't require the vectors to be sorted, although it's faster if they are.