2

We know that the standard container class templates deque and list can be used to implement queue and +vector to implement stack. But, what are difference between these two implementation, if we always use the same methods to access and also can not access arbitrary elements using at() or [] as we do it with deque (vector).

Beibut Amirgaliyev
  • 21
  • 4
  • possible duplicate of [STL Containers - diffrence between vector, list and deque](http://stackoverflow.com/questions/9650254/stl-containers-diffrence-between-vector-list-and-deque) – Bo Persson Mar 11 '12 at 15:57

1 Answers1

6

The container adaptors, such as stack and queue, are implemented using a specific subset of operations - any container that will be used with a particular adaptor must support all of the operations that the adaptor requires.

vector cannot be used with the queue container adaptor because:

Any sequence supporting operations front(), back(), push_back() and pop_front() can be used to instantiate queue.

And vector doesn't support pop_front().

vector, deque or list can be used with stack because all three of these containers support the operations that stack requires:

Any sequence supporting operations back(), push_back() and pop_back() can be used to instantiate stack.

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
  • Note: `vector` does not support `pop_front` because there it cannot (really) be implemented efficiently. – Matthieu M. Mar 11 '12 at 15:48
  • Excuse me, but I haven't taken an answer for my question. I am not asking you why these containers groupped together. Question is: if i create queue using STL's queue Q, I created queue with name Q which will be implemented using Deque, if I write queue) QL I use linkedlist implementation. But, what are difference, if you use both of them in the same way and I suggest that time complexity is the same? – Beibut Amirgaliyev Mar 11 '12 at 17:08
  • @Beibut: I'm sorry, I guess I didn't understand the question. As far as time complexity goes, the operations the container adapters use are all required to have "amortized constant time" (C++03 23.1.1/12) on the underlying containers. So there's no complexity difference caused by using one container or another. Of course, that doesn't mean the performance will necessarily be the same. – Michael Burr Mar 11 '12 at 20:57