From: Robert Klemme Date: 2004-09-05T18:35:14+09:00 Subject: Re: Hashes and ordering "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