Erasing from vector

Question

I'm tried to erase all elements from a vector. In fact, I wrote that:

#include<iostream>
#include<vector>

std::vector<int> foo(std::vector<int> v)
{
    std::vector<int> result;
    std::cout << "Initial size = " << v.size() << std::endl;
    for(int i = 0; i < v.size(); i++)
    {
        std::cout << "Size = " << v.size() << std::endl;
        v.erase(v.begin() + i);
    }
    return result;
}

int main()
{
    int a[] = {1 ,2, 5, 8, 213, 2};
    std::vector<int> v;
    v.assign(a, a+6);
    foo(v);
}

DEMO

Why does that program prints

Initial size = 6
Size = 6
Size = 5
Size = 4

Where is

Size = 3
Size = 2
Size = 1

?

possible duplicate of [Erasing elements from a vector](http://stackoverflow.com/questions/347441/erasing-elements-from-a-vector) — Cory Kramer, Jun 10 '15 at 16:06
possible duplicate of [vector erase iterator](http://stackoverflow.com/questions/4645705/vector-erase-iterator) — Panagiotis Kanavos, Jun 10 '15 at 16:10
Minor nitpick shouldn't `std::vector foo(std::vector v)` be `std::vector foo(std::vector& v)` — DumbCoder, Jun 10 '15 at 16:11
This is not a duplicate of any of the questions linked above, OP is trying to [`clear`](http://en.cppreference.com/w/cpp/container/vector/clear) the vector, not erase a few elements. @St.Antario, learn how to use a debugger, it's trivial to figure out what's going on if you use one. — Praetorian, Jun 10 '15 at 16:26
You have a function `foo` that deletes every other element of a vector, so you end up with a vector that is half the size of what you started with. What's the question? — Chris Dodd, Jun 10 '15 at 18:19

score 4 · Accepted Answer · answered Jun 10 '15 at 16:07

4

After third erasure you have i == 3 and v.size() == 3 and for exits

answered Jun 10 '15 at 16:07

marom

5,064
10
14

3

Which is why one should always use iterators instead of indexes, even when working with vectors – Panagiotis Kanavos Jun 10 '15 at 16:08
@PanagiotisKanavos What do you mean should use iterators? – St.Antario Jun 10 '15 at 16:10
@PanagiotisKanavos: How do iterators help? erasing from a vector invalidates all later iterators referring to elements of the vector, so you can easily have dangling references that will cause undefined behavior when you try to use them. At least with indexes, you know you can get at that element of the vector, without undefined behavior, even if it was a different element from what you were expecting... – Chris Dodd Jun 10 '15 at 18:16
@ChrisDodd the iterator returned by erase is a valid iterator and you can capture that and use it to delete the next element. This is well defined behavior. – NathanOliver Jun 10 '15 at 18:59
@NathanOliver: Yes, but you have to go out of your way to use the iterator returned by erase, and not just increment the iterator you called erase on (as the OP's code does). – Chris Dodd Jun 10 '15 at 19:02
1

@ChrisDodd I wouldn't really call this out of the way `while (it != v.end()) { it = v.erase(it); }` – NathanOliver Jun 10 '15 at 19:06
@NathanOliver: That erases everything in the vector, rather than every other element. The equivalent to the OPs code is `for (auto i = v.begin(); i < v.end(); i++) v.erase(i);` -- which is undefined behavior, though it is likely that it will work on most implementations. – Chris Dodd Jun 10 '15 at 19:34
@ChrisDodd the OP wants to erase everything not every other thing. `'m tried to erase all elements from a vector.` – NathanOliver Jun 10 '15 at 19:37
@NathanOliver: The point is that blindly saying 'always use iterators, not indexes' is counterproductive -- it obscures the actual problem and likely leads to more problems than it solves. – Chris Dodd Jun 10 '15 at 19:50
@ChrisDodd if you noticed, the OP mixed iterators and indexes, thinking `begin()` and `end()` are indexes. If one is going to use STL containers, one should learn and use STL's constructs for looping – Panagiotis Kanavos Jun 11 '15 at 07:18

aslg · Answer 2 · 2015-06-10T16:37:47.513

You should learn to use the appropriate loop for what you want to achieve, or simply use them appropriately. You can use a for loop when you know in advance how many iterations you need to do, but be careful with how you use the index.

What you're doing inside the cycle is changing the size of the vector, so every iteration v.size() becomes smaller. When i == 3, the vector size has been reduced to 3 and the loop ends earlier than you expected.

There are some alternatives to what you want to achieve,

// Store the size of the array so it doesn't change midway in the loop
for(int i = 0, iEnd = v.size(); i < iEnd; i++)
{
    std::cout << v.size() << std::endl;
    //v.erase( v.begin() );
    v.pop_back(); // pop_back is quicker but erases from the end
}

Or

// More appropriate, since you don't even need to know the size
while ( !v.empty() ) {
    std::cout << v.size() << std::endl;
    v.pop_back();
}

In these loops I assume that you don't care about any specific elements and just want to erase them. If you do care about specific elements other answers already mention that.

But really you should be using

v.clear();

because the STL already does that for you.

score 1 · Answer 3 · answered Jun 10 '15 at 16:11

To remove all elements from a vector use std::vector::clear

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    std::vector<int> v(10);
    cout << v.size() << endl;
    v.clear();
    cout << v.size();
    cin.get();
    return 0;
}

Phil · Answer 4 · 2015-06-10T19:34:27.347

1

Because after the 3 erasures (when Size = 4), v.size() is 3 and i is 3, so i < v.size() is no longer true and you break out of the for loop, for(int i = 0; i < v.size(); i++) and return from the function.

If you just want to erase all elements of a vector, try v.clear().

edited Jun 10 '15 at 19:34

answered Jun 10 '15 at 16:12

Phil

5,822
2
31
60

Vlad from Moscow · Answer 5 · 2015-06-10T16:32:02.290

You can understand the problem easy if you consider this abstract loop

size_t N = v.size();

size_t i = 0;
size_t j = N;


while ( i < j )
{
   i++;
   j--;
}

Thus you will delete exactly ( N + 1 ) / 2 elements in the vector or more precisely ( v.size() + 1 ) / 2 elements .:)

To remove all elements in the vector you could use member function clear().

if you want to remove elements of the vector selectively you could write

for ( auto it = v.begin(); it != v.end(); )
{
    if ( need_to_delete ) it = v.erase( it );
    else ++it;
}

where need_to_delete is any condition you want to use.

score 1 · Answer 6 · answered Jun 10 '15 at 16:24

When the 1st element is deleted v.size() is also updated.So when it reaches size 3 its size is also 3 so it exits the for loop.

Note: try not to use the update condition (the middle condition of for loop ) as something that changes as the loop proceed unless you are sure about doing it.

kfsone · Answer 7 · 2015-06-10T19:53:12.930

You may be aware of the concept of "iterator invalidation", and you are using size_t i to avoid this. Unfortunately, what you're using is still essentially an iterator and erasing an element from a vector invalidates all iterators not just the ::iterator typed ones :).

invalidate is a carefully chosen term that has subtle nuances. It implies that the iterators didn't stop working, and that you may sometimes find they still work. But you shouldn't trust them to.

So invalidate doesn't mean they are broken or wrong, it means that you should reconsider them. For example, if you have captured vec.begin() and you have caused the vector to relocate it's data, the value of vec.begin() may no-longer be valid. It typically isn't, but you've been warned :)

std::vector is implemented over a simple contiguous array:

[  0  ][  1  ][  2  ][  3  ]

When you erase an element, the object it contains is destructed and then all of the elements to the right are moved left, physically resituated in memory.

[  0  ][~~~~~][  2  ][  3  ] sz=4
[  0  ][  2  <<  2  ][  3  ] sz=4
[  0  ][  2  ][  3  <<  3  ] sz=4
[  0  ][  2  ][  3  ][?????] sz=4

Then the vector reduces size by the count of elements removed, in this case 1:

[  0  ][  2  ][  3  ] sz=3

You can see that the overall process of erase(), then, is expensive when the objects are not simple or when the vector is large, but I'll come back to that.

The problem with your implementation is that you increase i, and the size shrinks, so you wind up deleting every second element.

  i=0
[  0  ][  1  ][  2  ][  3  ] sz=4

erase(i);
  i=0
[~~~~~][  1  ][  2  ][  3  ] sz=3
[  1  <<  1  ][  2  ][  3  ] sz=3
[  1  ][  2  <<  2  ][  3  ] sz=3
[  1  ][  2  ][  3  <<  3  ] sz=3
[  1  ][  2  ][  3  ][?????] sz=3
[  1  ][  2  ][  3  ] sz=3
  i=0

i++;
         i=1
[  1  ][  2  ][  3  ] sz=3

erase(i);
         i=1
[  1  ][~~~~~][  3  ] sz=3
[  1  ][  3  <<  3  ] sz=3
[  1  ][  3  ][?????] sz=3
[  1  ][  3  ] sz=2
         i=1

i++;
               i=2
[  1  ][  3  ] sz=2

break;

std::vector provides clear to empty an array, but if you are interested in understanding how to perform such an operation yourself:

Option 1: delete from back

while (!vec.empty())
    vec.pop_back();

What this does is destruct the last element and then reduce size. It's very cheap.

[  0  ][  1  ][  2  ][  3  ] sz=4
pop_back();
[  0  ][  1  ][  2  ][~~~~~] sz=4
[  0  ][  1  ][  2  ] sz=3

Option 2: Erase a range of elements

std::vector<int> vec { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
vec.erase(vec.begin() + 2, vec.begin() + 5);
vec.erase(vec.begin(), vec.end());

Option 3: Shrink the array:

vec.resize(0);

Option 4: Clear

This is the preferred and normal way to empty a vector

vec.clear();

Erasing from vector

7 Answers7