From: Glenn Parker Date: 2004-12-03T00:59:29+09:00 Subject: Re: ordered hash ? Austin Ziegler wrote: > On Thu, 2 Dec 2004 23:37:34 +0900, Nikolai Weibull >> >>Having an ordered Hash is like saying that arrays should be indexed by >>strings--it's simply not what they are meant to be. > > Be that as it may, it is still necessary to have an insertion-ordered > hash-like object. > > I use it in PDF::Writer for page objects that can be referred to > meaningfully -- but still render in the order in which they were > inserted. How is an "OrderedHash" different from something we might call a "HashedArray", i.e. an array where elements also have a string-like address? With this hybrid type, the array-ness and the hash-ness are orthogonal and neither takes precedence. To me, this says that the only solution (that can maintain an arbitrary ordering) is something like Michael's two-layered implementation, where a hash and an array both refer to the same set of objects internally. Hashing destroys ordering, so you have to pay for it somewhere else. A more flexible altnerative to Michael's OrderedHash implementation might embed an index within each element, or maintain a parallel hash with indices, then sort the elements by index on demand. If you access the elements in sorted order infrequently, this might be a win for performance. SkipList and related patterns impose an external sort-ordering on the hash elements, so they would not suit Austin's requirements. -- Glenn Parker | glenn.parker-AT-comcast.net |