std :: vector中的值传播

Question

如果我有这样的std::vector初始化:

0 1 2 3 4 5

我怎样才能最好地将4个传播到第一个位置？即我想要std::vector在这种状态:

4 0 1 2 3 5

移除4并重新插入它可能是昂贵的,因为O(N)我相信前面的插入.我在考虑在连续的地方交换价值(比如泡泡排序),但那也是O(N).是否只使用另一个容器std::list？

编辑:在看到一些混乱之后,让我澄清一下,我的目标是在一个已知的任意位置预先设置一个值std::vector,该值位于另一个已知位置的值前面std::vector.

Answer 1

即使有一个公认的答案,正常的C++方式是使用提供的算法.在这种情况下,它应该是std :: rotate

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // for std::advance


int main(int argc, char** argv) {

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

    std::cout << "Before: ";
    for (auto element : v)
        std::cout << element << " ";
    std::cout << std::endl;

    // edit starts here
    auto first=v.begin();
    auto nfirst=first;
    std::advance(nfirst, 4); // Iterator of first element to move to front
    auto last=nfirst;
    std::advance(last, 1); // 1 is element count for moving to front

    std::rotate(first, nfirst, last);
    // edit ends here

    std::cout << "After: ";
    for (auto element : v)
        std::cout << element << " ";
    std::cout << std::endl;

    return 0;
}

编辑: 与Luc Touraille讨论后,我看到了改进的空间.现在该解决方案std::advance用于迭代器操作.所以它应该使用前向迭代器,这是需要的std::rotate.

Answer 2

如果O(N)是一个问题,更改容器(例如std :: deque)是唯一的选择.

但是,确保O(N)确实是一个问题!