Thread: STL container question

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    STL container question

    Just a quick question. Say I'm using a container where I am constantly adding to and taking away from, and it doesn't matter whether I add to the beginning or end, nor does it matter if I take away from the beginning or end. Also, I would never need to access any of the items in the middle. So basically among others, a stack, a queue, and a vector would all work just fine with my code. So my question is, if I can use any of them, does it matter at all which one I use in terms of efficiency, speed, memory usage, and anything else I can't think of at the moment?

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    container choice usually boils down to how the container is to be used. Tell us how you plan to use the container. Do you need fast inserts? fast deletes? fast searches? Do you need to remove elemnets in order inserted etc.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Thats just it, it doesn't really matter. I have a struct that I want to put into the container (doesn't matter which end) and the container goes through a loop that constantly looks at one element in the container (again doesn't matter which one, so basically it can look at either the front or the back, the last one entered or the first one entered) and based off the information in that struct does calculations which could possibly add more into the container. It then pops the struct it just looked at and continues with the loop. This continues until the container is empty.

    Like I said, a vector, queue, or stack could all just as easily accomplish this. I just wasn't sure if all one wanted to do was push, pop, and analyze an arbitrary end (could be solely the front or back, doesn't make a difference) if the choice of containers mattered

    Hope this makes sense

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    use a vector then.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    But is there a reason why a vector would be better? If a stack or queue could easily accomplish the task, it just seems like a vector with its added (and not needed in this case) features might slow some of the container operations down.

  6. #6
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    stack and queue are both adapters for other containers. vector is likely to be most efficient of the 3. if you are careful you can avoid reallocations in the vector by use of reserve.You will also have the added benefit of random access iterators giving you the full range of algorithms at your disposal.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  7. #7
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Cool, thanks! One last question though (I promise!), if a vector is probably more efficient, why would one ever use a stack? It seems like a vector has all the same operations - and more - as a stack, and if its more efficient as well, I'm not sure why a stack should ever be used. Maybe only for readability and clarity?

  8. #8
    Registered User
    Join Date
    Apr 2002
    Posts
    362
    Sounds to me like you may be looking more toward a 'deque' than a vector since you may want to 'push' and/or 'pop' at either end. (You just knew someone would throw some garbage into the game, didn't you? )

    Back to your question, though. Since, as Stone_Coder has explained, stacks and queues (and priority_queues) are 'container adapters', they are restricted interfaces to containers (vectors, lists and deques). ('deque' is pronounced 'deck', by the way...thank you, Mr. Stroustrup.)

    A vector isn't more efficient than a stack. More functional? Yes, but not more efficient. Think of a 'stack' as a "subset" of a vector...or list...or deque. A stack object is simply "stripped" of the functionality of the container and left with only top(), push() & pop().

    Why would you choose to use a stack? That depends on your application - nice 'weasel' job on my part, right? Actually, it really doesn't make a lot of difference since, when you instantiate a 'stack' object, the default container is a 'deque'. (Remember that a 'stack' is an adaptor, not a container.)

    Bottom line, use a 'deque'. Push to the front or back, pop from the front or back and, no (in)efficiency problems in the middle, based on your original post.

    P.S. What happened to the 'vector'? Hey, vectors aren't the only containers in the STL!

    -Skipper
    "When the only tool you own is a hammer, every problem begins to resemble a nail." Abraham Maslow

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Thanks for the help. Haven't really used dequeue's yet, but only because I haven't come across a problem where I might want to do both sides of the container. The problem I stated doesn't really need both, I just wanted to show that it could be a FIFO or FILO without changing anything, no real reason to NEED access to both sides at the same time.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. swap function of STL container
    By George2 in forum C++ Programming
    Replies: 11
    Last Post: 03-29-2008, 02:53 AM
  2. Writing my own stl container
    By curos in forum C++ Programming
    Replies: 10
    Last Post: 12-18-2005, 04:33 AM
  3. STL List container with classes
    By Rune Hunter in forum C++ Programming
    Replies: 10
    Last Post: 10-25-2005, 02:13 PM
  4. im extreamly new help
    By rigo305 in forum C++ Programming
    Replies: 27
    Last Post: 04-23-2004, 11:22 PM
  5. question about STL
    By free2run in forum C++ Programming
    Replies: 2
    Last Post: 12-16-2002, 12:12 PM