# Thread: Can reducing a vector's size cause a reallocation?

1. ## Can reducing a vector's size cause a reallocation?

In page 456 of TC++PL, Stroustrup says "When a vector is resized to accomodate more (or fewer) elements, all of its elements may be moved to new locations." I know that if the size is increased, then a reallocation will happen if the capacity is exceeded. But I thought this could never happen if the size is decreased, say by pop_back(). I have an algorithm which grows a vector by a sequence of push_back()s and pop_back()s, with a known upper bound N to the size, and would like to do
Code:
```  vector<T> v;
v.reserve(N);```
followed by a sequence of push_back()s and pop_back()s such that the size is always between 0 and N. Can there ever be a reallocation? If not, any idea what Stroustrup was talking about?

2. Originally Posted by robatino
followed by a sequence of push_back()s and pop_back()s such that the size is always between 0 and N. Can there ever be a reallocation? If not, any idea what Stroustrup was talking about?
Stroustrup means exactly what he said. What part of it isn't clear?

3. It's like realloc(); it can move its memory block even when resizing to a smaller size.

Think of it this way. Why keep memory allocated if you're not using it? Especially if the vector used to have, say, a million elements and now it has three.

Then consider this: if you make a memory block smaller, and there's space for it earlier in memory, why not move the block there? You would decrease memory fragmentation. Of course, if the block grows again you'd have to move it back, but still.

4. Although your implementation may not move memory just by making the vector smaller, that doesn't guarantee that everyone else is the same.

If you assume that it can, then you won't be surprised later on.

5. My confusion is that I thought that under certain circumstances one could use reserve() to guarantee that a reallocation would not happen, so that iterators wouldn't be invalidated, for example. In particular, I thought that if one called reserve(N), then if the size is increased (say by calling push_back()), a reallocation was guaranteed to not happen until the size exceeds N. Is this true? If so, is it not true if one calls pop_back() instead?

> Although your implementation may not move memory just by making the vector smaller, that doesn't guarantee that everyone else is the same.

I don't know or care what my implementation does, I'm trying to find out what the Standard allows.

6. In particular, I thought that if one called reserve(N), then if the size is increased (say by calling push_back()), a reallocation was guaranteed to not happen until the size exceeds N. Is this true? If so, is it not true if one calls pop_back() instead?
From http://wwwasd.web.cern.ch/wwwasd/lhc...r/vec_0251.htm
void
reserve (size_type n);
Increases the capacity of self in anticipation of adding new elements. reserve itself does not add any new elements. After a call to reserve, capacity() is greater than or equal to n and subsequent insertions will not cause a reallocation until the size of the vector exceeds n. Reallocation does not occur if n is less than capacity(). If reallocation does occur, then all iterators and references pointing to elements in the vector are invalidated. reserve takes at most linear time in the size of self.
I read that to mean that as long as you keep inserting and the size does not exceed N, the vector will not be moved; but as soon as you delete an element from the vector, it thinks "you've done adding, I can start shrinking it now". Just my interpretation.

7. I can't find it in the standard, but I guess most implementations don't really let you shrink a vector (that is, make the capacity smaller). It's just too stupid to move all the data because of a pop_back.

Actually: pop_back is required to be semantically equivalent to vec.erase(vec.back()-1) and erase can only invalidate iterators from the point forward. So there's a guarantee that pop_back doesn't invalidate any iterators except for the last. And it would be too hard to shrink the capacity (reallocate) the vector while keeping this guarantee.

8. Originally Posted by anon
I can't find it in the standard, but I guess most implementations don't really let you shrink a vector (that is, make the capacity smaller).
If foo is a std::vector<T>, you can shrink its buffer (trim to size) like this:

