should python have a sort list-map object in the std-lib?

[Steven D'Aprano]

On Sun, 27 Nov 2005 23:35:03 -0500, Tim Henderson wrote:

> Hi
> 
> The question why are there no sorted dictionaries in python, seems to
> pop up with unseeming regularity. That question in itself in
> nonsensical sense dictionaries are hash-maps, however should python
> have a sorted map type object is a good question.
> 
> clearly many people like have a sorted map, and sorting the keys every
> time seems rather wasteful, as does keeping a separate sorted list of
> the keys.

Another good question is, does it *seem* wasteful or is it *actually*
wasteful? More or less wasteful than having special code in Python to
implement "sorted dictionaries" (whatever that means)?

It is good to have a rich, powerful set of tools in a programming
language. It is bad to expect that, no matter what task you need, that
your language should have a single function or object to do it. That just
leads to a bloated language where it is harder to find the feature you
want than it is to simply write it yourself.



> a related question is, in python is it more efficient to a maintain a
> list type in sorted order by inserting each new object in the correct
> location (by say finding it with a binary search and then using del
> list[x]) or appending each new item to the end of said list and using
> the built-in .sort method, or sorted() function?

I don't think using del to insert an object into a list would be very
efficient, no matter how little time the deletion took :-)

Why don't you try it for yourself? You only need some quick and dirty code
to discover which approach is better (for a quick and dirty definition of
"better"). Don't forget to check out the bisect module too.


-- 
Steven.