From -4054335780878089436 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,cd1ac2d60a3f06 X-Google-Attributes: gidf78e5,public From: josuttis@my-deja.com Subject: Re: What the deque?! Date: 2000/07/02 Message-ID: <8jgh23$st$1@nnrp1.deja.com>#1/1 X-Deja-AN: 641240772 Approved: Fergus Henderson , moderator of comp.std.c++ References: X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f X-Http-User-Agent: Mozilla/4.7 [en] (X11; I; Linux 2.2.13 i686) X-Complaints-To: abuse@demon.net X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au X-Trace: mail2news.demon.co.uk 962469588 mail2news:23940 mail2news mail2news.demon.co.uk X-Http-Proxy: 1.0 x65.deja.com:80 (Squid/1.1.22) for client 212.68.79.43 Organization: Deja.com - Before you buy. X-Article-Creation-Date: Thu Jun 29 22:02:54 2000 GMT X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-MyDeja-Info: XMYDJUIDjosuttis Newsgroups: comp.std.c++ 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 , 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 ]