Merge Two sorted vectors

Question

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.

Answer 1

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));

Answer 2

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]

Answer 3

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()); ```