Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #5806 > unrolled thread

STL list or map?

Back to article view | Back to comp.lang.c++

Contents

  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

Page 1 of 2  [1] 2  Next page →

#5806 — STL list or map?

   I have the following structure defined, and I'm trying to decide the 
best container to use for accessing specific elements: "best" meaning 
the fastest way.  I will be searching on the "sBibNo" field, and it will 
likely contain values in a high range (20000-50000).  The elements 
stored will not be contiguous.  I can't allocate an array of elements 
because doing so would waste a lot of memory space...so I can't use a 
direct index to find the elements.
   I'm thinking I could use either an STL list or map for this 
application, but I fear the list processing would be prohibitively slow 
and the map might be quite wasteful in other ways.  The actual number of 
elements used in this application probably won't exceed 3000.
   Please advise.  TIA

struct SHADOWS
{
	char sRCode, aRCode;
	int  sBibNo, aBibNo;
} 

[toc] | [next] | [standalone]

#5810

Mike Copeland wrote:

>    I have the following structure defined, and I'm trying to decide the
> best container to use for accessing specific elements: "best" meaning
> the fastest way.  I will be searching on the "sBibNo" field, and it will
> likely contain values in a high range (20000-50000).  The elements
> stored will not be contiguous.  I can't allocate an array of elements
> because doing so would waste a lot of memory space...so I can't use a
> direct index to find the elements.
>    I'm thinking I could use either an STL list or map for this
> application, but I fear the list processing would be prohibitively slow
> and the map might be quite wasteful in other ways. 

Memory: A list node contains the data and typically two pointers. Very 
likely, the underlying allocator is also putting in a hidder pointer. That 
is three pointers in addition to your data. A map node typically contains 
three pointers and the hidden pointer in addition to the data. Taking into 
account that the allocator is likely to round sizes to multiples of 16 or 32 
bytes, you are somewhat unlikely to see a difference.

Cost of iteration: incremening / decrementing an iterator is constant time 
for a list and ammortized constant time for a map.

> The actual number of
> elements used in this application probably won't exceed 3000.
>    Please advise.  TIA
[...]

Elsethread, the suggestion was made to hide this decision as an 
implementation detail of some class. That is a good idea.

If you choose a list representation, then a lot will depend on which pattern 
of searches predominates in your application. E.g., if there is a 
comparatively small set of keys that you will search for very often, then a 
"self organizing file" might be a good idea: you always search from front to 
tail and when you dfind a key, you move the entry to the head of the list. 
This way, frequently searched entries gather near the front and will be 
found quickly.

If your searches are more or less evenly distributed among the keys, a 
better data structure would probably improve performance of searching. The 
tradeoff is usually a slightly greater complexity for inserting an entry. 
Whether changing the data structures pays off, therefore, also depends on 
whether your application will search way more often than it will modify the 
underlying data.

As the influencing factors are hard to predict, you should write your 
program so that it will be easy to change the data structure. Then, 
implement one that you can easily prove correct. Create unit tests. When you 
change the data structure, those tests will catch bugs. Once the other data 
structure is up and running, you can compare performance.


Best,

Kai-Uwe Bux

[toc] | [prev] | [next] | [standalone]

#6267

Kai-Uwe Bux wrote:

> Elsethread, the suggestion was made to hide this decision as an
> implementation detail of some class. That is a good idea.

I don't think that it is. This is the perfect opportunity for the OP to
learn about applying the correct container/algo by taking the required
amount of time to do so. Unnecessary abstraction just delays the decision
and gives the application unnatural semantics and stifles the
programmer's level of capability. Use the right tool for the job. Don't
just use a hammer for expediency. The way to proceed is in recognizing
the application's required semantics first. Second, pick the correct
container/algo. If need be (and usually it need not be), perform
optimization (time and/or space and/or size) steps (but do avoid this 
unless
it is REALLY necessary, for it can unnecessarily result in "bad" code).

>
> If you choose a list representation, then a lot will depend on which
> pattern of searches predominates in your application. E.g., if there
> is a comparatively small set of keys that you will search for very
> often, then a "self organizing file" might be a good idea: you always
> search from front to tail and when you dfind a key, you move the
> entry to the head of the list. This way, frequently searched entries
> gather near the front and will be found quickly.

That is a good example of the thought process required to arrive at a
solution.

