[boost] Re: Bag concept

From: Reid Sweatman (borderland_at_[hidden])
Date: 2000-01-13 00:25:03

> While we're defining container concepts, there ought to be a Bag
> concept. A Bag is something that you can put and get items out of. For
> instance, Dietmar's heaps and queue's would qualify as Bags. The
> requirements for a Bag would simply be:
>
> Bag::value_type
> Bag::size_type
>
> b.push(t)        void
> b.pop()          void
> b.top()          T&
> b.empty()        size_type
>
> I suppose you could add logical inspectability to the requirements,
> but I think that's what the Collection concept is for, so we might as
> well keep the Bag concept minimalistic.

This is one I'm very much in favor of.  I've just spent three days working
out a caching scheme that turned out to require one data object of the bag
sort, in which all I really needed was a place to dump things, and I didn't
care what order they were in (except when the object needed to be resized,
which would probably be rare), and another place with roughly the same
requirements, save that I needed fast lookup.

I ended up going with a stack hand-implemented from a vector for the first,
so I could sort it when necessary, and a set for the second, so I could use
the binary search on it.  I would be nice, though, to have an object that's
really and truly a bag, in the classical sense (which I take to really be
the meaning of "set," which the set object doesn't really fulfill, since
it's ordered, and a classical set may not be...and for anyone to whom these
semantics aren't clear, I come from a formal math background, so I'm talking
naive set theory here, and my notion of "bag" comes from Holub's compiler
book).  Doing it the way I did strikes me as involving some unavoidable
overhead the application really can't afford, mostly in the set object,
since it has to maintain a binary tree.  A bag would solve the problem
without imposing that overhead.

Occasionally it would be nice to impose order on that classical bag, though,
so it would be nice to be able to apply various sorting and lookup
algorithms to it, like Dietmar's heaps and queues.  I'd resist, however, the
notion of making a bag be inherently ordered.  Sets already do that, and I
don't think a bag should be required to be ordered in any way.  However,
this raises an inheritance problem, since many of the standard containers
could really be considered to be specialized bags.  After all, a set is the
basic abstraction that underlies just about every branch of mathematics.

I think I'd prefer a basic bag that fits the classic definition, and some
derived specialized bags that add functionality like unique elements,
ordering, and so on.  I also note that as you've defined the bag interface,
you've basically defined a stack.  And I apologize for any prior discussion
I may have missed.  Okay, that's my 0.02 Zorkmids.