1

Remove first N elements from a std::vector

This question talks about removing items from a vector and 'compacting memory'. What is 'compacting memory' and why is it important here?

JCx
  • 2,689
  • 22
  • 32

3 Answers3

3

The OP is talking about shrinking the memory the vector takes up. When you erase elements from a vector its size decreases but it capacity (the memory it is using) remains the same. When the OP says

(that also compacts memory)

They want the removal of the elements to also shrink the capacity of the vector so it reduces its memory consumption.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
3

Inside the implementation of the std::vector class is some code that dynamically allocates an array of data-elements. Often not all of the elements in this internal array will be in use -- the array is often allocated to be bigger than what is currently needed, in order to avoid having to reallocate a bigger array too often (array-reallocations are expensive!).

Similarly, when items are removed from the std::vector, the internal data-array is not immediately reallocated to be smaller (because doing so would be expensive); rather, the now-extra slots in the array are left "empty" in the expectation that the calling code might want to re-use them in the near future.

However, those empty slots still take up RAM, so if the calling code has just removed a lot of items from the vector, it might want to force the vector to reallocate a smaller internal array that doesn't contain so many empty slots. That is what they are referring to as compacting in that question.

Jeremy Friesner
  • 70,199
  • 15
  • 131
  • 234
  • Wouldn't reallocation when std::vector shrinks be just freeing memory at the end of the block? This should be faster than reallocating when std::vector size increases (= possibly allocating a larger block of memory, and then copying the content). – Uri Raz Aug 17 '18 at 16:47
  • It might be faster than allocating a larger array (it depends on whether the underlying heap supports a partial-free operation). In any case, accessing the heap is more expensive than not accessing the heap, so the vector class tries to avoid doing so when possible. – Jeremy Friesner Aug 17 '18 at 17:35
2

It means that the vector shouldn't use more memory than it needs to. In other words, the OP wants:

size() == capacity()

This can be achieved in C++11 and later by calling shrink_to_fit() on a vector. This is only a request though, it is not binding.

To make sure it will compact memory you should create a new vector and call reserve(oldvector.size()).

Hatted Rooster
  • 35,759
  • 6
  • 62
  • 122