[Python-Dev] LinkedHashSet/LinkedHashMap equivalents

[Nick Coghlan]

Anthony Baxter wrote:
> On Thursday 10 March 2005 17:29, Raymond Hettinger wrote:
> 
>>Or the implementation can have a switch to choose between keep-first
>>logic or replace logic.
>>
>>The latter seems a bit odd to me.  The key position would be determined
>>by the first encountered while the value would be determined by the last
>>encountered.  Starting with [(10, v1), (20, v2), (10.0, v3)], the
>>ordered dictionary's items would look like [(10, v3), (20, v2)].
> 
> 
> Or, alternately, we keep the last occurence, and move it to the new position.
> There's a wide number of different use cases, each with a slightly different
> final result, and for this reason alone I'm -0 on it for the library. 
> 
> Anthony
> 

But surely such use cases could be more easily handled by subclassing from 
collections.OrderedDict and tweaking the semantics than by having to implement 
an ordered mapping from scratch.

Would the default semantics below really be that suprising?

"An ordered dictionary remembers the order in which keys are first seen and, 
when iterated over, returns entries based on that order. This applies to direct 
iteration, iteration over values and (key, value) pairs, to the list-producing 
methods (i.e. keys(), values() and items()) and to any other operations that 
involve implicit iteration (e.g. converting to a string representation). 
Overwriting an entry replaces its value, but does not affect its position in the 
key order. Removing an entry (using 'del') _does_ remove it from the key order. 
Accordingly, if the entry is later recreated, it will then occur last in the key 
order.

This behaviour is analagous to that of a list constructed using only 
list.append() to add items (indeed, the key order can be thought of as a list 
constructed in this fashion, with keys appended to the list when they are first 
encountered).

An ordered dictionary provides a sort() method. The sort operation is applied to 
the key ordering and affects future iteration over the dictionary. Again, this 
is analagous to sorting a list."

For instance, to convert a standard dictionary to an ordered dictionary using a 
specific key function:

   x = collections.OrderedDict(sorted(d.itervalues(), key=keyfunc))

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://boredomandlaziness.skystorm.net