O(1) performance for insertions/deletions at the front of an Array/String

I just did some benchmarks on push, pop, shift, and unshift
and/or various equivalents for both the Array and String
classes.  I was using 100000 elements.  Here are my findings:

1. push/pop and equivalents have O(1) performance as expected.

2. shift also has O(1) performance.  I'm assuming that it
simply moves the start of array pointer by 1 instead of
shifting the data.

3. unshift has O(1) performance when you unshift no more than
the amount you have shifted.  I'd assume it just decremented
the start of array pointer.  When you unshift more than you
shifted, it is O(n), physically moving the data to the right.

4. all other equivalents to shift and unshift (slice!(0),
delete_at(0), insert(0,), [0,]=) have O(n) performance.

I have a couple applications where being able to quickly
insert/delete at the front and back of an Array/String would be
great.

Here are my suggestions to you core developers (the ones
responsible for Array/String at least):

a. at least make equivalents to shift (slice!(0), slice!(0,n)
delete_at(0), [0,n]=nil/[]/"") also O(1).  In the String class
there is currently no fast equivalent to Array#shift.

b. make unshift (and equivalents in Array and String) always
O(1).  This could be done my stretching the Array/String to the
left just like push (and equivalents) stretches the
Array/String to the right in memory.

c. if shifts/unshifts can be made just as fast as pushes/pops,
you could cut the average time in half for random insertions
and deletions.  You could insert/delete toward the closest end
of the Array/String and on average move half the amount of
data.  The closer you are to either end, the less data that
needs to be moved.

For reference, here is a ruby implementation showing how all 4
insert/delete operations at the ends can be made O(1).  This
was pretty easy since shift is O(1).  It would be a little more
difficult to implement this for a String right now.

class Array2
    def initialize(after=[],before=[])
        @after = after
        @before = before
    end
    def push(*args)
        @after.push(*args)
    end
    def pop
        v = @after.pop
        v.nil? && @after.empty? && (v = @before.shift)
        v
    end
    def unshift(*args)
        @before.push(*(args.reverse))
    end
    def shift
        v = @before.pop
        v.nil? && @before.empty? && (v = @after.shift)
        v
    end
end




		
__________________________________ 
Yahoo! Mail 
Stay connected, organized, and protected. Take the tour: 
http://tour.mail.yahoo.com/mailtour.html