Spreading a value in std :: vector

Question

If I initialized std::vector as follows:

 0 1 2 3 4 5 

how can i best spread 4 in first place? That is, I want std::vector in this state:

 4 0 1 2 3 5 

Removing 4 and reinserting can be expensive, since the front panel inserts are O(N) , I think. I was thinking of changing the values ​​in sequential places (e.g. in sorting bubbles), but that would also be O(N) . Does another container, like std::list only way?

EDIT: Seeing some confusion, let me make it clear that my goal is to add a value in a known arbitrary place in std::vector before a value in another famous place in std::vector .

Answer 1

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

However, make sure that O (N) is indeed a problem!

Answer 2

Even if there is an accepted answer, the usual C ++ way is to use the 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 discussing with Luke Torail, I saw a place for improvement. Now the solution uses std::advance to manipulate the iterator. Therefore, it should work with advanced iterators, which are mandatory for std::rotate .

Answer 3

Seriously, I have serious doubts that O (n) really is a problem in your actual code. There are much better reasons to use std::vector instead of std::list , for example, better memory locality and less memory overhead than just big-O. But you can still optimize the standard approach (which requires dst be up to src , though)

 std::vector<int>::iterator src = ..., dst = ...; ... auto tmp = std::move(*src); vec.erase(src); vec.insert(dst, std::move(tmp)); 

slightly, turning both O (n) traversals (one left shift in erase and one left shift in insert ) by one (possibly even smaller):

 auto tmp = std::move(*src); for(auto iter=src; iter!=dst; --iter) *iter = std::move(*std::prev(iter)); *dst = std::move(tmp); 

EDIT:. Note that my code snippet above does nothing but the need to replicate std::rotate , as Jan suggested in his answer.

Answer 4

In addition to the excellent answer provided by @JanHerrmann, here is a general function for moving an element in a range:

 #include <algorithm> #include <iostream> #include <iterator> // Moves the element src before dst, maintaining the order of other values template <typename RandomAccessIt> void moveElement(RandomAccessIt src, RandomAccessIt dst) { if (dst == src) { return; } if (dst < src) { std::rotate(dst, src, src + 1); } else { std::rotate(src, src + 1, dst); } } void printVector(const std::vector<int> &v) { std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; } int main() { std::vector<int> v = { 0, 1, 2, 3, 4, 5 }; printVector(v); // 0 1 2 3 4 5 moveElement(v.begin() + 4, v.begin()); printVector(v); // 4 0 1 2 3 5 moveElement(v.begin() + 2, v.begin() + 2); printVector(v); // 4 0 1 2 3 5 moveElement(v.begin() + 2, v.begin() + 3); printVector(v); // 4 0 1 2 3 5 moveElement(v.begin() + 2, v.end()); printVector(v); // 4 0 2 3 5 1 }