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

[Alex Martelli]

Tim Henderson <tim.tadh at gmail.com> 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.

It may be the most practical approach, though.  Designing ONE "ordered
dictionary" needs to answer several questions that will affect (reduce)
its usefulness no matter how you answer them, such as: do the keys need
to be hashable *as well as* order-comparable?  Do copies of key objects
get implicitly taken on insertion?  Etc, etc.


> 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?

Depends on the patterns of occurrences of insertions and deletions
versus needs to use the sortedlist, in terms of how do they get bunched
or spread out in time wrt each other.  For many cases, the best answer
is, neither of those you mentioned, but rather the functions in heapq.


Alex