Sign in to follow this  
bengaltgrs

Shrinking a vector

Recommended Posts

I have created a vector and used push_back to add a few elements to the end, then I tried to make the vector smaller with pop_back but it still keeps the element in memory. vector<int> vec(0); vec.push_back(5); vec.push_back(6); vec.pop_back(); cout<<vec[1]; This code will output the 6 even though I already called pop_back. Why is it still in memory and how can I get rid of it? -Chris EDIT: Sorry about the name that was poped back, meant to change that before I posted it. [Edited by - bengaltgrs on March 29, 2005 8:08:39 PM]

Share this post


Link to post
Share on other sites
A C++ vector is a dynamically allocated array. Memory allocations are expensive operations. Furthermore, each time the vector class needs to reallocate its memory block (it only contains a single, continuous memory block), all the data it contains needs to be copied, which is expensive. Finally, even though you've removed an element from the vector, it still is likely that you will later put a new one in its stead.

For all those reasons, the vector class implementation tries to minimize the number of memory allocations. When the vector grows, it actually allocates more memory than needed, to prepare for later grows. You can force that with the reserve() member function, and check how many elements the vector has room allocated for with the capacity() member function. Note that the value returned by capacity() will always at least equal that returned by size(), that is, how many elements actually in the vector.

Additionally, when you remove an element from the vector, it doesn't "shrink" the allocated memory block, since that could involve a complete reallocation, depending on the behavior of your memory manager (again, configurable by the Allocator template parameter - std::vector<Element, Allocator>). So, when you remove an element, the destructor for that element gets called and the size (not capacity!) of the vector is adjusted, but that generally doesn't involve zeroing out the memory the object used to occupy. Indeed, doing so would, in most cases, be a pure waste of time: the next time that memory location is used, the constructor will put its own values in there (remember all the advice about always initializing your variables).

You cannot, however, rely on this behaviour. While accessing data beyond the size of the vector may not trigger a run-time error, it is still a logical error, a flaw in your program. Accessing data beyond the capacity of the vector is just asking for trouble. You told the computer (directly or indirectly) you were not using that memory, don't come back on your word. A program crash would be a lucky result. Data corruption a much worse problem (if you modify data that is actually used by some other part of the program...)


Now, in your particular case, an int does not have a destructor (it's a basic type, its destructor is a no-op). So the only thing that happens is that the vector's size is adjusted; the data stays there.

Now, if you really want to do a "shrink-to-fit" of your vector, that is, reduce the capacity to the vector's size (actual capacity may still be greater, since the vector may yet allocate some more extra space), you need to create a new vector and copy the data (and only the data) to it.

The way to achieve that is as follow:


vector<int> vec; // the vector containing the data

{
vector<int> tmp; // a vector that will hold the data.
tmp.assign(vec.begin(), vec.end()); // copy vec's data to tmp (and only the actual data)
tmp.swap(vec); // (quickly) exchange the contents of vec and tmp
}
// tmp, which contained vec's old contents (included the extra crud) is now destroyed



or, more succintly vector<int>(vec.begin(), vec.end()).swap(vec);, using an unnamed temporary and the vector range constructor. Using the regular copy constructor might work, but I believe the form above is the idiomatic way to achieve your goal.

Share this post


Link to post
Share on other sites
Quote:
Original post by bengaltgrs
I have created a vector and used push_back to add a few elements to the end, then I tried to make the vector smaller with pop_back but it still keeps the element in memory.

vector<int> vec(0);
vec.push_back(5);
vec.push_back(6);
gay.pop_back();
cout<<vec[1];

This code will output the 6 even though I already called pop_back. Why is it still in memory and how can I get rid of it?

-Chris


Just on the note of "it's still in memory" (Fruny has allready thouroughly detailed how to eliminate extra memory allocated...), try this little experiment:

int main ( void )
{
int * p = new int ( 10 );
delete p;
cout << *p << endl; //may still output 10, although the result is undefined.
}


Deleting an object does not magically erase the RAM inside. It could zero it all out if the implementors of C++ wanted to, but that's un-necessary*. After you've deleted it, you shouldn't access it, and therefor all zeroing it out would do is waste precious CPU cycles.

(*for necessary cleaning up we have destructors, which are called as needed)

(Oddly, my implementation of GCC does seem to zero it out)

Share this post


Link to post
Share on other sites
The result of your code is also undefined, since you're accessing the second element of a vector that only contains 1 element. It only seems to work because the vector's operator[] does not perform bounds checking. If you instead use the equivalent method at(), which differs from operator[] only in that it performs bounds checking, you will see an exception come up:


vector<int> vec(0);
vec.push_back(5);
vec.push_back(6);
gay.pop_back();

cout << vec.at(1); // exception here


-Markus-

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave Hunt
"gay.pop_back()" won't remove anything from vec. [wink]

I swear to god I posted something like that last night but now it's gone. I have a feeling Fruny deleted it.

Share this post


Link to post
Share on other sites
Yeah, there are 2 deleted posts on this thread that do actually highlight the correct problem with the original code, but were probably deleted for what appeared to be homophobic content. ;) Maybe the original poster should try using less dubious variable names in future!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this