views:

196

answers:

3
+6  A: 

This is quite a strained out, but:

Consider vector's allocator that could only allocate memory with, say, 4 KB granularity. Then it wouldn't make sense to reallocate memory if a vector had capacity of 4096 and size of 4095 as this wouldn't conserve memory, yet waste some CPU time for copying elements.

doublep
Feasible, but there's no way in the standard allocator interface to communicate this. (Unless I've missed an 0x addition?) Not reallocating if size is 4095 and capacity is 4096 could be done independently, though, and I suppose makes sense---except that I could check that if I wanted before calling shrink_to_fit.
Roger Pate
Well, one already specialized case is vector<bool>. Allocators obviously have at least 1 byte granularity and, as far as I recall, vector<bool> uses a bit per element. Really minor, though.
doublep
vector<bool> is an abomination generally agreed to be a mistake. It does cause problems if you write a template that might use bool and expect a real container interface, and I'd hope any other specializations for vector can't be similarly broken (in fact, AFAIK, the standard would forbid that).
Roger Pate
+2  A: 

The rounding ideas are indeed relevant, but rather indirectly. The question is "what optimizations are intended to be allowed." That's making some assumptions about the standardization process wrt. optimizations. In general, the intent is to allow all non-observable optimizations and then some - such as copy elision where the not-calling of the copy ctor is observable. In this case, capacity() != size() might be an observable effect of an optimization, and the standard allows it.

As for the reasons to add this latitude, I could also imagine ignoring a shrink request when capacity() is only 101% of size() - too little gains. There will never be a single precise reason, as the LWG consists of many people with many viewpoints. There just is (was) enough of a consensus that there are sufficient extra optimization opportunities created by granting this freedom.

MSalters
I do know that, in general, the standard tries to allow implementations to choose from many different and competing optimizations. Given the explicit note, however, I thought there could be some concrete ones, and hopefully more than just "you requested this action and we disagree, status: declined".
Roger Pate
A: 

While is it already special, vector <bool> has to allocate in blocks of size 8. I also know some people are working on getting malloc to return the 'true size' of any allocated blocks, so if an allocated block would have introduced unavoidable waste, instead the vector usefully uses the space.

As we move to 64-bit OSes, memory space suddenly becomes (famous last words) larger than anyone will ever get close to filling, so it becomes much more reasonable to allocate large blocks of virtual memory and fill them whenever. Moving objects around is expensive, and in practice a waste of time, as we are not moving things because physical memory is limited, just from one virtual place to another!

Chris Jefferson
How does this relate to possible optimizations enabled by shrink_to_fit being non-binding?
Roger Pate
Because if vector was forced to do shrink_to_fit, even when it had extra memory it couldn't get rid of, then it would end up rellocating, or just "rediscovering" that memory later, at cost. Better for it to be upfront and say "I can't shrink my buffer any smaller than this, without wasting memory".
Chris Jefferson