[Python-ideas] Reimplementing collections.deque as a dynamic array

[Cameron Simpson]

On 29May2012 00:46, Julian Berman <julian at grayvines.com> wrote:
| I've occasionally had a need for a container with constant-time append
| to both ends without sacrificing constant-time indexing in the middle.
| collections.deque will in these cases narrowly miss the target due to
| linear indexing (with the current use case being for two deques
| storing the lines of text surrounding the cursor in a text editor
| while still being randomly indexed occasionally).
| 
| Wikipedia lists at least two common deque implementations:
| 
| http://en.wikipedia.org/wiki/Double-ended_queue#Implementations
| 
| where switching to a dynamic array would seemingly satisfy my requirements.
| 
| I know from a bit of experience (and a quick SO perusal) that "How do
| I index a deque" does occasionally come up. Any thoughts on the value
| of such a change?

It was pointed out to me recently that Python's list.append() is constant
time overall.

Use two lists, one for append-forward and one for append backward. Keep
track of the bound. Access to item "i" is trivially computed from the
backward and forward list sizes and ends.

Cheers,
-- 
Cameron Simpson <cs at zip.com.au> DoD#743
http://www.cskk.ezoshosting.com/cs/

The mere existence of a problem is no proof of the existence of a solution.
        - Yiddish Proverb