set_union got wrong result when i called it twice

Question

this problem confused me for many hours, please help me! the first time I call set_union, the result is right, but second I call it, the result is wrong, see the code:

std::vector<int> set1{ 1, 2, 3, 4, 5, 6 };
std::vector<int> set2{ 4, 5, 6, 7, 8 };
std::vector<int> result{};

std::set_union(std::begin(set1), std::end(set1),
    std::begin(result), std::end(result), 
    std::back_inserter(result));  
// result is 1 2 3 4 5 6

std::back_insert_iterator< std::vector<int>> back2 =
    std::set_union(std::begin(set2), std::end(set2), 
        std::begin(result), std::end(result), 
        std::back_inserter(result));

I debug the above code, get this result:

[0] 1   int
[1] 2   int
[2] 3   int
[3] 4   int
[4] 5   int
[5] 6   int
[6] 1   int
[7] - 572662307 int
[8] - 572662307 int
[9] - 572662307 int
[10] - 572662307    int
[11] - 572662307    int
[12]    4   int
[13]    5   int
[14]    6   int
[15]    7   int
[16]    8   int

score 3 · Accepted Answer · answered May 06 '19 at 07:03

The resulting range cannot overlap with either of the input ranges. https://en.cppreference.com/w/cpp/algorithm/set_union

Why don't you use this?

 std::set_union(std::begin(set1), std::end(set1), 
    std::begin(set2), std::end(set2), 
    std::back_inserter(result));

score 2 · Answer 2 · answered May 06 '19 at 07:04

You have undefined behavior here. When you pass iterators to result as both input and output parameters to std::set_union, writing to the output iterator invalidates all input iterators. This is due to the memory layout of std::vector - writing to it might require moving all its data to a new memory location, if the capacity can't hold a new element, so references/pointers/iterators that refer to the initial memory locations can't be used anymore.

You want to store the result in a new container, e.g.

std::vector<int> out;
std::set_union(std::begin(set2), std::end(set2), 
    std::begin(result), std::end(result), 
    std::back_inserter(out));

Also note that for the first invocation, std::copy is the more appropriate algorithm (or assignment result = set1;).

set_union got wrong result when i called it twice

2 Answers2