From: Charles Hixson Date: 2004-09-06T07:46:08+09:00 Subject: Re: Hashes and ordering Robert Klemme wrote: > > "Kristof Bastiaensen" schrieb im Newsbeitrag > news:pan.2004.09.04.21.31.32.818609@vleeuwen.org... > >> On Sat, 04 Sep 2004 11:33:54 +0200, Robert Klemme wrote: >> >>> >>> "Kristof Bastiaensen" 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. > > > Si. > >> 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). > > > Yeah, a bit similar to an LRU cache implementation - only that you > change order only on insertion and don't have a size limit. > > Kind regards > > robert FWIW, there is an RBTree for Ruby included in the rpa list of packages. I don't know what it's interface it, or whether it works properly, but it's there. (It seems to be implemented in C, so it might well be as fast as Hash.)