No trees in the stdlib?

[Steven D'Aprano]

On Wed, 01 Jul 2009 20:39:06 +1200, Lawrence D'Oliveiro wrote:

> In message <mailman.2140.1245996088.8015.python-list at python.org>, João
> Valverde wrote:
> 
>> Simple example usage case: Insert string into data structure in sorted
>> order if it doesn't exist, else retrieve it.
> 
>     the_set = set( ... )
> 
>     if str in the_set :
>         ... "retrieval" case ...

Not terribly useful, because there's no way of attaching any data to 
retrieve to the key. Apart from the case of interning strings (or other 
keys), you'd probably want a dict rather than a set:

if str in the_dict:
    return the_dict[str]
else:
    the_dict[str] = something_or_other


>     else :
>         the_set.add(str)
>     #end if


> Want sorted order?
> 
>     sorted(tuple(the_set))
> 
> What could be simpler?

Dropping the entirely superfluous creation of a tuple:

sorted(the_set)

That's a reasonable approach for small sets of data, but it isn't very 
useful if the_set contains 4GB of keys, because you have to duplicate the 
keys, then sort them. More effective would be a data structure that was 
always sorted. This has the further advantage that it's even simpler than 
sorted(the_set):

the_set



-- 
Steven