From 5477285399303776133 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,cd1ac2d60a3f06 X-Google-Attributes: gidf78e5,public From: "Richard Parkin" Subject: Re: What the deque?! Date: 2000/06/30 Message-ID: <8jfe6s$msv$1@suparna.cam.msi-eu.com>#1/1 X-Deja-AN: 640532729 Approved: Fergus Henderson , moderator of comp.std.c++ References: X-Priority: 3 X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2014.211 X-Complaints-To: abuse@demon.net X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au X-Trace: mail2news.demon.co.uk 962309351 mail2news:22286 mail2news mail2news.demon.co.uk Organization: Molecular Simulations, Inc - Cambridge, UK X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-MSMail-Priority: Normal NNTP-Posting-Date: 29 Jun 2000 12:07:56 GMT Newsgroups: comp.std.c++ Scott Meyers 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 ]