Thread: deque best practices

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    deque best practices

    Hello everyone,


    This is what mentioned in the book The C++ Standard Library, section 6.3 Deques,

    --------------------
    In summary, you should prefer a deque if the following is true:

    You don't refer to elements of the container.

    It is important that the container frees memory when it is no longer used (however, the standard does not guarantee that this happens).
    --------------------

    My confusions,

    1. What means "refer to elements of the container"? We should not do that? Why -- we always refer to elements in the container? When we use iterator of deque to acccess elements in deque container, we always refer to elements of container, right? What does the author mean?

    2. I think whether deque container implementation actually free the memory when we do erase or pop or just mark it as freed to reserve for future use (e.g. insert or push) is up to implementation details, does this point to be a reason why we use deque? Confused.


    thanks in advance,
    George

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    1. It means that deque's are intended to be used by pushing and popping values. It is not a good idea to iterate over the elements of a deque, and do an operation on each element. Simply because there is no guarantee that deque operations will be implemented in a way that make such operations reasonably efficient.

    2. There are no specific requirements that erase/pop operations actually release or reallocate memory. That allows freedom for the implementer to do things in ways that make sense for the target system (eg are more "efficient", however that notion is defined). Essentially, it means that the implementer does not have to release/reallocate memory on every operation, if that gives other efficiencies.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    1) I think what is meant is "keep references for a long time", because deque's references are quite unstable.

    2) A deque may free memory that is not needed anymore. In practice, I have no idea what implementations do, but they probably will, since this could be seen as a feature.
    A vector, on the other hand, may not free memory it has allocated, unless you completely empty it, and typical implementations still won't do it then.
    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

  4. #4
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks CornedBee,


    Quote Originally Posted by CornedBee View Post
    1) I think what is meant is "keep references for a long time", because deque's references are quite unstable.
    Do you mean reference to deque object instance or iterator of deque? If you mean reference to deque object instance, I do not understand why it is not stable.

    If you mean interator of deque, I think there is nothing special for iterator of deque. Iterator of vector is also not stable when we manipulate the vector, like resize. Any comments?


    Thanks grumpy,


    Quote Originally Posted by grumpy View Post
    2. There are no specific requirements that erase/pop operations actually release or reallocate memory. That allows freedom for the implementer to do things in ways that make sense for the target system (eg are more "efficient", however that notion is defined). Essentially, it means that the implementer does not have to release/reallocate memory on every operation, if that gives other efficiencies.
    How do you understand "It is important that the container frees memory when it is no longer used" in my original question? Why important? If free memory will not improve performance, deque may defer the free, I can not see why it is important. Any comments?


    regards,
    George

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    References and iterators typically get invalidated at the same time.

    Just look at the invalidation rules. Pretty much any operation on a deque invalidates all iterators. With vector, you know that, as long as no reallocation happens, only iterators after the manipulation are invalidated.
    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

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks CornedBee,


    Quote Originally Posted by CornedBee View Post
    References and iterators typically get invalidated at the same time.

    Just look at the invalidation rules. Pretty much any operation on a deque invalidates all iterators. With vector, you know that, as long as no reallocation happens, only iterators after the manipulation are invalidated.
    1. I can understand iterator will be invalid. But, why reference to deque will be invalid?

    For example, suppose you have,

    Code:
    deque<int> qi;
    deque<int>& rqi =  qi;
    what operation on qi will make the reference rqi invalid?

    2.

    I am interested in "invalidation rules". But MSDN does not contain much information about it for each API about what will be made invalid after invoking the API. Do you have recommended online documents for that to make quick reference?


    regards,
    George

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    1) I'm talking about references to the members of the deque. So is the book. It takes an extraordinary leap of illogic to get to references to the deque object itself.

    2) The C++ standard. Or the draft for the next one - you were referred to it in another thread just now.
    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

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by George2 View Post
    How do you understand "It is important that the container frees memory when it is no longer used" in my original question? Why important? If free memory will not improve performance, deque may defer the free, I can not see why it is important. Any comments?
    This sort of thing is all about implementation trade-offs. One way of implementing the deque operations is to release and reallocate memory on every operation. Another way is to only allocate the memory once (when first needed) and for the deque to do bookkeeping and keep track of what memory it is actually using. If memory allocation is an expensive operation in comparison with the bookkeeping (and it can be on some operating systems) then the better implementation choice might be to only allocate memory once. Alternatively, if memory allocation is an inexpensive operation, the better implementation choice might be to release and reallocate.

    Similar arguments go for any standard container, which is why setting a vector size to zero is not guaranteed to release memory.

    When the container is destroyed (i.e. destructor invoked), it is guaranteed to release memory, so there is no memory leak regardless of implementation choice for other operations. Then it comes to implementation of the memory management (eg working of allocators, new/delete) and THEIR interaction with the operating system as to whether memory released by the PROGRAM is physically released .....
    Last edited by grumpy; 03-02-2008 at 04:27 PM.

  9. #9
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Hi CornedBee,


    I do not know what you mean "extraordinary leap of illogic"? Show some pseudo code please?

    Quote Originally Posted by CornedBee View Post
    1) I'm talking about references to the members of the deque. So is the book. It takes an extraordinary leap of illogic to get to references to the deque object itself.

    regards,
    George

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I do not know what you mean "extraordinary leap of illogic"? Show some pseudo code please?
    CornedBee was talking about references to the members of the deque.
    The book was talking about references to members of the deque.
    You ask why references to the deque will be invalid.
    Therefore, your question is illogical.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks laserlight,


    Quote Originally Posted by laserlight View Post
    CornedBee was talking about references to the members of the deque.
    The book was talking about references to members of the deque.
    You ask why references to the deque will be invalid.
    Therefore, your question is illogical.
    Question answered.


    regards,
    George

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. iterator for deque
    By George2 in forum C++ Programming
    Replies: 6
    Last Post: 03-06-2008, 08:17 PM
  2. Using DEQUE within Class Definition
    By wbeasl in forum C++ Programming
    Replies: 8
    Last Post: 10-07-2007, 09:50 AM
  3. Confusion with a Deque program
    By Bluefish in forum C++ Programming
    Replies: 0
    Last Post: 05-20-2006, 03:13 PM
  4. costum grow() not working
    By Opel_Corsa in forum C++ Programming
    Replies: 2
    Last Post: 02-17-2006, 10:11 PM
  5. Very slow processing of vectors?
    By Blackroot in forum C++ Programming
    Replies: 35
    Last Post: 02-06-2006, 06:36 PM