合并两个已排序向量

Question

我有两个已排序的向量

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

我想合并这两个向量，使它们合并后仍保持排序。

第一种方法：

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

我不想要这种方式。我希望有比这更好的方法。

- Ranjeet Hinge

---

使用单个循环比较每个向量的第一个元素，将最小（或最大）的推入并推进该向量。当您用完元素时，请推送剩余部分。这可能是算法中std::merge所做的。 - Allan Wind

Answer 1

我会使用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));

- orlp

---

添加包含文件并建议您将其放在主函数中，以便您的示例可以编译。 - Allan Wind

不需要，那只是不必要的噪音。我的回答是合并两个先前定义的 vector<int> v1, v2 的代码片段，而不是完整的程序。 - orlp

Answer 2

你可以使用C++ STL的合并函数。

  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;

输出结果为：[1, 2, 3, 4, 5]

- starboy_jb

---

添加包含文件并建议您将其放在主函数中，以便您的示例可以编译。 - Allan Wind

在初始化v3时，不需要将vec1.size()和vec2.size()转换为int类型相加。实际上这样做是具有误导性的。两个size()成员函数调用返回的都是无符号类型，并且构造函数接受同一类型的大小值。 - Peter

Answer 3

有6种方法可以做到这一点。

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

- iamdhavalparmar

---

OP指出了预期结果，因此4、5、6不在讨论范围内；3有疑问；1、2是正确的。 - Jarod42

对于 std::set_union，如果两个数组包含重复元素，则只会保留其中一个。 - TYeung