So there I was, minding my own business, when I noticed a glazy stare aimed
in my direction.  This was bad news, because my business of late is
explaing the STL to professional C++ programmers, and a glazy stare is a
sign of a confused programmer.  In particular, a programmer who wanted to
know what one would naturally use a deque for -- why the standard raises
the comparatively obscure deque up to the heights of a vector, list, and
string.  It was a good question, and I didn't have a good answer for it.

This evening I turned to my handsome AW C++ library for deque motivation.
(One of the few perqs of being an author is that you can generally get some
free books out of it.)  I consulted -- and pardon my name dropping, but I
just can't resist -- Budd, Knuth, Musser & Saini, Josuttis, Koenig & Moo,
Breymann, Sutter, Lippman, and Stroustrup in seach of a realistic general
problem for which a deque is a natural solution.  I didn't come up with
much.  Lippman and Josuttis mention a queue, but they fail to explain why
one would prefer a std::deque to a std::queue to model a queue.  Austern
provides the obligatory description of deque's behavior and technical
strengths and weaknesses, but he then goes out of his way to discourage use
of a deque vis a vis a vector.  (In conjunction with his recent C++ Report
column, this puts Matt on record as discouraging the use of deque, set,
multiset, map, and multimap :-}) Stroustrup manages to come up with two
examples of how a deque might be used ("to model a section of a railroad or
to represent a deck of cards in a game"), but having only .3333 of his 1019
pages to devote to the topic, he provides no details.  Personally, I'm
skeptical that there are a lot of programmers modeling railroads out there,
and because most card games have a fixed number of cards, it's not clear
why a vector or (gasp!) array used as a circular buffer wouldn't be as
suitable a choice as a deque.

So I'm still stumped and the programmer's eyes are still probably glazed.
Can you help me out?  Why *is* deque so fundamental a data structure that
it made it into the standard library?  And what *are* some typical
applications for which a deque is uniquely suited?

I can describe deque's behavior and technical strengths/weaknesses until
the ruminants come home, but that's not what I need.  What I need are some
plausible examples of problems where a deque's behavior, strengths, and
weaknesses are a better match for the problems than are the other standard
containers or container adapters.

Thanks,

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Scott Meyers <smeyers@aristeia.com> wrote:

>
> I can describe deque's behavior and technical strengths/weaknesses until
> the ruminants come home, but that's not what I need.  What I need are some
> plausible examples of problems where a deque's behavior, strengths, and
> weaknesses are a better match for the problems than are the other standard
> containers or container adapters.
>

A deque is a double-ended queue. It's usually several times faster than
a linked list for the same application. It's efficient when you need to
add or delete entries from _either_ end but _not_ from the middle (which
would be the case where a linked list would be a better solution). Think
FIFO. Note that queue<> is by default built around a deque. If you used
a circular buffer, you would be limited to the fixed size of the buffer,
since growing the buffer is a painful, massive performance hit.

If you need a priority queue, by the way, the preferred solution is
still not a linked list. Instead, you usually use a heap built around a
vector. Insertion and popping the top entry involve log(heap size) swaps
(which are usually fast). Breymann's book extends the STL even further
to handle variable priorities (which rate monotonic scheduling needs).

--
Harry Erwin, PhD, <mailto:herwin@gmu.edu>,Computational Neuroscientist
(modeling bat behavior), Senior SW Analyst and Security Engineer, and
Adjunct Professor of Computer Science, GMU. Looking--CV available at:
<http://mason.gmu.edu/~herwin/CV.htm>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

in article MPG.13c481aa27f926e798970c@news.supernews.com, Scott Meyers at
smeyers@aristeia.com wrote on 6/29/00 10:38 PM:

> So there I was, minding my own business, when I noticed a glazy stare aimed
> in my direction.  This was bad news, because my business of late is
> explaing the STL to professional C++ programmers, and a glazy stare is a
> sign of a confused programmer.  In particular, a programmer who wanted to
> know what one would naturally use a deque for -- why the standard raises
> the comparatively obscure deque up to the heights of a vector, list, and
> string.  It was a good question, and I didn't have a good answer for it.

[snip]

> I can describe deque's behavior and technical strengths/weaknesses until
> the ruminants come home, but that's not what I need.  What I need are some
> plausible examples of problems where a deque's behavior, strengths, and
> weaknesses are a better match for the problems than are the other standard
> containers or container adapters.

I think you are being coy, and that the following justification for deque is
well know. Symmetry and completeness!

A queue is so useful, but practically just a special case of deque, it is
hard to imagine designing a template library that includes queue but not
deque.

(Yes, practically: it is hard to implement a container that efficiently
pushes at an end that does not also efficiently pop at that end).

Thus every application of queue is also an application of deque (granted,
other sequences could be used in place of deque to implement queue).

Even so, I get your point: it is surprising that there are so few
applications where one wants to push and pop at both ends.

Anders.

--
Anders Pytte                                   Milkweed Software
PO Box 32                                  voice: (802) 586-2545
Craftsbury, VT 05826                  email: anders@milkweed.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Scott Meyers wrote
> ...
>I can describe deque's behavior and technical strengths/weaknesses until
>the ruminants come home, but that's not what I need.  What I need are some
>plausible examples of problems where a deque's behavior, strengths, and
>weaknesses are a better match for the problems than are the other standard
>containers or container adapters.

> ...
>it's not clear
>why a vector or (gasp!) array used as a circular buffer wouldn't be as
>suitable a choice as a deque.

to model a queue in the standard there is no circular vector availiable
which handles ctors and dtors of its objects correctly. You can use a normal
vector plus rotating index, but you need to have all the objects constructed
in the vector.

a deque is the most efficient container when the number of elements changes
in a large range. vector has to copy its elements when reallocation storage,
deque dont.
so a simple queue the has to expect to contain somtimes many elements and
sometimes less, is best implemented with a deque

Stefan



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Scott Meyers wrote:

> I can describe deque's behavior and technical strengths/weaknesses until
> the ruminants come home, but that's not what I need.  What I need are some
> plausible examples of problems where a deque's behavior, strengths, and
> weaknesses are a better match for the problems than are the other standard
> containers or container adapters.

The others answered technically, let me answer practically.

A deque models certain real-world systems, e.g.

   * Politics
        o Them what's got get in line at the front.
        o Them what's not get in line at the back.
   * Airline accomodations
        o Premium customers queue to the front.
        o Coach customers queue to the rear.

Hope this helps :-)

