Re: [tlug] Are ordered hashes useful?

[Raymond Wan <rwan.kyoto@example.com>]

On 15/02/11 11:04, Stephen J. Turnbull wrote:
> Marty Pauley writes:
>   >  On Sat, Feb 12, 2011 at 3:42 PM, Jun-Dai Bates-Kobashigawa
>   >  <jd.lists@example.com>  wrote:
>   >  >
>   >  >  Then there are cases where you want a data structure that provides both
>   >  >  dictionary access and ordered list access.
>   >
>   >  That data structure is called a "tree".  It's very common.
>
> Not to mention highly elaborated.
>
> But it's not clear that dictionary order and ordered-list order are
> the same.  For example, on python-dev the killer reason (ie, one that
> cannot be implemented with existing constructs) for requesting ordered
> dictionary was not for user use, but rather for implementing an
> optimization in function calls.

...

Yes, I don't agree that dictionary order and ordered list 
are the same.  Ordered list access could be provided by a 
tree, but to enable dictionary access, you either need to 
augment the tree with a hash table or build two trees in 
parallel.

I doubt one data structure can provide access to data in two 
ways.  I suppose you could (say) combine a tree and a hash 
table and then give it a new name (i.e. hashtable-tree) and 
then make it a primitive or library in some language.  IMHO, 
that's "kind" of cheating.  Associative lists are primitives 
in languages like Perl and Python, but underneath it all, a 
lot has to be done (and ironically, probably in C/C++).

If I'm not mistaken, Stephen's original query was whether an 
ordered hashing is useful.  I presumed this meant the 
underlying algorithm or data structure and somewhat 
language/library/API-neutral.

Ray