CODEWITHSUNDEEP
c++algorithm
Bob John
Bob John

Reputation: 3878

Can someone concisely explain how set_union works in c++?

I'm confused as to how to interpret the code given for set_union in the following page: http://www.cplusplus.com/reference/algorithm/set_union/

How does the algorithm ensure that the result holds the union of the two sets when the function returns? For example, if we wanted to find the set_union of the following lists:

L1        L2

hi        goodbye
bye       hello
see       hi
two       bye
three     hooray

Can someone walk me through how the algorithm works for lists like this, assuming we have an iterator to the front and back of each?

Upvotes: 0

Views: 132

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

You are missing a key requirement for the set_union to work: both ranges that you pass into it must be sorted. From the link that you posted:

set_union Constructs a sorted range beginning in the location pointed by result with the set union of the two sorted ranges [first1,last1) and [first2,last2).

The code shown on the page simply performs a merge of two pre-sorted sequences.

Upvotes: 3

David Rodríguez - dribeas
David Rodríguez - dribeas

Reputation: 208323

The key piece of information is that the algorithm assumes as a precondition that the elements are ordered in both ranges, so in your case it would be:

L1:  bye, hi, see, three, two
L2:  bye, goodbye, hello, hi, hooray

With that in mind it is not hard to follow what the algorithm does.

While the both ranges contain elements, add to the union the smallest of the elements pointed by the iterators and advance that iterator. If both iterators refer to the same element, add it and advance both iterators (you don't want to insert twice).

After one of the ranges is empty, just copy all of the remaining elements from the other range to the solution.

In this case, insert bye and advance both iterators, insert goodbye and advance the second iterator, insert hello and advance the second iterator, insert hi and advance both iterators, insert hooray and advance the second iterator. Now the second range is empty so just complete with the remaining elements from the first range.

Upvotes: 1

Related Questions