Code:
`std::vector<T>(foo).swap(foo);`
Or to clear the vector out completely (the clear() method just empties the elements, it doesn't shrink the allocation (or at least, is not required to)):

Code:
`std::vector<T>().swap(foo);`

9. I know about the "swap trick" - I was planning to use it after constructing the vector. My motivation was to be able to get the vector to shrink in place, so that if used memory is contiguous and the container is at the top, it won't fragment the memory when it shrinks. Is it reasonable to expect this to happen? I know it won't happen with arrays if I allocate a new array of the exact size, copy, and delete the old one, since the new array will normally be at a higher address than the old one. And I don't want to call realloc() explicitly in C++. But I'm not familiar with vectors, and it's taking me a while just to understand exactly what I can and can't get away with (hence my confusion over when iterators are invalidated).

10. Originally Posted by robatino
I know about the "swap trick" - I was planning to use it after constructing the vector. My motivation was to be able to get the vector to shrink in place, so that if used memory is contiguous and the container is at the top, it won't fragment the memory when it shrinks. Is it reasonable to expect this to happen?
The chances of the container being at the top of memory are very small. You're hoping for some negligible benefit that probably never happens. Usually the allocator maintains several lists of different sized blocks. When the size of an allocation is reduced, the allocator shaves off the excess and places it on the appropriate free list. But in practice this is usually avoided because it fragments memory needlessly. It's better to pay a smaller, constant-factor memory cost that doesn't change much during program execution, than it is to risk a sudden, unpredictable out-of-memory condition due to fragmentation.

Think about it: allocation doesn't fragment memory, DE-allocation does.

11. If you are trying to shrink the capacity of the vector, it will invalidate iterators (since the only way of doing that is the swap trick, which isn't even guaranteed to work).

If you are trying to shrink the size, then Stroustrup seems to be referring to using resize to reduce the size, not pop_back. If you are worried about the cost of a reallocation, I would say it is safe to assume it won't reallocate. If you are worried about invalidating iterators, I would say it is not safe to assume it won't reallocate. I say this because if it does reallocate, your program will only crash if you are assuming the iterators aren't invalid.

12. It doesn't shrink in place (if I'm not terribly wrong) but is copied to a smaller vector (of exact required size, and then the internals of foo are swapped with that of the temporary vector. The temporary gets deleted and frees the original memory of foo. (Since there is an extra allocation, wouldn't memory get even more fragmented?)

One possible rationale vectors don't tend to shrink, is that they gained their capacity the hard way and they are not going to give it away so easily.

Calling realloc in C++, depending on the objects, is a bad idea. Definitely in relation with standard containers: you just can't manage their memory otherwise than by using their member functions.

13. Originally Posted by anon
It doesn't shrink in place (if I'm not terribly wrong) but is copied to a smaller vector (of exact required size, and then the internals of foo are swapped with that of the temporary vector. The temporary gets deleted and frees the original memory of foo. (Since there is an extra allocation, wouldn't memory get even more fragmented?)
While it is important to understand fragmentation and the ways to avoid it, the chances of you actually running into a real problem because of it are relatively slim.

One possible rationale vectors don't tend to shrink, is that they gained their capacity the hard way and they are not going to give it away so easily.
That's pretty much how I think of it. The only time you'd really want to shrink the vectors is if there are many THOUSANDS of them and they live very long lifetimes.

14. > If you are trying to shrink the capacity of the vector, it will invalidate iterators (since the only way of doing that is the swap trick, which isn't even guaranteed to work).
I should have explained, I know that the final "shrink capacity to fit" will invalidate iterators, but want to make sure that this didn't happen during the earlier phase when the vector is being built up with push/pops, since this part may use iterators (though if necessary I'll rewrite the code to use indices instead).

15. Originally Posted by brewbuck
The only time you'd really want to shrink the vectors is if there are many THOUSANDS of them and they live very long lifetimes.
Actually, this is my exact situation. There will be tens or hundreds of thousands of these containers in memory simultaneously, and I can't afford for each one to have excess capacity since I may be using most of the machine's memory. Hence the need to trim the capacity and also to avoid fragmentation. If this was C, I'd use realloc(). Since calling it explicitly is a bad idea in C++, it's time for me to figure out how to use vectors properly.