How do I remove the ith item from a std::vector?
I know I want to delete the ith element. I have int i; and std::vector<process> pList; where process is a struct. I want to do something equivalent to the following:
pList.remove(i); 
Add a comment |
5 Answers
Here is an O(1) solution, assuming you don't care about the order of elements:
#include <algorithm> // ... { using std::swap; swap(pList[i], pList.back()); pList.pop_back(); } For PODs, assignment is faster than swapping, so you should simply write:
pList[i] = pList.back(); pList.pop_back(); In C++11, you can forget the above distinction and always use move semantics for maximum efficiency:
if (i != pList.size() - 1) { // Beware of move assignment to self // see http://stackoverflow.com/questions/13127455/ pList[i] = std::move(pList.back()); } pList.pop_back(); 
5 Comments
Loki Astari
That's clever assuming order is not important.
Ylisar
An even faster version would skip the swap and instead just assign, as the last element is getting pop_backed anyway.
fredoverflow
@Ylisar: For many types, swapping is much more efficient than assignment. Examples include most of the STL containers. Assignment is more efficient for PODs though. Thanks for reminding me.
Juraj Blaho
Is this algorithm implemented somewhere in
std or boost?
abc
This is what I always do, it works like a charm!
pList.erase(pList.begin()+i); To remove element with index i.
3 Comments
kralco626
Thanks! I didn't understand how to get an iterator to pass to the method...
Matthieu M.
one note, the behavior is undefined if the
vector contains less than i+1 elements. It's probably worth noting :)
Joe
Note that this will preserve the order of elements, and is O(n). If you don't need to preserve order, use the O(1) solution mentioned by others.
An approach to save yourself from linear complexity!
Since vector.erase() is linear complexity, I would suggest that just swap the ith element with the last element and then erase the element at the end (which is actually ith element); that way, you possibly can save yourself from linear complexity. That is just my thought!
1 Comment
vector.erase(iterator) Where iterator is the position. You can get the first element with vector.begin() and the last one with vector.end(). Just add to the iterator to get to the desired element. e.g.:
pList.erase(pList.begin()+6); to erase the 6th item.
1 Comment
Martin Meeser
it is the 7th item, isn't it? cplusplus.com
Use Vector.Erase. The complexity is linear on the number of elements erased (destructors) plus the number of elements after the last element deleted (moving).
iterator erase ( iterator position ); iterator erase ( iterator first, iterator last ); 
1 Comment
kralco626
Yes i saw this in the documentation but was still unable to figure out how to use it.