10

iterator erase ( iterator position );

iterator erase ( iterator first, iterator last );

Erase elements Removes from the vector container either a single element (position) or a range of elements ([first,last)).

This effectively reduces the vector size by the number of elements removed, calling each element's destructor before.

and:

remove

Removes all elements equaling the given value value from the range, defined by [first, last). Removing is done by shifting the elements in the range in such a way that required elements are overwritten. The elements between the old and the new ends of the range are left intact. Iterator to the new end of the range is returned.

Is there any way to remove elements from a std::vector within an iterator range(something like remove, but ALL elements from [first, last]) without resizing the vector? I need to keep it's maximum size that it reached at runtime to prevent reallocs.

Thanks!

Mircea Ispas
  • 20,260
  • 32
  • 123
  • 211

5 Answers5

17

resize will never reduce the capacity of the vector - you can safely use erase for this.

Use reserve to make a vector preallocate space for a certain number of items. Unless you actually exceed this limit, no insert or erase or resize will lead to a realloc. If you exceed it, the vector will internally reserve more space - but it will not reduce the internal capacity.

Erik
  • 88,732
  • 13
  • 198
  • 189
  • I can't know the size. I want to make the vector to adjust its size at runtime. – Mircea Ispas Mar 31 '11 at 07:50
  • @Felics: A vector will never reduce capacity (unless you `swap`) - The capacity you reach at runtime will not go down no matter how you erase elements. A vector's `size` and `capacity` are not the same. – Erik Mar 31 '11 at 07:55
  • @Felics: A vector only reallocs when it gets too big, or when to explicitly tell to get smaller. `size` gives you the number of actual elements in the vector, while `capacity` gives you the number of elements the vector can hold without reallocating. – Björn Pollex Mar 31 '11 at 07:55
  • @Erik I know that size and capacity are not the same but I read somewhere that erase will reduce it's capacity. If it will not reduce it's capacity I will use erase – Mircea Ispas Mar 31 '11 at 07:57
  • @Space_COwbOy: I find that your comment can be misunderstood. If you call `resize()` on a vector providing a smaller size, you are *telling it to be smaller* but the vector will *not* reduce the capacity. There are no operations in a vector that allow you to reduce the capacity, the only way of achieving it is by *swapping* with an smaller copy of the vector, but I would not call that *telling the vector to get smaller*. – David Rodríguez - dribeas Mar 31 '11 at 08:07
  • @Erik : Just for the sake of pedantry, it's worth noting that in C++0x, `std::vector<>::shrink_to_fit()` will also reduce capacity. – ildjarn Mar 31 '11 at 09:15
2

I think perhaps you're misunderstanding the difference between the capacity of the vector and its size.

The capacity is how big the underlying array actually is. The size is the number of elements which are actually being used in that array.

When you call erase/remove, you're removing elements from the array and shifting items forward. However, the big array doesn't modify it's capacity. Only the size field of the vector is changed (likely just a size_t), as well as some elements being shifted around.

A simple example: Here's an int vector with a capacity of 10, and a size of 4.

| 1 | 2 | 4 | 8 | Garbage | Garbage | Garbage | Garbage | Garbage | Garbage |

Now, say we want to remove item at index 1.

The operation would resemble something like this:

  1. Destruct the item at index 1 (in this case, an integer 2)

  2. Move all elements after index 1 which are valid forward however many places are necessary to ensure there's no garbage between the start of the array and the last valid item (in this case, shift everything forward 1).

  3. Decrease the size field by how ever many items were removed (in this case, 1).

The final vector: | 1 | 4 | 8 | Garbage | Garbage | Garbage | Garbage | Garbage | Garbage | Garbage |

There was no need to re-allocate any arrays because the capacity of the vector didn't change.

I'm not entirely sure on the semantics of the shift forward operation, there may be some calls to the copy constructor/assignment operator overloads (if any) when shifting items forward.

helloworld922
  • 10,801
  • 5
  • 48
  • 85
  • You say the final vector is 1 | 4 | 8 | Garbage | Garbage | ... | But the first Garbage is actually 8. – Ogen Jul 05 '15 at 12:12
  • @Ogen I believe it is undefined behavior to assume that the first garbage has any value. It *might* have a value of 8 in every current implementation, but I certainly would not rely on this. – helloworld922 Jul 05 '15 at 17:30
1

I think you want to use the reserve function to reserve space in the vector for the required number of items.

Have a look here: http://www.cplusplus.com/reference/stl/vector/reserve/

Before you remove an item from the vector you could call reserve with the current size to keep the capacity the same.

Request a change in capacity

Requests that the capacity of the allocated storage space for the elements of the vector container be at least enough to hold n elements.

This informs the vector of a planned increase in size, although notice that the parameter n informs of a minimum, so the resulting capacity may be any capacity equal or larger than this.

When n is greater than the current capacity, a reallocation is attempted during the call to this function. If successful, it grants that no further automatic reallocations will happen because of a call to vector::insert or vector::push_back until the vector size surpasses at least n (this preserves the validity of iterators on all these future calls).

A reallocation invalidates all previously obtained iterators, references and pointers to elements of the vector.

In any case, a call to this function never affects the elements contained in the vector, nor the vector size (for that purposes, see vector::resize or vector::erase, which modify the vector size and content).

Nick
  • 25,026
  • 7
  • 51
  • 83
  • 1
    Yes, but when I call erase it will make an realloc. – Mircea Ispas Mar 31 '11 at 07:49
  • Really? Why? I would have thought it would only realloc when it wants to reduce the capacity. If you've specified a reserved size then its not going to reduce capacity and so won't realloc. – Nick Mar 31 '11 at 07:51
  • @Felics: no it won't. You need to make the distinction between `size` (the number of elements in the container) and `capacity` (the number of elements it can contain without allocating more memory). In fact, a `vector`'s capacity never shrinks (so we need to use [tricks](http://stackoverflow.com/questions/1111078/reduce-the-capacity-of-an-stl-vector) to make it fit the size), so your issue is inexistent. – Luc Touraille Mar 31 '11 at 07:54
  • @Luc Touraille I didn't know that the vector never adjust its capacity when using erase. Thanks for the info. – Mircea Ispas Mar 31 '11 at 07:59
0
iterator erase ( iterator first, iterator last );

This is what you want to do. The fact that the destructors of the elements are called has nothing to do with the maximum size (i.e. capacity) of the vector, which is usually not reduced. When you remove an element from a vector, the size of the vector (= number of contained elements) is reduced, but the capacity does not change in most cases.

Thalur
  • 1,155
  • 9
  • 13
0

std::vector isn't reducing it's capacity when reducing it's size. In fact, to shrink the capacity of a vector, you need to use the swap-with-empty-vector idiom.

ognian
  • 11,451
  • 4
  • 35
  • 33