Question about erase()

When erase() is called on a vector for instance, what happens in terms of memory deallocation?

I'm doing an exercise question which is based on a simplified user-implementation of the vector container and it's gotten me to implement an erase() operation for the container based on the standard erase(). So I've written an erase() which takes a single iterator and overloaded it to take a range and they erase the required elements OK.

But I'm wondering what to do about deallocating memory after the erase. This container takes a simplified approach to allocation: once preallocated memory is exhausted, a new amount is allocated which is twice the current size. I'm guessing this isn't how the library vectors work though??

My question is, is it an acceptable strategy to deallocate all of the unused memory after every erase(), or is this too inefficient? Should I for instance wait until the unused memory consists of more than half the total memory before deallocating it (which would I guess be the opposite of the allocation strategy)? Or am I barking up entirely the wrong tree? This is all new ground for me!

You could take a peek at the <vector> header file and see what it does; but as far as I know, it never deallocates memory until the vector is destroyed or until you use the swap trick.

I'm prone to take your word for it, especially since that makes my life a lot easier at this point!

Hmm, not sure I'm up to peeking at library headers yet. It's embarrassing to admit but I don't even know where to find them. Do you know where I can find them in VC++ Express?

Quote:

---

Originally Posted by Sharke

I'm prone to take your word for it, especially since that makes my life a lot easier at this point!

Hmm, not sure I'm up to peeking at library headers yet. It's embarrassing to admit but I don't even know where to find them. Do you know where I can find them in VC++ Express?

---

using VC just right click on the header and click open header, otherwise you can find them under Program Files\Microsoft Visual Studio 8/9\

Ah! Thanks.

Basically, overall you'll need to call both constructors and destructors manually.

The "official" answer to these types of questions comes from the C++ standard. It determines when the vector is required or not allowed to allocate and deallocate. In many cases it doesn't provide detailed requirements, so it is up to each implementation. This can make it dangerous to check the header of your library implementation, because another library implementation might be different.

As to this question, I'm not entirely sure what the standard says. It might guarantee that no deallocation occurs (to preserve the validity of pointers and iterators to elements before the erased item) or it might simply leave it open ended so that implementation can do whatever they want.

My guess is that cpjust is right and implementations do not deallocate during an erase because that would change the capacity, but that cannot be guaranteed unless the standard guarantees it.


>> I'm guessing this isn't how the library vectors work though??
Yes, actually that is a basic version of how many vector implementations work.

>> is it an acceptable strategy to deallocate all of the unused memory after every erase()
I don't think so, I'd never deallocate unless the user requests it.

The safest assumption is that deallocation never occurs. You should program for the worst case, when behavior is not specified.

A vector will never give up space unless you empty it completely. This is a direct effect of the wording of the standard and any vector that releases memory on erase when it's not empty is broken.
I think most implementations don't release memory even when they're completely empty.