Michael said:
Michael Doubez wrote:
Rune Allnor wrote:
Alain Ketterlin wrote:
[...]
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.
We are in a C++ NG. So we seem to agree it is not noise.
There you go with the Big O stuff again. The concept of "queue" is
orthogonal to the language lawyer stuff.
The language and especially the STL is based on the mathematical and
algorithmic abstractions. IMO this comment is disregarding the
contribution of Alexander Stephanov to the language. IMHO the models
defined by the language are pretty good matches.
Apart from that the Container and Queue (let call it FIFO)
abstractions are two different beasts with different concerns. Let
take the definition of wikipedia (which are not too bad):
http://en.wikipedia.org/wiki/Container_(data_structure)
"In computer science, a container is a class, a data structure, or an
abstract data type (ADT) whose instances are collections of other
objects."
http://en.wikipedia.org/wiki/Queue_(data_structure)
"A queue (pronounced /ˈkjuË/ kew) is a particular kind of collection
in which the entities in the collection are kept in order and the
principal (or only) operations on the collection are the addition of
entities to the rear terminal position and removal of entities from
the front terminal position."
Listen to yourself, seesh!
Stop making is so hard!
Could you provide an alternative (softer
) definition.
STL is but one implementation, not THE implementation.
I am talking about the concepts defined by the STL, not the
implementation.
See:
http://www.sgi.com/tech/stl/queue.html
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.
I fail to see how that follow what I said.
[Oups, missing part.]
From a theoretical point of view, this can be discussed. From a
practical point of view, it would have been convenient for debugging/
logging purpose.
Actually from STL SGI, removing iteration is the raison d'etre of
std::queue<>:
"[...]Queue does not allow iteration through its elements. [2]"
"[2] This restriction is the only reason for queue to exist at all.
Any container that is both a front insertion sequence and a back
insertion sequence can be used as a queue;[snip] The only reason to
use the container adaptor queue instead of the container deque is to
make it clear that you are performing only queue operations, and no
other operations.
I was talking about queues in general. Not STL queue.
So we are talking of the same thing.
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 don't see how speaking about complexity or concepts would be a
implementation detail.
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.
I see no fault with the Wikipedia page.
