是否有交换C++向量中的两个段的函数？

Question

我知道有std::swap可以交换一个向量中的两个元素，或者迭代交换两个相同长度的段。例如，我可以编写一个循环以便在向量abcdefgh中交换bcd和efg，从而生成aefgbcdh。但我可以做bcd和ef（不同长度）吗？或者std::vector有没有其他功能可以实现这个功能？

Answer 1

如果分段相邻，则可以使用std::rotate。例如：

std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

比方说，我想用{ 4, 5, 6, 7 }来交换{ 1, 2, 3 }。我可以这样做：

std::rotate(v.begin() + 1, v.begin() + 4, v.begin() + 8); 

如果这些段是不相邻，您可以通过使用rotate两次做到这一点，但它可能会做更多的工作比是绝对必要的。例如，交换{ 1, 2 }与{ 4, 5, 6, 7 }

std::rotate(v.begin() + 1, v.begin() + 4, v.begin() + 8); 
std::rotate(v.begin() + 5, v.begin() + 7, v.begin() + 8); 

Answer 2

这减少了相等长度间隔互换后跟一个旋转。

等长间隔交换减少了问题'移动到另一个地方的间隔'，这可以在std::rotate就地实施。

如果半开区间[a,b)正在向前推进到x，则：

std::rotate(a,b,x); 

如果向后移动到y则：

std::rotate(y,a,b); 

如果我们假设，我们可以得到在间隔正确的顺序（在序列中右侧之前的左间隔），那么我们可以这样做：

template<class I> 
void swap(I a, I b, I x, I y){ 
    using std::distance; using std::next; using std::advance; 
    auto d_ab=distance(a,b); 
    auto d_xy=distance(x,y) 
    auto d=(std::min)(d_ab,d_xy); 
    std::swap_ranges(a,next(a,d),x); 
    advance(a,d); 
    advance(x,d); 
    if (a==b){ 
    std::rotate(b,x,y); 
    }else{ 
    std::rotate(a,b,x); 
    } 
} 

可以完成避免不止一次元素遍历的微优化，但是对于向量迭代器，额外的优化可以接近免费。

一个工业强度的人可以做标签调度，为随机访问迭代器写一个漂亮的代码，并为其他迭代器做一个双迭代器循环交换元素（手动交换范围边界检查），末尾有类似的rotate。

如果我们不知道的顺序是a，b，x，y我们需要需要随机访问迭代器（并获得<访问）。然后我们需要包装上面的std::rotate调用以更改参数的顺序。

通过访问end迭代器，我们可以在转发迭代器仍然效率低下的情况下做到这一点。