Remove ith item from a C++ std::vector

Question

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);

fredoverflow · Answer 1 · 2014-09-19T08:14:34.780

88

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();

edited Sep 19 '14 at 08:14

answered Dec 14 '10 at 18:08

fredoverflow

256,549
94
388
662

7

That's clever assuming order is not important. – Martin York Dec 14 '10 at 19:39
2

An even faster version would skip the swap and instead just assign, as the last element is getting pop_backed anyway. – Ylisar Oct 13 '11 at 15:35
@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. – fredoverflow Oct 13 '11 at 16:26
Is this algorithm implemented somewhere in `std` or `boost`? – Juraj Blaho Dec 03 '13 at 13:23
This is what I always do, it works like a charm! – Moshe Rabaev Aug 28 '16 at 21:57

score 63 · Accepted Answer · answered Dec 14 '10 at 18:05

63

pList.erase(pList.begin()+i);

To remove element with index i.

answered Dec 14 '10 at 18:05

Vladimir

170,431
36
387
313

Thanks! I didn't understand how to get an iterator to pass to the method... – kralco626 Dec 14 '10 at 18:09
4

one note, the behavior is undefined if the `vector` contains less than `i+1` elements. It's probably worth noting :) – Matthieu M. Dec 14 '10 at 18:49
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. – Joe May 24 '17 at 01:25

score 15 · Answer 3 · edited Jun 20 '20 at 09:12

15

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!

edited Jun 20 '20 at 09:12

Community

1
1

answered Dec 14 '10 at 18:10

Nawaz

353,942
115
666
851

1

"vector.erase() is linear complexity" Is there a book with a tabler for such things? I keep getting an impression that such estimates need a thorough knowledge of some algorithms (but I still hope there is a table with methods complexity for each data type somewhere). Thanks. – Nov 17 '12 at 03:56

score 5 · Answer 4 · answered Dec 14 '10 at 18:08

5

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.

answered Dec 14 '10 at 18:08

Tom Johnson

497
1
7
16

1

it is the 7th item, isn't it? [cplusplus.com](http://www.cplusplus.com/reference/vector/vector/erase/) – Martin Meeser Mar 14 '13 at 12:19

score 4 · Answer 5 · answered Dec 14 '10 at 18:05

4

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 );

answered Dec 14 '10 at 18:05

Sonny Saluja

7,193
2
25
39

2

Yes i saw this in the documentation but was still unable to figure out how to use it. – kralco626 Dec 14 '10 at 18:22

Remove ith item from a C++ std::vector

5 Answers5

An approach to save yourself from linear complexity!

Linked