CODEWITHSUNDEEP
c++
Ranjeet Hinge
Ranjeet Hinge

Reputation: 109

Merge Two sorted vectors

I have two sorted vectors

std::vector<int> v1 = {1,3}
std::vector<int> v2 = {2}

I want to merge this two vectors in such a way that after merging they remain sorted

1st Approach :

std::vector<int> v3;

for (int i = 0; i < v1.size(); i++)
{
   v3.push_back(v1[i]);
}

for (int i = 0; i < v1.size(); i++)
{
   v3.push_back(v2[i]);
}

sort(v3.begin(), v3.end());

I dont want this type of approach . I want better approach than this one.

Upvotes: 10

Views: 10845

Answers (3)

iamdhavalparmar
iamdhavalparmar

Reputation: 1218

There are 6 ways to do that.

  1. merge(beg1, end1, beg2, end2, beg3):- This function merges two sorted containers and stores them in a new container in sorted order (merge sort). It takes 5 arguments, first and the last iterator of 1st container, first and the last iterator of 2nd container and 1st iterator of the resultant container.

    vector<int> v1 = {1, 3, 4, 5, 20, 30}; 
  vector<int> v2 = {1, 5, 6, 7, 25, 30}; 
  vector<int> v3(12); 

   // Using merge() to merge vectors v1 and v2 
  // and storing result in v3 
  merge(v1.begin(), v1.end(), v2.begin(),  
                    v2.end(), v3.begin());

  2. inplace_merge(beg1, beg2, end):- This function is used to sort two consecutively placed sorted ranges in a single container. It takes 3 arguments, an iterator to the beginning of 1st sorted range, an iterator to the beginning of 2nd sorted range, an iterator to the last position.

     vector<int> v2 = {1, 5, 6, 7, 25, 30}; 

 vector<int> v3(12); 

 // using copy to copy both vectors into  
 // one container 
 auto it = copy(v1.begin(), v1.end(), v3.begin()); 
 copy(v2.begin(), v2.end(), it); 

 // Using inplace_merge() to sort the container 
 inplace_merge(v3.begin(),it,v3.end()); ```

  3. set_union(beg1, end1, beg2, end2, beg3):- This function computes the set union of two containers and stores them in a new container . It returns the iterator to the last element of the resultant container. It takes 5 arguments, the first and the last iterator of the 1st container, the first and last iterator of the 2nd container, and 1st iterator of the resultant container. The containers should be sorted and it is necessary that the new container is resized to a suitable size.

  4. set_intersection(beg1, end1, beg2, end2, beg3):- This function computes the set intersection of two containers and stores it in a new container . It returns the iterator to the last element of the resultant container. It takes 5 arguments, the first and the last iterator of 1st container, the first and the last iterator of the 2nd container, and 1st iterator of the resultant container. The containers should be sorted and it is necessary that the new container is resized to a suitable size.

    
 // Initializing 2nd vector 
 vector<int> v2 = {1, 5, 6, 7, 25, 30}; 

 // Declaring resultant vector 
 // for union 
 vector<int> v3(10); 

 // Declaring resultant vector 
 // for intersection 
 vector<int> v4(10); 

 // using set_union() to compute union  of 2  
 // containers v1 and v2 and store result in v3 
 auto it = set_union(v1.begin(), v1.end(), v2.begin(),  
                              v2.end(), v3.begin()); 

 // using set_intersection() to compute intersection 
 // of 2 containers v1 and v2 and store result in v4 
 auto it1 = set_intersection(v1.begin(),v1.end(),  
               v2.begin(), v2.end(), v4.begin());```

  5. set_difference(beg1, end1, beg2, end2, beg3):- This function computes the set difference of two containers and stores them in a new container. It returns the iterator to the last element of the resultant container. It takes 5 arguments, the first and the last iterator of the 1st container, the first and the last iterator of the 2nd container, and 1st iterator of the resultant container. The containers should be sorted and it is necessary that the new container is resized to a suitable size.

  6. set_symmetric_difference(beg1, end1, beg2, end2, beg3):- This function computes the set symmetric difference of two containers and stores it in a new container . It returns the iterator to the last element of the resultant container. It takes 5 arguments, the first and the last iterator of the 1st container, the first and the last iterator of the 2nd container, and 1st iterator of the resultant container. The containers should be sorted and it is necessary that the new container is resized to a suitable size. vector v1 = {1, 3, 4, 5, 20, 30};

     vector<int> v2 = {1, 5, 6, 7, 25, 30}; 

 // Declaring resultant vector 
 // for difference 
 vector<int> v3(10); 

 // Declaring resultant vector 
 // for symmetric_difference 
 vector<int> v4(10); 


 // using set_difference() to compute difference 
 // of 2 containers v1 and v2. 
 auto it = set_difference(v1.begin(), v1.end(), 
              v2.begin(), v2.end(), v3.begin()); 

 // using set_symmetric_difference() to compute  
 // symmetric_difference/ of 2 containers 
 auto it1 = set_symmetric_difference(v1.begin(),  
       v1.end(), v2.begin(), v2.end(), v4.begin()); ```

Upvotes: 4

orlp
orlp

Reputation: 117661

I would use std::merge:

std::vector<int> v3;
v3.reserve(v1.size() + v2.size());
std::merge(v1.begin(), v1.end(),
           v2.begin(), v2.end(),
           std::back_inserter(v3));

Upvotes: 17

starboy_jb
starboy_jb

Reputation: 935

You can use c++ stl merge function.

  vector<int> vec1 = {1, 3, 5};
  vector<int> vec2 = {2, 4};

  vector<int> vec3((int)vec1.size() + (int)vec2.size());

  merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin());

  for (auto it : vec3) {
    cout << it << " ";
  } 

  cout << endl;

Output will be: [1, 2, 3, 4, 5]

Upvotes: 4

Related Questions