From: William Djaja Tjokroaminata <billtj@...>
Date: 2002-09-17T02:31:30+09:00
Subject: Is Ruby Array#shift/unshift Efficient?

Hi,

I just scanned the Ruby array implementation in array.c, and to my
surprise, every time Array#shift/unshift is called, memmove() is
invoked.  So far I never saw any advice for the preferred use of
push/pop to shift/unshift.  The last time I used C++, vector was good only
for push/pop while if we wanted to use push/pop/shift/unshift it was
better to use a deque.

Therefore, is memmove() really that efficient (O(1) operation), or should
Ruby array be re-implemented using a deque, or is there something else
that I am not aware of?  (For example, in Python array, only pop() and
append() are given, to signify that insert/delete at the beginning of
array is not an efficient (O(1)) operation.  I think C++ STL follows the
same philosophy.)

Regards,

Bill