7

Vectors double their size each time they run out of space when adding an element, but what about when you remove elements? say you added 800 elements to an array, and on the addition of that 800th element, the vector doubles its size to be able to hold 1600 elements. Now what if you start taking away elements to the point that its only holding say 5 or 10 elements?

will it recognize that the vector is much smaller than half the size of the space reserved for future elements and reserve less space?

Charles Hetterich
  • 171
  • 2
  • 10

2 Answers2

10

Vectors do not decrease in capacity when removing elements! This is to allow future elements to be added efficiently into the existing buffer.

Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
  • That's not the only way: `vec.resize(vec.size());` – bialpio Nov 12 '14 at 01:31
  • Please stop spreading the myth that the reduce-capacity trick is anything other than [a best-effort solution](http://stackoverflow.com/q/7829018/560648)! – Lightness Races in Orbit Nov 12 '14 at 01:37
  • I don't understand what "best-effort solution" means. – Neil Kirk Nov 12 '14 at 01:41
  • Ok I just removed that part of my answer because it adds more confusion and he didn't actually ask how to shrink it, just if it would shrink. – Neil Kirk Nov 12 '14 at 01:45
  • 1
    "_You can always rely on any iterators or pointers to the vector's elements after removing elements from the vector (apart from the removed ones of course)_." [Not really](http://en.cppreference.com/w/cpp/container/vector/erase). `erase()` invalidates iterators and references at or after the point of the erase. – AlexD Nov 12 '14 at 01:47
  • 2
    @AlexD Soon there will be no answer left. Feel free to edit the answer or post your own. I'm going to bed. – Neil Kirk Nov 12 '14 at 01:48
1

If it has already allocated a block of memory, it will continue to use it because it would be inefficient for it to free up some memory and later find it has to allocate more memory.

I always recommend writing a test snippet of code to test these sorts of things.

For example, I threw this together in 2 minutes to verify that I was telling you correct information:

#include <iostream>
#include <vector>

void printInfo(std::vector<char> &_vector)
{
  std::cout << "Size: " << _vector.size() << std::endl;
  std::cout << "Capacity: " << _vector.capacity() << std::endl;
  std::cout << std::endl;
}

int main()
{
  int numbElems = 10;
  std::vector<char> myvector;

  std::cout << "Nothing entered" << std::endl;
  printInfo(myvector);

  for (int i = 0; i < 10; i++) {
    for (int c = 0; c < numbElems; c++) {
      myvector.push_back(i);
    }
    std::cout << "Pushed " << numbElems << std::endl;
    printInfo(myvector);
  }

  for (int i = 0; i < 5; i++) {
    for (int c = 0; c < numbElems; c++) {
      myvector.pop_back();
    }
    std::cout << "Popped " << numbElems << std::endl;
    printInfo(myvector);
  }

  myvector.erase(myvector.begin(), myvector.end());
  printInfo(myvector);

  std::cout << "max_size: " << myvector.max_size() << std::endl;

  return 0;
}

If you compile and run you will see Capacity never goes down in size. Even after erase, or some of the elements are removed.

On linux you can use less to scroll through the output.

  • That does proves it on your compiler. You need to refer to spec to prove it. – Neil Kirk Nov 12 '14 at 07:42
  • Forgot to mention that. I'm using `g++` of the GNU compiler collection. Not sure how to word that correctly. But yes, it does depend on the implementation of vector. –  Nov 12 '14 at 19:42