--
Jack J. Woehr                 # Ceterum censeo
PO Box 51, Golden, CO 80402   # in herbas belli
http://www.well.com/~jax/rcfb # ab idem desistamus.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Jack J. Woehr" wrote:
>
> Scott Meyers wrote:
>
> > I can describe deque's behavior and technical strengths/weaknesses until
> > the ruminants come home, but that's not what I need.  What I need are some
> > plausible examples of problems where a deque's behavior, strengths, and
> > weaknesses are a better match for the problems than are the other standard
> > containers or container adapters.
>
> The others answered technically, let me answer practically.
>
> A deque models certain real-world systems, e.g.
>
>    * Politics
>         o Them what's got get in line at the front.
>         o Them what's not get in line at the back.
>    * Airline accomodations
>         o Premium customers queue to the front.
>         o Coach customers queue to the rear.
>
> Hope this helps :-)

Correction, which unfortunately invalidates your argument:

Premium customers go to the back of the premium queue, coach customers
go to the back of the coach queue. Attention is given first to the front
of the premium queue until it's empty, and only then to the front of the
coach queue. The same correction applies to the political example.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"James Kuyper" <kuyper@wizard.net> wrote in message news:396517B4.3D8B3159@wizard.net...
> "Jack J. Woehr" wrote:
> >
> > A deque models certain real-world systems, e.g.
> >
> >    * Politics
> >         o Them what's got get in line at the front.
> >         o Them what's not get in line at the back.
> >    * Airline accomodations
> >         o Premium customers queue to the front.
> >         o Coach customers queue to the rear.
> >
> > Hope this helps :-)
>
> Correction, which unfortunately invalidates your argument:
>
> Premium customers go to the back of the premium queue, coach customers
> go to the back of the coach queue. Attention is given first to the front
> of the premium queue until it's empty, and only then to the front of the
> coach queue. The same correction applies to the political example.

Right. Jack's systems are examples of priority queues, not deques.
(There's a priority queue in the standard library.)

I've always assumed that the reason deque is a container in its own
right is because it's a primitive. You can make a queue using a deque
internally; you can't do it the other way around. So deque is the
primitive and queue is the adapter.

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"Remember when we told you there was no future? Well, this is it."
                                                            -- Blank Reg


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Scott Meyers <smeyers@aristeia.com> wrote in message
news:MPG.13c481aa27f926e798970c@news.supernews.com...
> So I'm still stumped and the programmer's eyes are still probably glazed.
> Can you help me out?  Why *is* deque so fundamental a data structure that
> it made it into the standard library?  And what *are* some typical
> applications for which a deque is uniquely suited?

> I can describe deque's behavior and technical strengths/weaknesses until
> the ruminants come home, but that's not what I need.  What I need are some
> plausible examples of problems where a deque's behavior, strengths, and
> weaknesses are a better match for the problems than are the other standard
> containers or container adapters.

To be honest, I only use deque when I want a vector, but don't know how big
it'll be up front so can't use reserve. A non_contiguous_vector (or better
name) that used an array of arrays for it's storage but looked like a vector
would be better here if it existed.

So deque is better than all other containers if:
1) You want to insert/remove at *both* ends.
2) You need random access, or lower memory overhead than list.
3) You don't need random insert/remove.

