26

Is there any better way (either faster or with fewer symbols of code) than erasing the element and re-adding it to the back?

template <typename T>
void moveItemToBack(std::vector<T>& v, size_t itemIndex)
{
   T tmp(v[itemIndex]);
   v.erase(v.begin() + itemIndex);
   v.push_back(tmp);
}
6
  • Not really...Vector is not a very efficient way to store things that need to be removed from the beginning. Look at std::queue or std::dequeue
    – IdeaHat
    May 21, 2014 at 16:59
  • @MadScienceDreams: std::dequeue is no better here, and I need random access. May 21, 2014 at 17:00
  • Then the efficient structure to use is to make your own ring buffer.
    – IdeaHat
    May 21, 2014 at 17:01
  • 1
    Sorry, the down-vote wasn't me (unfortunately, I've found a lot of stack overflow puts down-votes on "beginner" questions). The fact that I don't have a direct answer to your question is why I'm in the comments. A ring buffer would utilize a vector, be constant time to do this operation (which answers the "faster" part).
    – IdeaHat
    May 21, 2014 at 17:10
  • 2
    You also might try using std::rotate. It will do what you want but I'm not sure if it would be faster or slower than push_back/erase. May 21, 2014 at 17:37

3 Answers 3

53

You can do this with std::rotate from the standard library. Since this doesn't change the vector size it also won't trigger a reallocation. Your function would look something like this:

template <typename T>
void moveItemToBack(std::vector<T>& v, size_t itemIndex)
{
    auto it = v.begin() + itemIndex;
    std::rotate(it, it + 1, v.end());
}
3
  • 2
    This is what Stepanov (designed the STL) recommends: stepanovpapers.com/notes.pdf , pg. 154. May 21, 2014 at 18:03
  • Just a note: if I'm reading this correctly, this has O(n) complexity. The std::swap solution below has complexity O(1).
    – geometrian
    Oct 11, 2016 at 8:19
  • 2
    @imallett You're correct. This answer does preserve the order of elements other than the moved item while the other answer doesn't. The question, as stated, wasn't clear if that was a requirement. Preserving order is more costly. Oct 11, 2016 at 16:43
13

Possibly the fastest way, would be to swap it with the last element

template <typename T>
void moveItemToBack(std::vector<T>& v, size_t itemIndex)
{
   std::swap(v[itemIndex], v.back()); // or swap with *(v.end()-1)
}

one operation! Ofcourse std::swap has to work with T

4
  • 7
    It's an obvious solution, but it alters the ordering of items beyond simply moving one to the end. May 21, 2014 at 19:20
  • @VioletGiraffe While rotate doesn't ? May 21, 2014 at 19:20
  • @VioletGiraffe OK now got what you ment. It's OK to rotate as long as the relative order doesn't change. I was just giving a literal answer to the question "move one element to the back" May 21, 2014 at 19:21
  • Of course, it's my mistake I didn't express all the requirements in my question. Your answer suits my question as currently stated. May 21, 2014 at 19:27
5

You can avoid the extra variable.

v.push_back(v[itemIndex]);
v.erase(v.begin() + itemIndex);

If you delete frequently from the middle of the vector and can rewrite your code so that it doesn't require random access, you may be able to improve efficiency by using a linked list (std::list) instead.

5
  • Ah, of course, neat! Thanks. BTW, is there any benefit to using emplace_back rather than push_back here? May 21, 2014 at 17:00
  • @VioletGiraffe, if T is small, emplace_back is not likely to be faster than push_back. If T is large then I'm actually not sure.
    – Brian Bi
    May 21, 2014 at 17:01
  • 1
    @Brian emplace_back actually calls the constructor for the class, which would reduce to the copy constructor with this call...so in this case, I don't think it would matter for either. You could do v.push_back(std::move(v[itemIndex)) to trigger using the move constructor in C++11.
    – IdeaHat
    May 21, 2014 at 17:14
  • @MadScienceDreams, you're right, I was stupid for a moment there and thought push_back took its argument by value
    – Brian Bi
    May 21, 2014 at 17:17
  • 5
    There is a potential performance hit doing it this way. Doing push_back before the erase temporarily increases the vector's size and might cause a reallocation. May 21, 2014 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.