From -4735336431709810720 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,cd1ac2d60a3f06 X-Google-Attributes: gidf78e5,public From: "Bill Wade" Subject: Re: What the deque?! Date: 2000/06/30 Message-ID: <8jfqk4$grk@library1.airnews.net>#1/1 X-Deja-AN: 640533961 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.2919.6600 X-Complaints-To: abuse@demon.net X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au X-Trace: mail2news.demon.co.uk 962309567 mail2news:22540 mail2news mail2news.demon.co.uk Organization: Neosoft (using Airnews.net!) X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-MSMail-Priority: Normal Abuse-Reports-To: abuse at airmail.net to report improper postings Newsgroups: comp.std.c++ "Scott Meyers" 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 implementation should usually perform about as well as the better of circular vector, vector, 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). 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. 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 or vector, use deque instead. It may be faster and is certainly easier to use. Herb Sutter has given examples where stack > was better than stack >, 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 ]