>
> If your searches are more or less evenly distributed among the keys, a
> better data structure would probably improve performance of
> searching. The tradeoff is usually a slightly greater complexity for
> inserting an entry. Whether changing the data structures pays off,
> therefore, also depends on whether your application will search way
> more often than it will modify the underlying data.

Example of optimization concerns.

>
> As the influencing factors are hard to predict, you should write your
> program so that it will be easy to change the data structure. Then,
> implement one that you can easily prove correct. Create unit tests.
> When you change the data structure, those tests will catch bugs. Once
> the other data structure is up and running, you can compare
> performance.
>

Again, I disagree (see above).

[toc] | [prev] | [next] | [standalone]

#6269

On 06/ 6/11 08:52 PM, MikeP wrote:
> Kai-Uwe Bux wrote:
>
>> Elsethread, the suggestion was made to hide this decision as an
>> implementation detail of some class. That is a good idea.
>
> I don't think that it is. This is the perfect opportunity for the OP to
> learn about applying the correct container/algo by taking the required
> amount of time to do so. Unnecessary abstraction just delays the decision
> and gives the application unnatural semantics and stifles the
> programmer's level of capability. Use the right tool for the job.

Requirements aren't always invariant.  If we lived in a perfect world, 
your observations would be correct.  But we don't!

>> As the influencing factors are hard to predict, you should write your
>> program so that it will be easy to change the data structure. Then,
>> implement one that you can easily prove correct. Create unit tests.
>> When you change the data structure, those tests will catch bugs. Once
>> the other data structure is up and running, you can compare
>> performance.
>
> Again, I disagree (see above).

Again, we don't all live in a world of unchanging requirements.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#6283

Ian Collins wrote:
> On 06/ 6/11 08:52 PM, MikeP wrote:
>> Kai-Uwe Bux wrote:
>>
>>> Elsethread, the suggestion was made to hide this decision as an
>>> implementation detail of some class. That is a good idea.
>>
>> I don't think that it is. This is the perfect opportunity for the OP
>> to learn about applying the correct container/algo by taking the
>> required amount of time to do so. Unnecessary abstraction just
>> delays the decision and gives the application unnatural semantics
>> and stifles the programmer's level of capability. Use the right tool
>> for the job.
>
> Requirements aren't always invariant.  If we lived in a perfect world,
> your observations would be correct.  But we don't!

You seem to be trying to make the exception the rule. The rule is to only 
code the exceptional case only in the exceptional case and not aberrate 
the common case with the exceptional. If you extrapolate further from 
your suggestion, you will see it is not practical nor is it good 
engineering.

In the OP's case shown above, doing the abstraction of the container/algo 
could be R&D but the final product should be devoid of test harnesses.

>
>>> As the influencing factors are hard to predict, you should write
>>> your program so that it will be easy to change the data structure.
>>> Then, implement one that you can easily prove correct. Create unit
>>> tests. When you change the data structure, those tests will catch
>>> bugs. Once the other data structure is up and running, you can
>>> compare performance.
>>
>> Again, I disagree (see above).
>
> Again, we don't all live in a world of unchanging requirements.

Non-sequitor at best, strawman at worst. Your "case" is moot. (You are 
welcome to try again though but I am not into have overly-general or 
philosophical discussion about it, for it is a well-defined area, at 
least to me it is). 

[toc] | [prev] | [next] | [standalone]

#6317

On 06/ 6/11 10:36 PM, MikeP wrote:
> Ian Collins wrote:
>> On 06/ 6/11 08:52 PM, MikeP wrote:
>>> Kai-Uwe Bux wrote:
>>>
>>>> Elsethread, the suggestion was made to hide this decision as an
>>>> implementation detail of some class. That is a good idea.
>>>
>>> I don't think that it is. This is the perfect opportunity for the OP
>>> to learn about applying the correct container/algo by taking the
>>> required amount of time to do so. Unnecessary abstraction just
>>> delays the decision and gives the application unnatural semantics
>>> and stifles the programmer's level of capability. Use the right tool
>>> for the job.
>>
>> Requirements aren't always invariant.  If we lived in a perfect world,
>> your observations would be correct.  But we don't!
>
> You seem to be trying to make the exception the rule.

No I'm not I'm simply agreeing with the suggestion to hide this decision 
as an implementation detail of some class.  The standard doesn't define 
how standard containers are implemented, it defines how they behave.

