[boost] Re: Bag concept

From: Andy Glew (glew_at_[hidden])
Date: 2000-01-13 17:33:39

I don't know if y'all need yet another opinion about names,
but what the heck. Talking generically, ideally, not always
referring to the STL names (although I'll acquiesce in the STL
names, until they are replaced by the Generic Java names):

Briefly
=====

"queue" means ordered extracts. LIFO if nothing else;
or "priority_queue". No guarantees on internal order.

I basically agree with John Potter:
    Hum: push, pop, top, empty ?  classic stack
    Oh: put, take, look, empty ?  any collection/container
And Kevlin Henney:
   * Perhaps an adjective rather than a noun would be better. Rather than
   describing it as a thing, describe its properties.

"buffer" is a generic queue, with no guarantees as to extraction
order.

"bag" means multiset. Longstanding use, although I would prefer
to deprecate "bag" in favour of "multiset".

"collection" implies that "looking at the collection" is what's important.
So, a pure queue that only allowed you to enqueue/dequeue would not
be a collection; C++'s queue is.
    "sorted_collection", "arbitrary_collection" could be formed naturally.
"set" and "map" have unique elements. No guaranteed
order of extraction. No guaranteed order of traversal.
Random queries.
    "multiset" and "multimap" may have multiple elements.
No guaranteed order of extraction, except when specifying
object or key to be extracted. Random queries. No guaranteed
order of traversal.
    YES: IMHO C++ (and Pascal, and many other programming
languages) got this wrong. The C++ STL's set/map/multiset/multimap
provide a guaranteed internal traversal order, and would better
be called "sorted_set", "sorted_map", etc. IMHO "hash_map"
is the only primitive map. My opinion is in good company:
Messrs Date and Codd, of relational database theory, are also
of the opinion that "set" does not imply ordering.

I have no preconceptions about "sack", "pouch", "satchel", "backpack",
etc., except agreeing with Kevlin that inventing arbitrary new terminology
is bad, if adjectives applied to existing terms sereve equally well.

Verbosely
=======

"queue" is a data structure that has insert and extract operations
(enqueue and dequeue, if you like; push*/pop* for STL).
    There's a huge body of knowledge called "Queuing Theory";
it would be a shame to adopt a definition of "queue" that is
incompatible with this theory.

The term "queue" implies ordering, LIFO ordering if not
further qualified.
    "priority_queue" is a further qualification: some static key
controls the order of extraction.
    "dynamic_priority_queue" is a priority queue where
the priorities attached to the objects change while in the queue.
Extraction still always extracts the instantaneously highest
(or lowest) priority objects in a single threaded world; in
a multithreaded world, often falls back to some approximation
of instantaneous highest priority, since full serialization may
be too costly. (E.g. Thomas Anderson's run queues.)

"queue" and "priority_queue" are not strongly associated
with internal ordering: i.e. iterating over the queue does not
mean that the order of iteration will be the same as the order of
extraction.  This allows implementations such as binary or Fibonacci
heaps, that do not keep the objects in sorted order.

"sorted_queue" might be construed as a queue that provided
an iterator that traversed objects inside the queue in their priority
order.