All,
Since I am still a C neophyte and an array fits so many of my requirements, I am thinking that it may be the way to go. I don't have to do anything for the Perl prototype and the C implementation doesn't require rocket science.

• shift/pop are a simple matter of changing the logical end points
• unshift/push can be optimized if there is room between logical and real end points
• splice will require swapping values from the end to the insertion point perhaps through memcpy

It just isn't blazingly fast in comparison to binary trees.

Update:
I discussed this with ambrus further in the CB. There are optimizations available that wouldn't be otherwise for a general solution that I can capitalize on. I will start out with a large real array and place my logical array in the middle.