> The rule is to only
> code the exceptional case only in the exceptional case and not aberrate
> the common case with the exceptional. If you extrapolate further from
> your suggestion, you will see it is not practical nor is it good
> engineering.

Do what?

> In the OP's case shown above, doing the abstraction of the container/algo
> could be R&D but the final product should be devoid of test harnesses.

Eh?  You completely snipped the OP.

>>>> As the influencing factors are hard to predict, you should write
>>>> your program so that it will be easy to change the data structure.
>>>> Then, implement one that you can easily prove correct. Create unit
>>>> tests. When you change the data structure, those tests will catch
>>>> bugs. Once the other data structure is up and running, you can
>>>> compare performance.
>>>
>>> Again, I disagree (see above).
>>
>> Again, we don't all live in a world of unchanging requirements.
>
> Non-sequitor at best, strawman at worst. Your "case" is moot. (You are
> welcome to try again though but I am not into have overly-general or
> philosophical discussion about it, for it is a well-defined area, at
> least to me it is).

Well good for you.  Yesterday I had to change an object cache from a set 
to a map to facilitate exporting the data to a new external application. 
  Because the choice of container was "an implementation detail of some 
class" only that class had to be modified.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#6321

Ian Collins wrote:
> On 06/ 6/11 10:36 PM, MikeP wrote:
>> Ian Collins wrote:
>>> On 06/ 6/11 08:52 PM, MikeP wrote:
>>>> Kai-Uwe Bux wrote:
>>>>
>>>>> Elsethread, the suggestion was made to hide this decision as an
>>>>> implementation detail of some class. That is a good idea.
>>>>
>>>> I don't think that it is. This is the perfect opportunity for the
>>>> OP to learn about applying the correct container/algo by taking the
>>>> required amount of time to do so. Unnecessary abstraction just
>>>> delays the decision and gives the application unnatural semantics
>>>> and stifles the programmer's level of capability. Use the right
>>>> tool for the job.
>>>
>>> Requirements aren't always invariant.  If we lived in a perfect
>>> world, your observations would be correct.  But we don't!
>>
>> You seem to be trying to make the exception the rule.
>
> No I'm not I'm simply agreeing with the suggestion to hide this
> decision as an implementation detail of some class.

Well let's analyze that a bit more. State what is going to be relegated 
to "an implementation detail of some class" and what the class is that is 
composed of that "implementation detail". And you are suggesting that 
this should be done always and not just in exceptional cases?

[toc] | [prev] | [next] | [standalone]

#5821

On May 29, 8:58 pm, mrc2...@cox.net (Mike Copeland) wrote:
>    I have the following structure defined, and I'm trying to decide the
> best container to use for accessing specific elements: "best" meaning
> the fastest way.  I will be searching on the "sBibNo" field, and it will
> likely contain values in a high range (20000-50000).  The elements
> stored will not be contiguous.  I can't allocate an array of elements
> because doing so would waste a lot of memory space...so I can't use a
> direct index to find the elements.
>    I'm thinking I could use either an STL list or map for this
> application, but I fear the list processing would be prohibitively slow
> and the map might be quite wasteful in other ways.  The actual number of
> elements used in this application probably won't exceed 3000.

That's the trade-off you are faced with: Memory vs speed.

If you want to search inside the container, forget the list.
Lists can only be searched sequentially. Maps probably give
the fastest search results, at the expense of some internal
data structures that require memory.

Rune

[toc] | [prev] | [next] | [standalone]

#6268

Rune Allnor wrote:
> On May 29, 8:58 pm, mrc2...@cox.net (Mike Copeland) wrote:
>> I have the following structure defined, and I'm trying to decide the
>> best container to use for accessing specific elements: "best" meaning
>> the fastest way. I will be searching on the "sBibNo" field, and it
>> will likely contain values in a high range (20000-50000). The
>> elements stored will not be contiguous. I can't allocate an array of
>> elements because doing so would waste a lot of memory space...so I
>> can't use a direct index to find the elements.
>> I'm thinking I could use either an STL list or map for this
>> application, but I fear the list processing would be prohibitively
>> slow and the map might be quite wasteful in other ways. The actual
>> number of elements used in this application probably won't exceed
>> 3000.
>
> That's the trade-off you are faced with: Memory vs speed.
>
> If you want to search inside the container, forget the list.
> Lists can only be searched sequentially.

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.

