CODEWITHSUNDEEP
c++sortingmergestdvectorstdset
Eduard Rostomyan
Eduard Rostomyan

Reputation: 6546

Merging std::sets into std::vector

Consider the following.

I have two std::sets and want to merge them in the std::vector in sorted order.

Which is the most effective way to do that?

I did something like this, but I think that there must be a better way of doing it.

std::set<int> S1;
std::set<int> S2;
// ....
// Initialization of sets
// ....

std::vector V;

std::set<int>::iterator iter;

for(iter = S1.begin(); iter!=S1.end(); ++iter)
{
    V.push_back(*iter);
}

for(iter = S2.begin(); iter!=S2.end(); ++iter)
{
    V.push_back(*iter);
}

std::sort(V.begin(), V.end());

Here is my code, is there more effective way? Thanks in advance.

Upvotes: 3

Views: 504

Answers (4)

gleusch
gleusch

Reputation: 86

std::merge should do the trick, since S1 and S2 are sorted:

// Initialization of sets
// ....
std::vector V;

std::merge(S1.begin(), S1.end(), S2.begin(), S2.end(), std::back_inserter(V));

// instead of V.begin() -- thanks for the correction.

Upvotes: 7

quercus32
quercus32

Reputation: 116

The sets are already sorted, so it does seem wasteful to re-sort it all again at the end.

How about something like this (left a couple of TODOs as an excercise for the reader!):

  std::set<int>iterator S1iter = S1.begin();
  std::set<int>iterator S1iter = S2.begin();

  while( S1iter != S1.end() && S2iter != S2.end() ) {

    if( S1iter == S1.end() ) {
       //TODO:  S1 is finished, so push back range S2iter->S2.end()
       //       onto the vector
       break;
    }
    else if( S2iter == S2.end() ) {
       //TODO:  S2 is finished, so push back range S1iter->S1.end()
       //       onto the vector
       break;
    }
    else if( *S1iter < *S2iter ) {
      V.push_back( *S1iter );
      ++S1iter;
    }
    else {
      V.push_back( *S2iter );
      ++S2iter;
    }

  }

Upvotes: 1

MsrButterfly
MsrButterfly

Reputation: 1599

You can use std::merge(): http://en.cppreference.com/w/cpp/algorithm/merge

Its implementation is similar to yours.

Upvotes: 0

Havenard
Havenard

Reputation: 27864

I believe you can simplify your code by using std::copy():

std::copy(S1.begin(), S1.end(), std::back_inserter(V));
std::copy(S2.begin(), S2.end(), std::back_inserter(V));
std::sort(V.begin(), V.end());

Upvotes: 1

Related Questions