From 1727512070576961537 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,cd1ac2d60a3f06,start X-Google-Attributes: gidf78e5,public From: smeyers@aristeia.com (Scott Meyers) Subject: What the deque?! Date: 2000/06/29 Message-ID: #1/1 X-Deja-AN: 640346788 X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au Approved: Fergus Henderson , moderator of comp.std.c++ X-Trace: mail2news.demon.co.uk 962275146 mail2news:25660 mail2news mail2news.demon.co.uk Organization: Scott Meyers X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f Newsgroups: comp.std.c++ X-Complaints-To: abuse@demon.net 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 ]