From -4297684359153957916 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,ba96c237e128ed5a X-Google-Attributes: gidf78e5,public From: Don Montgomery Subject: Re: STL priority queue search Date: 1998/07/08 Message-ID: <6o0fb8$ls6$1@news.utdallas.edu>#1/1 X-Deja-AN: 369651131 Approved: Fergus Henderson References: <6nirma$dng$2@news.utdallas.edu> <35A15612.3F54@wizard.net> <35A237D3.41C6@wizard.net> Organization: The University of Texas at Dallas X-Original-Date: 8 Jul 1998 18:55:36 GMT X-Auth: PGPMoose V1.1 PGP comp.std.c++ iQBFAgUANaPTT+EDnX0m9pzZAQGbyAF/UTg1nx8bvX3YhaWsPS0cdAIFw04uIGCJ oNOyaOULhLnF+5t4Co8muLd/HWPguiFG =7Uxz User-Agent: tin/pre-1.4-980514 (UNIX) (SunOS/5.6 (sun4u)) Newsgroups: comp.std.c++ James Kuyper wrote: : James Kuyper wrote: :> Don Montgomery wrote: :> > On 3 Jul 1998, Don Montgomery wrote: :> > !Hi, does anyone know the (a) good way to do a linear :> > !(or, for that matter, a random access) search on PQs :> > !in STL? :> > Let me re-phrase: is it possible/how do you do it: get an :> > iterator returned from a :> > :> > priority-queue >? :> > :> > (Purpose: to check for non-key flag fields in an event list, :> > with the possibility of User-defined-type deletion from the :> > priority-queue, or perhaps just setting an `invalid flag.') :> [snip] : is, it can't be a reverse-sorted list. I conclude that it is : unambiguously unsafe to remove arbitrary elements from 'c'. Flagging bad : elements should still work, however. I was actually thinking of an operation `wipe-it()' which would (a) remove the `bad' element from the heap (in O(n) time for vector, O(1) time for deque), and (b) do make_heap on what was left to restore heap properties (in O(n) time). This would not be too bad, if wipe-it() was called infrequently. I'm staring at it to try to discover where the trade-off is between (1) doing that, (2) keeping a flag list (i.e., not even doing any search, just doing a condition check for each event that is popped), and (3) searching out events, but not deleting them, just marking them to be discarded as encountered. I guess I need to get further into implementation (and cases!) to get a feeling for what's best (in my case!). Don Don Montgomery Advanced Communications Technology (ACT) Laboratory University of Texas at Dallas montgo@utdallas.edu --- [ 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 ]