Can reducing a vector's size cause a reallocation?

This is a discussion on Can reducing a vector's size cause a reallocation? within the C++ Programming forums, part of the General Programming Boards category; From my interpretation of the standard, it appears that you should be guaranteed that no reallocation will occur if you ...

  1. #16
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    From my interpretation of the standard, it appears that you should be guaranteed that no reallocation will occur if you have already called reserve and are using push_back and pop_back only.

    I believe this is the case because it guarantees that once reserve is called, no reallocation will occur on insertion until the size needs to surpass the capacity. It also states that pop_back is the same as a call to erase on the last element, and erase only invalidates iterators and references after the element that is erased. Put those together and I think it's guaranteed that you can pop_back safely.

  2. #17
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by Daved View Post
    From my interpretation of the standard, it appears that you should be guaranteed that no reallocation will occur if you have already called reserve and are using push_back and pop_back only.

    I believe this is the case because it guarantees that once reserve is called, no reallocation will occur on insertion until the size needs to surpass the capacity. It also states that pop_back is the same as a call to erase on the last element, and erase only invalidates iterators and references after the element that is erased. Put those together and I think it's guaranteed that you can pop_back safely.
    Thanks, Daved. That's what I suspected, but what Stroustrup said confused me. I think he was just talking about calling resize() exclusively. But I still don't understand why using resize() to REDUCE the size should be capable of causing a reallocation, if the capacity doesn't change (or can it?).

    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?)
    I was hoping that since the swap trick is a common idiom (and at present the simplest way of doing what it does), the compiler would recognize what it's being asked to do, and avoid actually creating the temporary, instead just copying the contents of v to wherever it wants to (possibly shrinking it in place).

    Edit: And if it's not smart enough, that's a really good argument for a vector member function that does this, to make it clear.
    Last edited by robatino; 04-12-2007 at 01:46 AM.

  3. #18
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    >> That's what I suspected, but what Stroustrup said confused me.
    I agree, what he says is confusing. My guess is that there is no guarantee either way for resize()-ing smaller, so to be safe he added the (or fewer) part. You could always ask him, he tends to answer emails, although maybe a search of comp.lang.c++.moderated might be better first.

    >> possibly shrinking it in place
    The problem is that shrinking the memory is difficult. I understand what you are hoping for, but I think you have to just bite the bullet and either leave unused capacity or allow copying of the elements.

  4. #19
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by robatino View Post
    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.
    In STL the allocation of memory for a container is decoupled from the implementation of the container itself. If you need more control over how allocation happens, you need to learn about and write a custom allocator.

  5. #20
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    However, if the vector itself doesn't release the memory, it won't really matter what the allocator does. The allocator only allocates or deallocates when the vector says to, and in this case the problem is that the vector is not releasing the memory when you want to shrink it.

    I guess it is possible that you could come up with other workarounds via a custom allocator, but only if the situations were right.

Page 2 of 2 FirstFirst 12
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, 05: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21