Re: STL stack/deque

From: Leor Zolman (leor_at_bdsoft.com)
Date: 12/07/03 

Date: Sun, 07 Dec 2003 10:38:57 -0500

On Sun, 7 Dec 2003 08:32:46 -0800, "osmium" <r124c4u102@comcast.net>
wrote:

>Martijn Lievaart writes:
>
>> On Sun, 07 Dec 2003 06:44:10 -0800, osmium wrote:
>>
>> >> Vectors are optimised for random access with [] operator. Stacks use a
>> > deque
>> >> because it's more efficient. ( they can use some sort of linked list
>> >> arrangement, as opposed to a vector, which may well use a dynamically
>> >> re-allocated array so random access is fast )
>> >
>> > That sounds like idle speculation or rationalizing to me. It is hard to
>> > imagine anything more efficient that ix++ and ix--. Which is what you
>get
>> > when you model a stack using an array.
>>
>> What is the basic operation on a stack? Pushing and popping values. This
>> may require expansion of the container. For a vector this is an expensive
>> operation (the complete contents must be copied), while for dequeue it is
>> a fairly efficient operation (a new 'segment' is added).
>
>This is the kind of reasoning that would lead to an automobile with a 500
>gallon gas tank, and the commensurate reduction in gas mileage and
>acceleration. My word for that is "rationalizing". You do something and
>*then* you decide why you did it.
>

That's an interesting analogy, because I think it goes to further
support Martin's point (which I agree with). The C++ committee
characterizes the expected (required) performance of STL containers in
terms of performance guarantees, not arbitrary data structures (even
though the performance guarantees typically drive the choice of
underlying data structure.) That aspect of vectors that forces O(n)
performance when the vector has to grow is the problem; this problem
does not occur in deques. The irony is that a vector-based
implementation may actually run faster under certain circumstances
(based on how you use it), but then, you're of course free to override
the default container that stack is using.

As for the 500-gallon gas tank analogy: To me that's like using a
vector for a stack and reserving the 500 elements up front to avoid
the re-allocation problem! ;-)
        -leor

Leor Zolman
BD Software
leor@bdsoft.com
www.bdsoft.com
C++ users: Download BD Software's free STL Error Message
Decryptor at: www.bdsoft.com/tools/stlfilt.html

Relevant Pages

  • Re: OO Design induces an existential crisis
    ... First, Andy, I do not have a fixation on containers. ... We have many categories of classes in object technology. ... One of those categories is the container class. ... We can create instances of class Stack. ...
    (comp.object)
  • Re: Lets put this to rest
    ... The above is consistent with a stack; ... it leaves out the FIFO nature of a stack. ... It's a container with order applied. ... the actual policy can be left to design when that particular business ...
    (comp.object)
  • Re: stack display
    ... >>I want to display a stack but keep the elements in the stack as they were. ... > contains a protected member 'Container c', where Container is the type of ... > Bart v Ingen Schenau ... destroy the copy, leaving the original untouched. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: display stack
    ... >> Container. ... Perhaps you could derive your own stack class from ... > now when I read your posting I looked it up in the Holy Standard, ... > struct Hack: public Stack ...
    (comp.lang.cpp)