Reduce the Capacity of an Stl Vector

reduce the capacity of an stl vector

std::vector<T>(v).swap(v);

Swapping the contents with another vector swaps the capacity.

  std::vector<T>(v).swap(v); ==> is equivalent to 

 std::vector<T> tmp(v);    // copy elements into a temporary vector
         v.swap(tmp);              // swap internal vector data

Swap() would only change the internal data structure.

Will a std::vector's capacity ever be reduced?

So I think that a vector should reduce its capacity when its capacity is much larger than its size.

Firstly, the standard would have to specify what "capacity is much larger than its size" would mean. That would limit the choices that implementations currently have over the reallocation strategy.

Secondly, if reducing the capacity required re-allocating and moving all the remaining elements. This means that all iterators may be invalidated by an erase, which limits safe usage.

Currently, erase states

Invalidates iterators and references at or after the point of the erase, including the end() iterator.

Thirdly, a vector is just as likely to reach it's high watermark of capacity again as it is to remain small for a long time.

You would be making the usage worse for a number of valid scenarios, for the dubious benefit of releasing a large allocation. Modern virtual memory systems deal fine with old allocations sticking around strictly longer than neccecary.

So are there some conditions to trigger the reduction of its capacity?

Yes, shrink_to_fit is an explicit request to do what you want. If you do desire it to reallocate to a smaller size, you can ask for that. Other usages, which would be harmed by shinks, are unaffected.

Does vector::erase reduce vector::capacity?

Not necessarily no. When reading the C++ standard (and cppreference proxies the standard remarkably well), if something is not explicitly mentioned, then assume such a something is not required.

It would possibly be sub-optimal for a C++ Standard Library implementation to do so.

How to limit the capacity of std::vector to the number of element

How to limit the capacity of std::vector to the number of element

The best that you can do, is to reserve the required space before you add the elements. This should also have the best performance, because there are no reallocations and copying caused by it.

If that is not practical, then you can use std::vector::shrink_to_fit() after the elements were added. Of course, that doesn't help if the allocation may never peak above the set limit.

Technically, neither of these methods are guaranteed by the standard to match the capacity with size. You are relying on the behaviour of the standard library implementation.

Is shrink_to_fit the proper way of reducing the capacity a `std::vector` to its size?

Do the arguments in the quotation hold?

Measure and you will know. Are you constrained in memory? Can you figure out the correct size up front? It will be more efficient to reserve than it will be to shrink after the fact. In general I am inclined to agree on the premise that most uses are probably fine with the slack.

If yes, what's the proper way of shrinking an STL container's capacity to its size (at least for std::vector).

The comment does not only apply to shrink_to_fit, but to any other way of shrinking. Given that you cannot realloc in place, it involves acquiring a different chunk of memory and copying over there regardless of what mechanism you use for shrinking.

And if there's a better way to shrink a container, what's the reason for the existence of shrink_to_fit after-all?

The request is non-binding, but the alternatives don't have better guarantees. The question is whether shrinking makes sense: if it does, then it makes sense to provide a shrink_to_fit operation that can take advantage of the fact that the objects are being moved to a new location. I.e., if the type T has a noexcept(true) move constructor, it will allocate the new memory and move the elements.

While you can achieve the same externally, this interface simplifies the operation. The equivalent to shrink_to_fit in C++03 would have been:

std::vector<T>(current).swap(current);

But the problem with this approach is that when the copy is done to the temporary it does not know that current is going to be replaced, there is nothing that tells the library that it can move the held objects. Note that using std::move(current) would not achieve the desired effect as it would move the whole buffer, maintaining the same capacity().

Implementing this externally would be a bit more cumbersome:

{
   std::vector<T> copy;
   if (noexcept(T(std::move(declval<T>())))) {
      copy.assign(std::make_move_iterator(current.begin()),
                  std::make_move_iterator(current.end()));
   } else {
      copy.assign(current.begin(), current.end());
   }
   copy.swap(current);
}

Assuming that I got the if condition right... which is probably not what you want to write every time that you want this operation.

How to downsize std::vector?

Effective STL, by Scott Meyers, Item 17: Use the swap trick to trim excess capacity.

vector<Person>(persons).swap(persons);

After that, persons is "shrunk to fit".

This relies on the fact that vector's copy constructor allocates only as much as memory as needed for the elements being copied.

std::vector resize(0) or clear() - but keep it's capacity

Actually the clear member function keeps the vector capacity unchanged. It only destroys (calls the destructor) each of the vector elements and sets the vector size to 0.

In this situation, at each iteration, I would call clear() to destroy all the vector elements, then call the member function reserve(size) which, in the case where the vector capacity is too small, will increase it to at least size.

---

Related Topics