reduce the capacity of an stl 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.

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.

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]

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.

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.

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.

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.

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

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

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;

Answer 10

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

Answer 11

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().