CODEWITHSUNDEEP
c++stdsetset-union
sitiposit
sitiposit

Reputation: 149

Forming the union of two sets seems to give wrong and inconsistent answers

The following code is my attempt to form the union of the two element set {2,3} with the empty set {}. I expect that the resulting container (in this case, a list) should have size 2.

However, when I run the code, I get that the size of the union is 0 or 3, depending on which of the two indicated locations for the declaration of the variable united. Neither of these results is what I expected and they clearly can't both be correct.

What am I missing here? 

#include <list>
#include <set>
#include <algorithm>  
#include <iostream>

using namespace std;

int main()
{
    //list<int> united; // resulting output is 3

    int d1[] = {2,3};
    set<int> dom1(d1, d1+2);
    set<int> dom2;

    list<int> united; // resulting output is 0

    set_union(dom1.begin(), dom1.end(), dom2.begin(), dom2.end(), united.begin());

    cout << united.size();

    return 0;
}

Upvotes: 0

Views: 80

Answers (2)

eerorika
eerorika

Reputation: 238301

If you take a look at the documentation of std::set_union you'll find that the fifth iterator must meet the requirements of OutputIterator.

Then, if you take a look at the documentation of std::list::begin, you'll find that it returns a std::list::iterator (or std::list::const_iterator), which is only a BidirectionalIterator which is a subtype of InputIterator.

Technically, a non const InputIterator is also an OutputIterator but that behaves in a way that does not work for your program. It iterates the nodes of united and copy-assigns the source elements over the ones already existing. But since united is empty in your case, the iterator goes out of bounds, resulting in undefined behaviour.

An easy way to get an OutputIterator that inserts new elements, is to use the std::back_inserter.

Upvotes: 3

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385098

In general, whenever you get "wrong and inconsistent answers", you have undefined behaviour, or your program is otherwise ill-formed without having been diagnosed. Look for out-of-range bugs.

Here, your output iterator refers to a range that does not exist.

You should replace united.begin() with std::back_inserter(united), so that elements are created as needed.

This is per the example in the cppreference.com std::set_union documentation.
Read the documentation!

Upvotes: 2

Related Questions