Popping from the middle of a deque + deque rotation speed

[Tim Peters]

[Russell Warren]
> ...
> As to indexing into a deque being O(index)... I didn't realize that.
> It is certainly something to keep in mind, though... looping through
> the contents of a deque would obviously be a bad idea with this being
> the case!  I wonder if the generator for the deque helps reduce this?
> Will check later.

FYI, deque implements efficient forward and reverse iterators.  So, e.g.,

    for x in a_deque:
        pass

and

    for x in reversed(a_deque):
        pass

takes time proportional to len(a_deque).  In contrast,

    for i in xrange(len(a_deque)):
        x = a_deque[i]

take time quadratic in len(a_deque).

The iterators don't use __getitem__ under the covers; explicitly
indexing does, and that's the difference here.