From: Kristof Bastiaensen <kristof@...>
Date: 2004-09-05T06:30:25+09:00
Subject: Re: Hashes and ordering

On Sat, 04 Sep 2004 11:33:54 +0200, Robert Klemme wrote:

> 
> "Kristof Bastiaensen" <kristof@vleeuwen.org> schrieb im Newsbeitrag
> news:pan.2004.09.04.07.58.02.69935@vleeuwen.org...
>> On Sat, 04 Sep 2004 12:39:31 +0900, Hal Fulton wrote:
>>
>> > Markus wrote:
>> >> Where are you going with this?  There seem to be three unrelated
>> >> things here:
>> >
>> > Well, I have been thinking along the lines of: What if we had a
>> > built-in ordered indexable collection in Ruby?
>> >
>> >
>> What about an association list (Array)?
>>
>> [["one", 1], ["two", 2], ["three", 3]].assoc("one") => ["one", 1]
>>
>> You could wrap it in a class to have it behave more like a Hash.
> 
> Very inefficient if you have many lookups (O(n)).  And it doesn't maintain
> order automatically.
> 

Yes, that's true.  I mentioned it because it is already in the language.

> The typical and most efficient implementation in the general case of an
> ordered map is a tree AFAIK.

Yes! And a balanced tree.  It is probably the best when you want
the map ordered by key.

If you wanted insertion order, what would you think of the combination
of a Hash and a linked list?  The hash could provide key lookup, and the
linked list would keep the order.  (It would need to be only a
single-linked list).

> 
> Kind regards
> 
>     robert

Regards,
Kristof