Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does std::stack use std::deque by default?

Since the only operations required for a container to be used in a stack are:

  • back()
  • push_back()
  • pop_back()

Why is the default container for it a deque instead of a vector?

Don't deque reallocations give a buffer of elements before front() so that push_front() is an efficient operation? Aren't these elements wasted since they will never ever be used in the context of a stack?

If there is no overhead for using a deque this way instead of a vector, why is the default for priority_queue a vector not a deque also? (priority_queue requires front(), push_back(), and pop_back() - essentially the same as for stack)


Updated based on the Answers below:

It appears that the way deque is usually implemented is a variable size array of fixed size arrays. This makes growing faster than a vector (which requires reallocation and copying), so for something like a stack which is all about adding and removing elements, deque is likely a better choice.

priority_queue requires indexing heavily, as every removal and insertion requires you to run pop_heap() or push_heap(). This probably makes vector a better choice there since adding an element is still amortized constant anyways.

like image 408
Greg Rogers Avatar asked Sep 19 '08 14:09

Greg Rogers


People also ask

What is the default container used by std :: stack?

By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used.

Is std :: deque contiguous?

Elements in a deque are not contiguous in memory; vector elements are guaranteed to be. So if you need to interact with a plain C library that needs contiguous arrays, or if you care (a lot) about spatial locality, then you might prefer vector .

Is the std :: stack a data container?

std::stack > class stack; The std::stack class is a container adaptor that gives the programmer the functionality of a stack - specifically, a LIFO (last-in, first-out) data structure. The class template acts as a wrapper to the underlying container - only a specific set of functions is provided.

What is STD deque?

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements.


1 Answers

As the container grows, a reallocation for a vector requires copying all the elements into the new block of memory. Growing a deque allocates a new block and links it to the list of blocks - no copies are required.

Of course you can specify that a different backing container be used if you like. So if you have a stack that you know is not going to grow much, tell it to use a vector instead of a deque if that's your preference.

like image 64
Michael Burr Avatar answered Oct 03 '22 16:10

Michael Burr