data structures module

[Oren Tirosh]

On Fri, Jan 16, 2004 at 01:08:51PM -0500, Aahz wrote:
> In article <92c59a2c.0401152306.1c6a17f5 at posting.google.com>,
> MetalOne <jcb at iteris.com> wrote:
> >
> >Today, I wanted a priority queue.
> >I notice that Python does not have any sorted lists.
> >I know that I can call list.sort(), but that seems rather inefficient
> >to call every time an element is added.
> >I am wondering why there is not a module or modules containing many
> >common data structures.  Has such a thing been decided against?  Is it
> >that just nobody has done it?  Has nobody else suggested the need for
> >it?  Maybe I should search, but I am too tired now, I need sleep.
> 
> There's a current discussion on python-dev about a "collections" module
> or package, and that's one of the structures under discussion.

The major thread of the discussion there is about enhancing the built in 
list type to handle popping the first item more efficiently behavior) so 
the append/pop() idiom of implementing a queue will work in amortized O(1)
time. 

I like the general direction this is going - no new basic data types. 
Lists and dicts are sufficient for 98% of all will we ever need. The
remaining 2% can mostly be implemented in Python because it's rarely 
performance-critical. The remaining cases are probably better handled by
specialized extension modules anyway (e.g. jkbuckets)

Oren