My guess is that it's not much use on it's own, but it's very good for use
in container adapters.

My reasoning is, if there were 'raw' containers, and container interfaces
(which were adapters around the raw containers) for clients to use, then I
could imagine there would be things like

Raw: contiguous_vector, non_contiguous_vector, single_list, double_list,
hash_table, rb_tree....

Container: vector, queue, list, map, set, priority_queue...

Notice that vector, list, map and set (or something very similar) occur in
both, whereas deque is really there as raw storage container.

Sorry if I haven't helped with a decent use.

Ric





---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I don't completely understand your dismissal of queues as a valid example of
the need for a deque structure.  Granted, it is possible to implement the queue
adapter in terms of list instead of its current default, deque.  However,
although the list implementation should be more or less as efficient as deque
from a Big-O computational standpoint, it is likely that a list will require
significantly more memory.

Maybe that's a esoteric consideration these days, but I think it's still a
fairly valid rationale for the deque type.  List is really best for situations
involving constant-time insertion in the middle of the structure.  A queue
doesn't require that, thus a deque is a more suitable data structure.

-----
Gillmer J. Derge

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <MPG.13c481aa27f926e798970c@news.supernews.com>,
Scott Meyers <smeyers@aristeia.com> wrote:
>So I'm still stumped and the programmer's eyes are still probably glazed.
>Can you help me out?  Why *is* deque so fundamental a data structure that
>it made it into the standard library?  And what *are* some typical
>applications for which a deque is uniquely suited?

I can't explain why the C++ committee felt the need to raise deque's status
this way, but in general a decent reason for doing this kind of thing with
some data and control structures, even if they're not frequently used, is
because they're tricky for developers to roll their own in the instances
when they're needed.  By putting them in a standard library you remove
disincentives from using them and hopefully ensure high quality, efficient
implementations.

You could probably find good justifications for deques in Knuth or books on
data structures.

--
Barry Margolin, barmar@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Scott Meyers" <smeyers@aristeia.com> wrote

> ... it's not clear
> why a vector or (gasp!) array used as a circular buffer wouldn't be as
> suitable a choice as a deque.

A typicall deque<T> implementation should usually perform about as well as
the better of circular vector<T>, vector<T*>, and when you use deque you
don't have to write the logic to handle

  1) The circle indexing logic.
  2) resize when full.
  3) recovery of excess space when size() is much less than previous size().
  4) ownership issues (when compared to vector<T*>).
  5) lifetime (construction/destruction) of objects that are in the vector's
begin/end range, but not in your circular begin/end range.

In fact your deque<> may legally be implemented in terms of circular
vector<T*>.  Because it makes iterator's random access more complicated, I
don't know if any existing implementations actually do that.

You can probably get better performance with a circular array, but that is
often true when comparing a fixed-capacity container to a variable sized
container.

> I can describe deque's behavior and technical strengths/weaknesses until
> the ruminants come home, but that's not what I need.  What I need are some
> plausible examples of problems where a deque's behavior, strengths, and
> weaknesses are a better match for the problems than are the other standard
> containers or container adapters.

If you're considering a circular vector<T> or vector<T*>, use deque instead.
It may be faster and is certainly easier to use.

Herb Sutter has given examples where stack<deque<T> > was better than
stack<vector<T> >, although some of his timing was done on an implementation
that had taken care to optimize deque::push_back, but just called insert()
in vector::push_back (and the compiler wasn't able to recognize the
optimization available when insert(end()) was called.

=========================
> In conjunction with his recent C++ Report column, this puts Matt on record
as
> discouraging the use of deque, set, multiset, map, and multimap

When reading Matt Austern's recent article (prefer sorted vector to map),
consider that STL writers have a strong motivation to write code that is as
fast as possible.  I often have a stronger motivation to make the code more
robust against design changes and to save developer time.  As an example:

Spellchecker, design statement

  1) Read in list of valid words
  2) Tell if candidate words are in the list.

Given a choice between set and sorted vector (sort after reading all valid
words), sorted vector will probably execute faster and save space.  However
the set code has the following advantages:

  a) Code is slightly easier to write (no need to call sort()) and read.
  b) If the design statement changes to allow valid words to be
