在C++中交换两个向量之间长度不同的序列

Question

假设你有两个整数向量：

我想定义一个函数，允许我通过传递起始索引和两个序列的长度来交换两个向量中的一系列元素。

例如： 其中 和 是向量，作为参数传递的数字表示序列的起始索引和长度。

在这种情况下，输出应为

v1 = 1,2, 13,14,15 ,5,6,7,8,9

v2 = 10,11,12, 3,4 ,16,17,18

我所定义的函数签名不是限制，如果您认为有更好的方法，那也可以。

- JackNova

Answer 1

看起来所有常规的STL算法都无法完全满足您想要做的事情：

std::swap_ranges几乎可以胜任，但它要求您交换长度相等的范围 std::rotate也不错，但它要求第一个范围的结束点等于第二个范围的开始点。

// pseudo-splice on vector
v1.insert(v1.begin() + 2 + 2, v2.begin() + 3, v2.begin() + 3 + 3);
v2.erase(v2.begin() + 3, v2.begin() + 3 + 3);

// pseudo-splice on vector
v2.insert(v2.begin() + 3, v1.begin() + 2, v1.begin() + 2 + 2);
v1.erase(v1.begin() + 2, v1.begin() + 2 + 2);

当然，你可以轻松地将此抽象为一个函数模板，该模板接受两个范围的任意迭代器边界。

根据David的评论进行编辑，您可以进行一些优化以避免不必要的调整大小。

// compute smallest range here, in this case it's the v1 part
std::swap_ranges(v1.begin() + 2, v1.begin() + 2 + 2, v2.begin() + 3);

// now handle the remaining part of the longest range, in this case it's element v2 + 3 + 2
std::insert(v1.begin() + 2 + 2, v2.begin() + 3 + 2);
std::erase(v2.begin() + 3 + 2);

更新: 如果你使用std::list，那么你可以使用splice，这样更容易 (我在那里重新排列了insert/erase部分以模仿下面的代码)。

v1.splice(v1.begin() + 2 + 2, v2, v2.begin() + 3, v2.begin() + 3 + 3);
v2.splice(v2.begin() + 3, v1, v1.begin() + 2, v1.begin() + 2 + 2);

- TemplateRex

---

+1 是因为它能够正常工作。它可以进行改进，以避免一些向量的调整大小（例如交换前 min(length1,length2) 个元素，然后插入/删除其余部分），但我现在有点懒得编码。 - David Rodríguez - dribeas

@DavidRodríguez-dribeas 谢谢，如果 vector 上有 STL 切片(splice) 就好了。 - TemplateRex

Answer 2

我认为这应该不会有任何困难，除非 Length1 != Length2，那么您将不得不重新分配向量。

 swap_elements(v1, start1, length1, v2, start2, length2){
      if(length1 != length2){
        //alloc mem for both of the arrays
        //copy the unmodified portions of the original arrays into the new arrays
      }

      //swap the elements
 }

- Razvan

Answer 3

使用插入和删除来进行原地操作的运行时间比下面的代码更差，因为每次调用插入和删除时，向量的其他元素都必须相应地在内存中移动，并分配新的内存块，如果需要，则将向量元素移动到新的内存块。为避免重新调整大小和内存问题，最好在最开始就创建两个新的向量。

swap_elements(vector<int> &v1, int s1, int l1, vector<int> &v2, int s2, int l2){
    vector<int> nv1(v1.begin(),v1.begin()+s1);
    vector<int> nv2(v2.begin(),v2.begin()+s2);
    for(int i=0;i<l2;i++)
      nv1.push_back(v2[s2+i]);
    for(int i=0;i<l1;i++)
      nv2.push_back(v1[s1+i]);
    for(int i=s1+l1+1;i<v1.size();i++)
      nv1.push_back(v1[i]);
    for(int i=s2+l2+1;i<v2.size();i++)
      nv2.push_back(v2[i]);
    v1.clear();
    v2.clear();
    v1=nv1;
    v2=nv2;
}

- aaronqli