Best data-structure to use for two ended sorted list
Question: I need a collection data-structure that can do the following:

  * Be sorted
  * Allow me to quickly pop values off the front _and_ back of the list O(log n)
  * Remain sorted after I insert a new value
  * Allow a user-specified comparison function, as I will be storing tuples and want to sort on a particular value 
  * Thread-safety is not required
  * Optionally allow efficient haskey() lookups (I'm happy to maintain a separate hash-table for this though)

My thoughts at this stage are that I need a priority queue _and_ a hash table,
although I don't know if I can quickly pop values off _both_ ends of a
priority queue. Another possibility is simply maintaining an OrderedDictionary
and doing an insertion sort it every-time I add more data to it.

Because I'm interested in performance for a moderate number of items (I would
estimate less than 200,000), I am unsure about what asymptotic performance I
require for these operations. n will not grow infinitely, so a low constant
performance `k` in `k * O(n)` may be as important `O(n)`. That said, I would
prefer that both the insert and pop operations take `O(log n)` time.

Furthermore, are there any particular implementations in Python? I would
really like to avoid writing this code myself.


Answer: You might get good performance for these kinds of operations using
[`blist`](http://pypi.python.org/pypi/blist/) or a database (such as the
[sqlite](http://docs.python.org/library/sqlite3.html) which is in the stdlib).