> Maps probably give
> the fastest search results, at the expense of some internal
> data structures that require memory.

[toc] | [prev] | [next] | [standalone]

#6270

On Jun 6, 10:55 am, "MikeP" <mp011...@some.org> wrote:
> Rune Allnor wrote:
> > On May 29, 8:58 pm, mrc2...@cox.net (Mike Copeland) wrote:
> >> I have the following structure defined, and I'm trying to decide the
> >> best container to use for accessing specific elements: "best" meaning
> >> the fastest way. I will be searching on the "sBibNo" field, and it
> >> will likely contain values in a high range (20000-50000). The
> >> elements stored will not be contiguous. I can't allocate an array of
> >> elements because doing so would waste a lot of memory space...so I
> >> can't use a direct index to find the elements.
> >> I'm thinking I could use either an STL list or map for this
> >> application, but I fear the list processing would be prohibitively
> >> slow and the map might be quite wasteful in other ways. The actual
> >> number of elements used in this application probably won't exceed
> >> 3000.
>
> > That's the trade-off you are faced with: Memory vs speed.
>
> > If you want to search inside the container, forget the list.
> > Lists can only be searched sequentially.
>
> 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.

Rune

[toc] | [prev] | [next] | [standalone]

#6277

Rune Allnor <allnor@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).

-- Alain.

[toc] | [prev] | [next] | [standalone]

#6284

Alain Ketterlin wrote:
> Rune Allnor <allnor@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". 

[toc] | [prev] | [next] | [standalone]

#6285

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?

Rune

[toc] | [prev] | [next] | [standalone]

#6289

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.

[toc] | [prev] | [next] | [standalone]

#6295

On 6 juin, 16:06, "MikeP" <mp011...@some.org> wrote:
> 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.

I don't understand your point. A list is a data structure while a
queue is a way to organize/prioritize data (the FIFO abstraction).
Thus, in the C++ standard, a std::list<> is a container while a
std::queue<> is a container adapter.

I would be interest on how you can compare them ?

> 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.

From the reviews I have seen, it is tagged as a bit too academic.

--
Michael

[toc] | [prev] | [next] | [standalone]

#6296

Michael Doubez wrote:
> On 6 juin, 16:06, "MikeP" <mp011...@some.org> wrote:
>> 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.
>
> I don't understand your point.

My point is that discussion about fundamentals of ADTs is noise in a NG 
about C++. As such, I gave suggestion for further investigation to the 
poster.

> A list is a data structure while a
> queue is a way to organize/prioritize data (the FIFO abstraction).

The are both ADTs. In the simplest case, I think of a priority queue as a 
queue that allows adding to the front of the queue in addition to just 
the back of the queue. That one additional capability can distinguish a 
priority queue from a regular queue. Here's a good "homework" question: 
Should a queue allow iteration over it's elements just like a list does? 
(Good homework or test question in general. I wasn't assigning you 
homework!).

But see, now you are sucking me into the discussion I didn't want to get 
into! Web/search is your friend.

> Thus, in the C++ standard, a std::list<> is a container while a
> std::queue<> is a container adapter.


You seem to be confusing the abstraction with a particular 
implementation. Just because you CAN build a queue from a list does not 
mean you HAVE to build it that way, nor is it necessarily the best way.

> I would be interest on how you can compare them ?

I compare them according to their behavioral capabilities and by their 
applicability to a given scenario.

>> I recommend Cormen's book as the best on the subject.
>
> From the reviews I have seen, it is tagged as a bit too academic.

Well that is exactly what seems to be the need: fundamental principles of 
the different ADTs, divorced from any particular implementation in any 
programming language. If you don't like Cormen, there are plenty of other 
books on the subject. My red-black tree is based on the pseudo-code in 
the Cormen book, but an early version. I will be rewriting based on their 
latest edition which is more stable in regards to not invalidating 
iterators. So, I obviously like the book and that is why I recommended 
it. 

[toc] | [prev] | [next] | [standalone]

#6316

On 6 juin, 18:10, "MikeP" <mp011...@some.org> wrote:
> Michael Doubez wrote:
> > On 6 juin, 16:06, "MikeP" <mp011...@some.org> wrote:
> >> 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.
>
> > I don't understand your point.
>
> My point is that discussion about fundamentals of ADTs is noise in a NG
> about C++. As such, I gave suggestion for further investigation to the
> poster.

