How to reduce the capacity of a std::vector

Question

Is there a way to reduce the capacity of a vector ?

My code inserts values into a vector (not knowing their number beforehand), and when this finishes, the vectors are used only for read operations.

I guess I could create a new vector, do a .reseve() with the size and copy the items, but I don't really like the extra copy operation.

PS: I don't care for a portable solution, as long as it works for gcc.

Hostelry

Just a note, reserve() doesn't necessarily reserve the exact amount you pass to it; it reserves an amount greater then or equal to the amount you pass to reserve(). – Impropriety

Note that the swap idiom does perform a copy. I don't know if GCC has an extension to release unused reserved memory. In my opinion such a method should be in the standard for vector<>. – Triplicate

Consider using a deque instead of vector. It's almost as fast as vector but does not keep data in contigous blocks and it does not need reserve() – Janis

A vector doesn't need reserve() either; it's just more efficient to do it rather than keep expanding its length as needed during push_back()s. – Giuseppe

More specific to the issue than reserve(), is that a deque doesn't need O(N) over-capacity, only O(1) over-capacity. A vector needs O(N) over-capacity when resizing itself, in order to implement the requirement that insertion at the end is amortised O(1) time. That's why deque is a good suggestion. – Monniemono

Answer 1

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.

Leandra

Yes - this is essentially a copy. AFAIK this is the only standard way to do what the OP wants. As far as a non-standard way that avoids the copy (which the OP would find acceptable), I'm not sure if GCC's STL has this (but I wouldn't be surprised if it does). – Triplicate

@avakar - yes this is guaranteed to work by the standard (see aJ's break down of what's happening). but it's also guaranteed to copy all the elements of the original vector. – Triplicate

Michael, can you point me to where it is specified, that after vector's copy-constructor is called, capacity() == size()? I just scanned through and couldn't find any such guarantee. – Hubing

There's nothing that says that capacity() == size() for any vector (except maybe a default vector - I honestly don't know if a default vector is required to have no memory reserved). Even if you reserve() for a particular number of elements, the vector class is permitted to reserve more. The swap idiom will give you the default memory allocation for the number of elements in the vector - that might in fact be more than the absolute minimum amount of memory that would be required to hold that many objects. But there's no way to control that. – Triplicate

Right, my point is that the copy of the original vector can preallocate as much memory as the original one (i.e. an implementation where vector(v).capacity() == v.capacity() always holds can still be compliant). Without capacity() == size() guarantee (or at least some sort of capacity() < size() + k guarantee), vector<T>(v).swap(v) may in fact cause no shrinking at all. – Hubing

For what it's worth, the approach outlined in this answer is the way Stroustrup says to do it in his "The C++ Programming Language" book. – Hora

Also for what it's worth, Scott Meyer's "Effective STL" also says that this approach is the way to go. @Michael Burr: I'm pretty sure in the same book, he mentions that a default vector might have a size (for example, some implementations have a few "inline" elements for speed, I think). – Manvil

What about std::vector<T> temp; std::swap(temp, v);? Is the member swap more efficient somehow? – Liking

@aj and avakar, on mac os 10.15 and via clang / xcode i made extensive tests with swap and it never reduced the actual size... – Leix

Answer 2

With C++11, you can call the member function shrink_to_fit(). The draft standard section 23.2.6.2 says:

shrink_to_fit is a non-binding request to reduce capacity() to size(). [Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note]

Obtain

Answer 3

Go look at Scott Meyers Effective STL item 17.

Basically you can't directly reduce the storage size of a std::vector. resize() and reseve() will never reduce the actually memory footprint of a container. The "trick" is to create a new container of the right size, copy the data and swap that with the current container. If we would like to clear a container out this is simply:

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

If we have to copy the data over then we need to do the copy:

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

What this does is creates a new vector with the data from the old one, doing the copy that would be required in any operation that has the effect you need. Then calling swap() will just swap the internal buffers between the objects. At the end of the line the temporary vector that was created is deleted, but it has the guts from the old vector and the old vector has the guts from the new copy that is the exact size we need.

Velutinous

on mac os 10.15 and via clang / xcode i made extensive tests with swap and it never reduced the actual size... – Leix

Answer 4

The idiomatic solution is to swap with a newly constructed vector.

vector<int>().swap(v);

Edit: I misread the question. The code above will clear the vector. OP wants to keep the elements untouched, only shrink capacity() to size().

It is difficult to say if aJ's code will do that. I doubt there's portable solution. For gcc, you'll have to take a look at their particular implementation of vector.

edit: So I've peeked at libstdc++ implementation. It seems that aJ's solution will indeed work.

vector<int>(v).swap(v);

See the source, line 232.

Hubing

Note - this releases the memory for the vector - but it also removes all the elements (since you're swapping with an empty temporary vector). – Triplicate

Answer 5

No, you cannot reduce the capacity of a vector without copying. However, you can control how much new allocation growth by checking capacity() and call reserve() every time you insert something. The default behavior for std::vector is to grow its capacity by a factor of 2 every time new capacity is needed. You can growth it by your own magic ratio:

template <typename T>
void myPushBack(std::vector<T>& vec, const T& val) {
    if (vac.size() + 1 == vac.capacity()) {
        vac.reserve(vac.size() * my_magic_ratio);
    }

    vec.push_back(val);
}

If you're into a bit hacky techniques, you can always pass in your own allocator and do whatever you need to do to reclaim the unused capacity.

Branca

Answer 6

I'm not saying that GCC couldn't have some method for doing what you want without a copy, but it would be tricky to implement (I think) because vectors need to use an Allocator object to allocate and deallocate memory, and the interface for an Allocator doesn't include a reallocate() method. I don't think it would be impossible to do, but it might be tricky.

Triplicate

I think that it would be impossible for the vector container, since the elements are required to be contigious in memory. I haven't realized that allocators only had .allocate() and .deallocate(), so I guess this is the reason why such functionality does not exist. – Hostelry

The realloc() function is easy in C, but when you start adding more semantics to memory allocation it gets more complicated. I think that's why there is no counterpart in C++. – Giuseppe

Answer 7

If you're worried about about the overhead of your vector then maybe you should be looking to using another type of data structure. You mentioned that once your code is done initializing the vector it becomes a read only process. I would suggest going with an open ended array that will allow the program to decide its capacity at compile time. Or perhaps a linked list would be more suitable to your needs.
Lemme know if I completely misunderstood what you were getting at.

-UBcse

Foretopgallant

Other data structures have more overhead in case you have only very few elements. If have a case where I need millions of containers. std::vector needs significantly less memory in this case. – Obloquy

Answer 8

Old thread, I know, but in case anyone is viewing this in the future.. there's shrink_to_fit() in C++11 but since it is a non-binding request, the behaviour will depend on its implementation.

See: http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

Gula

Answer 9

I'm not an expert in C++,but it seems this solution works(atleast compiling it with g++ does):

std::vector<int>some_vector(20);//initial capacity 10
//first you gotta resize the vector;
some_vector.resize(10);
//then you can shrink to fit;
some_vector.shrink_to_fit();
//new capacity is 10;

Refill

Answer 10

This also works:

Try it online!

v = std::vector<T>(v); // if we need to keep same data
v = std::vector<T>(); // if we need to clear

It calls && overload of = operator, which does moving, same overload is used by swap().

Chrisman

Answer 11

Get the "Effective STL" book by Scott Myers. It has a complete item jus on reducing vector's capacity.

Footpath