value propagation in a std::vector

Question

If I have a std::vector initialized like this:

0 1 2 3 4 5

how can I best propagate the 4 to the first place? I.e. I want the std::vector in this state:

4 0 1 2 3 5

Removing the 4 and reinserting it could be expensive, as insertions at the front are O(N), I believe. I was thinking about swapping values in successive places (like in bubble sort), but that would be also O(N). Is using another container, like std::list the only way?

EDIT: After seeing some confusion, let me clarify, that my objective is to prepend a value at a known arbitrary location in the std::vector in front of a value at another known location in the std::vector.

Answer 1

Even if there is an accepted answer, the normal C++ way is to use provided algorithms. In this case it should be 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;
}

Edit: after discussion with Luc Touraille I saw room for improvement. Now the solution uses std::advance for iterator manipulation. So it should work with forward iterators which are the requirement for std::rotate.

Answer 2

Changing the container (e.g. std::deque) is the only option if O(N) is an issue.

However, do make sure that O(N) really is an issue!