From: Bill Kelly <billk@...>
Date: 2004-09-05T03:38:35+09:00
Subject: Re: Hashes and ordering

Hi Hal,

From: "Hal Fulton" <hal9000@hypermetrics.com>

> Well, I have been thinking along the lines of: What if we had a built-in
> ordered indexable collection in Ruby?
[...]
> It's more like:
> 
>    x = [1,2]
>    y = [2,1]
>    x == y     # false - we *do* depend on this being false
> 
> I'm envisioning a data structure that has an order, but is otherwise (in
> behavior, not implementation) like our current Hash.

There's a nice structure in stl called a multimap... I've used
it recently to model a priority queue.

Quoting from Generic Programming and the STL by M H Austern:

  multimap<Key, T, Compare, Allocator>
    A multimap is a Sorted Associative Container that associates
  objects of type Key with objects of type T.  It is a Pair
  Associative Container, meaning that its value type is 
  pair<const Key, T>.  It is also a Multiple Associative 
  Container, meaning that it may contain two or more identical 
  elements.  (This is the only way in which map and multimap
  differ.)  That is, the multimap class doesn't map a value of
  type Key to _an_ object of type T, but rather to _one or more_
  objects of type T.
    Since multimap is a Sorted Associatiave Container, its 
  elements are always sorted in ascending order.  The template
  parameter Compare defines the ordering relation.
    Like list, multimap has the important property that inserting
  a new element does not invalidate iterators that point to
  existing elements.  Erasing an element from multimap does not
  invalidate any iterators either, except, of course, for 
  iterators that point to the element that is being erased.


It's pretty cool - you can just toss values into it with
insert() as you would a hash.  But you can iterate forward
and backward through it, seeing the elements in sorted
order (sorted by Key).

So for my priority queue, my key is simply an integer and
my value is... well just any ol' object.

Since it's a *multi* map instead of just map, I can toss
in multiple elements having the same priority.  I.e.
  pri_q.insert(pair(9, "a"))
  pri_q.insert(pair(10, "b"))
  pri_q.insert(pair(10, "c"))
  pri_q.insert(pair(11, "d"))

...The 9, 10, and 11 are the keys.  It'll store both 10's for
me without conflict.  (Instead of the 10=>"c" replacing the
10=>"b".)

Anyway - dunno if this is anything like what you're
thinking of.


Regards,

Bill