-
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?
-
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.
-
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 :D
-
-
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.
-
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.
-
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?
-
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? :D )
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? :D 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
-
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.