Given that one of the main advantage of generic programming is the
abstraction of the algorithm relatively to the data structure and
given that the standard provides containers with guaranteed
complexity, it seems very relevant to me.

>
> > A list is a data structure while a
> > queue is a way to organize/prioritize data (the FIFO abstraction).
>
> The are both ADTs.

I strongly disagree. The concern of a container is to provide a
storage with complexity guarantees related to access/insertion/
suppression of data while a FIFO/LIFO/whatever is a restriction on the
storage to enforce an access policy.

Those are two separated concerns and that is reflected in the STL: by
example std::queue can be built from whatever container supporting
back insertion and front deletion, which can then be std::vector<>,
std::list<>, std::deque (and std::slist IIRC).


> In the simplest case, I think of a priority queue as a
> queue that allows adding to the front of the queue in addition to just
> the back of the queue. That one additional capability can distinguish a
> priority queue from a regular queue. Here's a good "homework" question:
> Should a queue allow iteration over it's elements just like a list does?
> (Good homework or test question in general. I wasn't assigning you
> homework!).

From a theoretical point of view or from a practic

> But see, now you are sucking me into the discussion I didn't want to get
> into! Web/search is your friend.


> > Thus, in the C++ standard, a std::list<> is a container while a
> > std::queue<> is a container adapter.
>
> You seem to be confusing the abstraction with a particular
> implementation. Just because you CAN build a queue from a list does not
> mean you HAVE to build it that way, nor is it necessarily the best way.

Well, I am speaking of the abstraction. std::queue<> implementation
can vary. I have never seen it, but I could specialize it on a
vector<T> container to provide an alternative implementation of
pop_front() push_back(), or even, in the case of a priority_queue<>, I
could use a sorted area and an unsorted one in order to amortize the
cost of sorting (or whatever).

That's quality of implementation, the standard providing the semantic
and complexity guarantee (in some case).

>
> > I would be interest on how you can compare them ?
>
> I compare them according to their behavioral capabilities and by their
> applicability to a given scenario.

But, to me, if you compare a container and an access policy, you are
basically comparing vegetables and a frying pan. They may be related
but don't compare.

[snip]

--
Michael

[toc] | [prev] | [next] | [standalone]

#6318

Michael Doubez wrote:
> On 6 juin, 18:10, "MikeP" <mp011...@some.org> wrote:
>> Michael Doubez wrote:
>>> On 6 juin, 16:06, "MikeP" <mp011...@some.org> wrote:
>>>> 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.
>>
>>> I don't understand your point.
>>
>> My point is that discussion about fundamentals of ADTs is noise in a
>> NG about C++. As such, I gave suggestion for further investigation
>> to the poster.
>
> Given that one of the main advantage of generic programming is the
> abstraction of the algorithm relatively to the data structure and
> given that the standard provides containers with guaranteed
> complexity, it seems very relevant to me.

As it relates to C++ specifically, yes, but in general, probably not.

>
>>
>>> A list is a data structure while a
>>> queue is a way to organize/prioritize data (the FIFO abstraction).
>>
>> The are both ADTs.
>
> I strongly disagree. The concern of a container is to provide a
> storage with complexity guarantees related to access/insertion/
> suppression of data

There you go with the Big O stuff again. The concept of "queue" is 
orthogonal to the language lawyer stuff.

> while a FIFO/LIFO/whatever is a restriction on the
> storage to enforce an access policy.

Listen to yourself, seesh! ;) Stop making is so hard!

>
> Those are two separated concerns and that is reflected in the STL

STL is but one implementation, not THE implementation.

> : by
> example std::queue can be built from whatever container supporting
> back insertion and front deletion, which can then be std::vector<>,
> std::list<>, std::deque (and std::slist IIRC).

One can build a queue many ways. If you want to break the concepts down 
to minutiae and work from there, that is fine too. In the end you still 
end up with an queue. A queue is a queue is a queue and that is all it 
can be or else you'd have to rename the resultant thing. But to suggest 
that a particular implementation redefines the abstraction that it 
defines what a queue is, is incorrect. When in doubt, go back to first 
principles.

