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

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    835

    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. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by robatino View Post
    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. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by anon View Post
    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. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by robatino View Post
    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. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by anon View Post
    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. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > 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. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by brewbuck View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  2. Reducing the size of compiled file
    By Diablo84 in forum C++ Programming
    Replies: 11
    Last Post: 04-07-2005, 04:00 PM
  3. Converting byte arrays to vectors
    By kasun in forum C++ Programming
    Replies: 3
    Last Post: 03-02-2004, 10:31 AM
  4. byte arrays & vectors
    By kasun in forum C++ Programming
    Replies: 1
    Last Post: 02-29-2004, 09:10 AM
  5. File Size and File Size on Disk
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 12-15-2001, 08:03 PM