why deque is default for stack?

[t]

The stack container adaptor uses deque as its default underlying
sequential container. I don't understand why since we only add
elements and remove elements from one side of a stack. Why isn't the
default vector instead? For that matter, why not list since we don't
access elements in the middle of the stack? I don't know if it's
necessary (and don't see that it is) to do so in the implementation of
stack.

Separate question: vector cannot be used for queue adaptor because it
doesn't have push_front. (Lippman C++ Primer, 4th ed, p350). Why
would queue need push_front when we only add to the back of the queue?

Separate question: priority_queue adaptor requires random access and
so can be built using vector or deque but not list (Lippman). Why
does it require random access?

 

[Kai-Uwe Bux]

The stack container adaptor uses deque as its default underlying
sequential container. I don't understand why since we only add
elements and remove elements from one side of a stack. Why isn't the
default vector instead? For that matter, why not list since we don't
access elements in the middle of the stack? I don't know if it's
necessary (and don't see that it is) to do so in the implementation of
stack.

There is really no decisive reason. For stack sizes that are very small, it
simply won't matter at all, and for large stack sizes std::deque is
marginally more efficient memory-wise and time-wise. A typical
implementation of std::vector will have a memory overhead of about 25%
percent on average, i.e., size() will be about 75% of capacity(). Also,
push_back() in a vector is amortized constant time but will, on average,
involve more than one copy-construction. For std::deque, it is one
copy-construction per push_back(). Access to front() and back() in
std::deque are not worse than for std::vector; only random access to
elements is slightly less efficient. Of course, all this is implementation
dependent anyway. However, the standard was written with established
implementation techniques in mind.

Separate question: vector cannot be used for queue adaptor because it
doesn't have push_front. (Lippman C++ Primer, 4th ed, p350). Why
would queue need push_front when we only add to the back of the queue?

Well, you need pop_front(), which std::vector also does not have.

Separate question: priority_queue adaptor requires random access and
so can be built using vector or deque but not list (Lippman). Why
does it require random access?

Internally std:riority_queue maintains a heap. Inserting and deleting
elements from a heap requires random access.


Best

Kai-Uwe Bux

 

[Guest]

The stack container adaptor uses deque as its default underlying
sequential container. I don't understand why since we only add
elements and remove elements from one side of a stack. Why isn't the
default vector instead? For that matter, why not list since we don't
access elements in the middle of the stack? I don't know if it's
necessary (and don't see that it is) to do so in the implementation of
stack.

Yes, vector, list, and deque can all be used. Why deque was chosen as
default and not vector I do not know, but perhaps it have better
performance when performing lots of push_back and pop_back operations.

Separate question: vector cannot be used for queue adaptor because it
doesn't have push_front. (Lippman C++ Primer, 4th ed, p350). Why
would queue need push_front when we only add to the back of the queue?

Actually, from what I can see from the standard, Lippman is wrong. What
vector lack is the pop_front method, and just like you said, push_back
is used to add elements.

Separate question: priority_queue adaptor requires random access and
so can be built using vector or deque but not list (Lippman). Why
does it require random access?

The priority_queue is kept in order using the make_heap, push_heap, and
pop_heap functions, which require random access iterators.

 

[tragomaskhalos]

The stack container adaptor uses deque as its default underlying
sequential container. I don't understand why since we only add
elements and remove elements from one side of a stack. Why isn't the
default vector instead? For that matter, why not list since we don't
access elements in the middle of the stack? I don't know if it's
necessary (and don't see that it is) to do so in the implementation of
stack.

Re: list, you have this backwards I think, you wouldn't want
list precisely because you don't need to access the middle of
the stack (and list is less space-efficient than vector or deque).

Perhaps the reason deque is the default is to allow stack<bool> to
behave properly in light of the vector<bool> fiasco - e.g the "top"
method would require some special gymnastics.

 

[Kai-Uwe Bux]

There is really no decisive reason. For stack sizes that are very small,
it simply won't matter at all, and for large stack sizes std::deque is
marginally more efficient memory-wise and time-wise. A typical
implementation of std::vector will have a memory overhead of about 25%
percent on average, i.e., size() will be about 75% of capacity().

[snip]

Argh, it's late at night and I can't calculate.

a) The two percentages do not match.

b) They are probably bogus anyway. Assuming that the vector uses a simple
doubling strategy, the overhead will be larger on average due to Benford's
law. The exact math is escaping me right now.


Best

Kai-Uwe Bux

 

[Justin.SpahrSummers]

Re: list, you have this backwards I think, you wouldn't want
list precisely because you don't need to access the middle of
the stack (and list is less space-efficient than vector or deque).

std::list uses a linked list implementation, which means that access
to the middle is inefficient, but modifying the end or beginning of it
is rather quick (although, specifically, adding an item may be slower
depending on how quickly the allocator works).

 

[werasm]

The stack container adaptor uses deque as its default underlying
sequential container. I don't understand why since we only add
elements and remove elements from one side of a stack. Why isn't the
default vector instead?

I've actually wondered about this question myself. Especially because
if one used a vector, dynamic allocations will eventually stop,
whereas
"I think" with a deque, allocations/deallocations will continue.
Vector
seemed more natural for especially a stack, considering that it
only grows to one side.

Werner

 

[Kai-Uwe Bux]

I've actually wondered about this question myself. Especially because
if one used a vector, dynamic allocations will eventually stop,
whereas
"I think" with a deque, allocations/deallocations will continue.

That happens only when the length crosses a blocklength multiple. When you
use a pooling allocator (and the HP/SGI reference implementation of the STL
did), the blocks are not returned to the OS but the allocator keeps them
around for re-use by the container. In that case, reallocation of a block
previously vacated is very cheap.

Vector seemed more natural for especially a stack, considering that it
only grows to one side.

Best

Kai-Uwe Bux

 

[James Kanze]

On 2007-10-02 09:31, t wrote:

Yes, vector, list, and deque can all be used. Why deque was chosen as
default and not vector I do not know, but perhaps it have better
performance when performing lots of push_back and pop_back operations.

As Kai-Uwe pointed out, it will probably involve less copying on
the average. Although it all depends---if you're constantly
pushing and popping, presumably, the vector will reach its
maximum size fairly quickly, and after that, there will be only
one copy per push, just as with deque. (In general, however, I
think that deque is conceived as being "optimal" for pushing and
popping, even at the end, and vector is conceived as being
"optimal" for random access.)

Actually, from what I can see from the standard, Lippman is
wrong. What vector lack is the pop_front method, and just like
you said, push_back is used to add elements.

Of course, push_front and pop_front go together. If a container
implements one, it will implement the other.

 

[Kai-Uwe Bux]

Kai-Uwe Bux wrote: [snip]

A typical
implementation of std::vector will have a memory overhead of about 25%
percent on average, i.e., size() will be about 75% of capacity().

[snip]
a) The two percentages do not match.
b) They are probably bogus anyway. Assuming that the vector uses a simple
doubling strategy, the overhead will be larger on average due to Benford's
law. The exact math is escaping me right now.

I think, I figured it out.

Given a simple minded allocation strategy for std::vector that doubles the
capacity every time it needs to reallocate, we have the following:

a) The expected ratio size() / capacity() is

1
--------- approx = 0.72
2 ln(2)

So, on average about 28% of the allocated memory is unused.

b) Filling the vector by a series of push_back() operations will involve on
average

1
4 - ------- approx = 2.56
ln(2)

copy constructor calls.


(I'm just posting this, because it surprised me. I used to belive that a
capacity doubling vector uses about 2 copy constructions per pushback and
is on average 75% filled.)


Best

Kai-Uwe Bux