Re: STL list or map?

From	"MikeP" <mp011011@some.org>
Newsgroups	comp.lang.c++
Subject	Re: STL list or map?
Date	2011-06-06 09:06 -0500
Organization	A noiseless patient Spider
Message-ID	<isimu3$9fa$1@dont-email.me> (permalink)
References	<MPG.284c454a9632e28b9896b3@news.eternal-september.org><13fd8066-d507-47ad-8b55-079e25a2022a@c41g2000yqm.googlegroups.com><isi4sk$tno$2@dont-email.me><04a2fb09-0063-4ea3-b328-379a413a523f@24g2000yqk.googlegroups.com> <87boyb6yy8.fsf@dpt-info.u-strasbg.fr> <isib1r$vgo$2@dont-email.me> <9e184b8b-5aba-4751-b179-6e6921dab06d@h36g2000pro.googlegroups.com>

Show all headers | View raw

Rune Allnor wrote:
> On Jun 6, 12:44 pm, "MikeP" <mp011...@some.org> wrote:
>> Alain Ketterlin wrote:
>>> Rune Allnor <all...@tele.ntnu.no> writes:
>>
>>> [...]
>>>>> The other responder noted that a "priority list" (for lack of a
>>>>> better designation in my mind right now) may be in order, which
>>>>> may or may not be. A list that moves recently accessed elements
>>>>> to the front may be just what the application requires. Do not
>>>>> reject a list out of only the above characteristic of a simple
>>>>> list. Let the application semantics govern.
>>
>>>> Is that a list? I have seen descriptions of such functionality
>>>> in Cormen & al. The description seemed like some sort of tree
>>>> structure, that was updated after each access, to me.
>>
>>> It's called a priority queue, and usually uses a tree to guarantee
>>> O(log(N)) insertion and extraction of the highest priority element.
>>> It is included in th STL (priority_queue).
>>
>> No. A list is a list. A queue is a queue. (Notwithstanding, a queue
>> can be made from a list). I didn't mean to confuse by using
>> "priority list" (and parentheically tried to preclude potential
>> confusion and also attempted to avoid by putting it in quotes) but
>> apparently I did. I was trying to conjure up a name for a list that
>> relinks last-accessed elements to the front of the list for I don't
>> know if there is a formal name for such a beast while there indeed
>> is a name for the different animal called "priority queue".- Hide
>> quoted text -
>>
>> - Show quoted text -
>
> OK, then why not try and untangle the confusion:
>
> 1) How is the list you describe functionally and semantically
>    different from a priority queue?
>
> 2) What would the advantages be, if any, with this list compared
>    to a priority queue?

Think about what a queue is and what a list is and how their behavior is 
different and think of some examples where each is appropriately applied 
from an application point of view. Save the Big-O stuff and the like for 
exotic situations or at least AFTER thinking about the problem from the 
use case perspective. The web and search is your friend. I recommend 
Cormen's book as the best on the subject.

Thread

STL list or map? mrc2323@cox.net (Mike Copeland) - 2011-05-29 11:58 -0700
  Re: STL list or map? Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-05-29 21:37 +0200
    Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 03:52 -0500
      Re: STL list or map? Ian Collins <ian-news@hotmail.com> - 2011-06-06 21:07 +1200
        Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 05:36 -0500
          Re: STL list or map? Ian Collins <ian-news@hotmail.com> - 2011-06-07 09:53 +1200
            Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 17:38 -0500
  Re: STL list or map? Rune Allnor <allnor@tele.ntnu.no> - 2011-05-29 23:32 -0700
    Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 03:55 -0500
      Re: STL list or map? Rune Allnor <allnor@tele.ntnu.no> - 2011-06-06 02:08 -0700
        Re: STL list or map? Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-06-06 12:23 +0200
          Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 05:44 -0500
            Re: STL list or map? Rune Allnor <allnor@tele.ntnu.no> - 2011-06-06 04:23 -0700
              Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 09:06 -0500
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-06 08:29 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 11:10 -0500
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-06 14:37 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 17:22 -0500
                Re: STL list or map? Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-06 15:33 -0700
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-07 01:28 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-07 07:00 -0500
                Re: STL list or map? Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-07 14:50 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-07 06:56 -0500
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-07 00:58 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-07 06:52 -0500
                Re: STL list or map? "io_x" <a@b.c.invalid> - 2011-06-06 18:20 +0200
                Re: STL list or map? "io_x" <a@b.c.invalid> - 2011-06-07 18:10 +0200
                Re: STL list or map? Keith H Duggar <duggar@alum.mit.edu> - 2011-06-06 09:29 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 12:42 -0500
  Re: STL list or map? Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-30 00:19 -0700
  Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-05-30 01:02 -0700
  Re: STL list or map? Juha Nieminen <nospam@thanks.invalid> - 2011-05-30 11:43 +0000
    Re: STL list or map? mrc2323@cox.net (Mike Copeland) - 2011-05-30 14:07 -0700
      Re: STL list or map? Jeff Flinn <TriumphSprint2000@hotmail.com> - 2011-05-31 08:37 -0400
  Re: STL list or map? "K. Frank" <kfrank29.c@gmail.com> - 2011-06-06 17:58 -0700

csiph-web