C++最简单有效的方法将单个元素移动到向量中的新位置

Question

对不起我的潜力nOOb'ness,但一直试图得到这几个小时,似乎无法找到一个优雅的解决方案的c ++ 98.

我的问题是,说我有一个字符串{a,b,c,d,e,f}的向量,我想把'e'移到第二个元素我怎么会这样做？显然,预期的输出现在打印出来{a,e,b,c,d,f}

理想情况下,寻找一个单独的操作,让我这样做只是为了提高效率,但我很乐意听到一些关于如何实现这一目标的建议.

谢谢.

Answer 1

std::vector<>因为它存储在连续的内存中而无法通过一个元素移动旧位置和新位置之间的所有内容,所以无法"高效"地执行此操作.所以它是矢量长度的线性时间(或者至少是移动的距离).

天真的解决方案将是insert()当时的erase(),但这需要在你修改的最右边的位置之后移动一切,两次!因此,你能做到"手",通过复制b通过d一个位置向右(例如用std::copy(),然后覆盖b.至少这样你避免换挡修改范围以外的任何东西.它看起来像你可以做std::rotate()这样做,正如@WhozCraig在评论中提到的那样.

Answer 2

std::rotate如果结果不够高效，我会首先尝试，并且只尝试其他手动操作（或矢量以外的容器）：

#include <vector>
#include <iostream>
#include <algorithm>

int main()
{
    // move 5 from 4th to 1st index

    std::vector<int> v {1,2,3,4,5,6};
    // position:        0 1 2 3 4 5

    std::size_t i_old = 4;
    std::size_t i_new = 1;
    auto it = v.begin();

    std::rotate( it + i_new, it + i_old, it + i_old + 1);
    for (int i : v) std::cout << i << ' ';
}

现场演示。