Hi,
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.
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.
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.
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.
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.
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.
When C++0x comes along, you can call the member function shrink_to_fit(). The draft standard section 23.2.6.2 says:
shrink_to_fitis a non-binding request to reducecapacity()tosize(). [Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note]
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
Get the "Effective STL" book by Scott Myers. It has a complete item jus on reducing vector's capacity.