added/removed between spell-checks, the set code is easier to maintain, and
keeps its good performance.
  c) Changing the code to take advantage of an anticipated feature which may
outperform both options (like hash_set) may be easier if I use set in the
first place.

HTH



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

As I recall, Knuth uses the railroad example; so there's no help there.
However, Guru of the Week #54 is interesting:
http://216.149.30.162/resources/gotw054a.html.


Mark Wiseman


Scott Meyers <smeyers@aristeia.com> wrote in message
> So there I was, minding my own business, when I noticed a glazy stare
aimed
> in my direction.  This was bad news, ...
> ...  In particular, a programmer who wanted to
> know what one would naturally use a deque for

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <MPG.13c481aa27f926e798970c@news.supernews.com>,
Scott Meyers <smeyers@aristeia.com> wrote:
>I can describe deque's behavior and technical strengths/weaknesses
>until the ruminants come home, but that's not what I need.  What I
>need are some plausible examples of problems where a deque's
>behavior, strengths, and weaknesses are a better match for the
>problems than are the other standard containers or container
>adapters.

Well, I found it invaluable.  In general it could be used for any
intrusive queue.  In my case, I used deque for a shared queue.  With
many consumers, I maintained indices into the deque so each consumer
could read its own "front" of its queue.  After all consumers had read
past the first x elements of the deque, I could trim off that part.

Amusingly enough, I was about to implement the data structure on my
own until I ran into an in-depth discussion of deque (and thus began
my exciting foray into STL).
--
                              |  "If hard data were the filtering criterion
Mark Ping                     |   you could fit the entire contents of the
emarkp@soda.CSUA.Berkeley.EDU |   Internet on a floppy disk."
                              | - Cecil Adams, The Straight Dope Tells All

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

A queue is NO STL container. It USES STL containers and was
historically a class of the STL package.
So we have deque to provide features such as
fast insertion on both ends and random access
in a STL container as deque. A queue could never
be a STL container because of its lack of several required abilities.
Hope it helps
 Nico

In article <MPG.13c481aa27f926e798970c@news.supernews.com>,
  smeyers@aristeia.com (Scott Meyers) wrote:
> So there I was, minding my own business, when I noticed a glazy stare
aimed
> in my direction.  This was bad news, because my business of late is
> explaing the STL to professional C++ programmers, and a glazy stare is
a
> sign of a confused programmer.  In particular, a programmer who wanted
to
> know what one would naturally use a deque for -- why the standard
raises
> the comparatively obscure deque up to the heights of a vector, list,
and
> string.  It was a good question, and I didn't have a good answer for
it.
>
> This evening I turned to my handsome AW C++ library for deque
motivation.
> (One of the few perqs of being an author is that you can generally get
some
> free books out of it.)  I consulted -- and pardon my name dropping,
but I
> just can't resist -- Budd, Knuth, Musser & Saini, Josuttis, Koenig &
Moo,
> Breymann, Sutter, Lippman, and Stroustrup in seach of a realistic
general
> problem for which a deque is a natural solution.  I didn't come up
with
> much.  Lippman and Josuttis mention a queue, but they fail to explain
why
> one would prefer a std::deque to a std::queue to model a queue.
Austern
> provides the obligatory description of deque's behavior and technical
> strengths and weaknesses, but he then goes out of his way to
discourage use
> of a deque vis a vis a vector.  (In conjunction with his recent C++
Report
> column, this puts Matt on record as discouraging the use of deque,
set,
> multiset, map, and multimap :-}) Stroustrup manages to come up with
two
> examples of how a deque might be used ("to model a section of a
railroad or
> to represent a deck of cards in a game"), but having only .3333 of his
1019
> pages to devote to the topic, he provides no details.  Personally, I'm
> skeptical that there are a lot of programmers modeling railroads out
there,
> and because most card games have a fixed number of cards, it's not
clear
> why a vector or (gasp!) array used as a circular buffer wouldn't be as
> suitable a choice as a deque.
>
> So I'm still stumped and the programmer's eyes are still probably
glazed.
> Can you help me out?  Why *is* deque so fundamental a data structure
that
> it made it into the standard library?  And what *are* some typical
> applications for which a deque is uniquely suited?
>
> I can describe deque's behavior and technical strengths/weaknesses
until
> the ruminants come home, but that's not what I need.  What I need are
some
> plausible examples of problems where a deque's behavior, strengths,
and
> weaknesses are a better match for the problems than are the other
standard
> containers or container adapters.
>
> Thanks,
>
> Scott
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting
with ]
> [ your news-reader.  If that fails, use
mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting.
---               ]
> [ FAQ:
http://reality.sgi.com/austern_mti/std-c++/faq.html              ]
>
>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]