>
>
>> In the simplest case, I think of a priority queue as a
>> queue that allows adding to the front of the queue in addition to
>> just the back of the queue. That one additional capability can
>> distinguish a priority queue from a regular queue. Here's a good
>> "homework" question: Should a queue allow iteration over it's
>> elements just like a list does? (Good homework or test question in
>> general. I wasn't assigning you homework!).
>
> From a theoretical point of view or from a practic

?

>>> Thus, in the C++ standard, a std::list<> is a container while a
>>> std::queue<> is a container adapter.
>>
>> You seem to be confusing the abstraction with a particular
>> implementation. Just because you CAN build a queue from a list does
>> not mean you HAVE to build it that way, nor is it necessarily the
>> best way.
>
> Well, I am speaking of the abstraction. std::queue<> implementation
> can vary.

I was talking about queues in general. Not STL queue.

>  I have never seen it, but I could specialize it on a
> vector<T> container to provide an alternative implementation of
> pop_front() push_back(), or even, in the case of a priority_queue<>, I
> could use a sorted area and an unsorted one in order to amortize the
> cost of sorting (or whatever).
>
> That's quality of implementation, the standard providing the semantic
> and complexity guarantee (in some case).

All of that is not really relevant to the current place in this thread. I 
tried to keep you from dragging implementation details into this, but no 
avail. Oh well, so much for so much for the ol' college try.

>
>>
>>> I would be interest on how you can compare them ?
>>
>> I compare them according to their behavioral capabilities and by
>> their applicability to a given scenario.
>
> But, to me, if you compare a container and an access policy, you are
> basically comparing vegetables and a frying pan. They may be related
> but don't compare.
>

You are over-thinking it and making it harder than it is. The fundamental 
concepts are much simpler than that. And it's only those fundamental 
concepts that this thread required, but now it's littered with all the 
extraneous material. I should have just posted this link and been done: 
http://en.wikipedia.org/wiki/Queue_(data_structure). If you have issues 
with what is there, you can change it (but I'll probably revert the 
changes). Wikipedia is your friend, then, I should have said. 

[toc] | [prev] | [next] | [standalone]

#6319

On Jun 6, 3:22 pm, "MikeP" <mp011...@some.org> wrote:
> Michael Doubez wrote:
> > I strongly disagree. The concern of a container is to provide a
> > storage with complexity guarantees related to access/insertion/
> > suppression of data
>
> There you go with the Big O stuff again. The concept of "queue" is
> orthogonal to the language lawyer stuff.

If that's what you really think, you should not be a programmer. You
need to go back to school. "Big O" talk is /not/ language lawyering.

The defining characteristics of a container are its methods and
contracts (if any) of insert, removal, finding, and iteration, and the
time and space complexity to do those operations.

You don't need to use any of the containers except for a singly linked
list and linear search. There is a reason why that isn't done in
practice, and the answer is precisely Big O.

[toc] | [prev] | [next] | [standalone]

#6337

On 7 juin, 00:33, Joshua Maurice <joshuamaur...@gmail.com> wrote:
> On Jun 6, 3:22 pm, "MikeP" <mp011...@some.org> wrote:
>
> > Michael Doubez wrote:
> > > I strongly disagree. The concern of a container is to provide a
> > > storage with complexity guarantees related to access/insertion/
> > > suppression of data
>
> > There you go with the Big O stuff again. The concept of "queue" is
> > orthogonal to the language lawyer stuff.
>
> If that's what you really think, you should not be a programmer. You
> need to go back to school. "Big O" talk is /not/ language lawyering.
>
> The defining characteristics of a container are its methods and
> contracts (if any) of insert, removal, finding, and iteration, and the
> time and space complexity to do those operations.
>
> You don't need to use any of the containers except for a singly linked
> list and linear search. There is a reason why that isn't done in
> practice, and the answer is precisely Big O.

Re-reading the thread, I think I understand the misunderstanding. At
one point, we have lost the context of the OP which question directly
related to performances.

AFAIS, MikeP's comment was just to choose the right abstraction
related to the problem and not a specific implementation (MikeP,
correct me if I have misread your answer). And thus, this "go back to
the basic"; with the corollary of not basing a decision on the
complexity guarantees.

This is generally good advice but, from an engineering point of view,
this is  debatable :)

Still, the list vs queue doesn't make sense IMNSHO.

--
Michael

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web