Thread: Question about erase()

  1. #1
    Registered User Sharke's Avatar
    Join Date
    Jun 2008
    Location
    NYC
    Posts
    303

    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!

  2. #2
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    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 am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  3. #3
    Registered User Sharke's Avatar
    Join Date
    Jun 2008
    Location
    NYC
    Posts
    303
    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?

  4. #4
    Registered User valaris's Avatar
    Join Date
    Jun 2008
    Location
    RING 0
    Posts
    507
    Quote Originally Posted by Sharke View Post
    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\

  5. #5
    Registered User Sharke's Avatar
    Join Date
    Jun 2008
    Location
    NYC
    Posts
    303
    Ah! Thanks.

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Basically, overall you'll need to call both constructors and destructors manually.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.
    Last edited by Daved; 06-09-2009 at 10:17 PM.

  8. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    The safest assumption is that deallocation never occurs. You should program for the worst case, when behavior is not specified.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  2. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  4. Question about linked lists.
    By cheeisme123 in forum C++ Programming
    Replies: 6
    Last Post: 02-25-2003, 01:36 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM