My favourite text editor is still vi, so I prefer the shorter term deque to DoubleEndedArray. 
1 Like
The name DoubleEndedArray doesn't make much sense to me, as Array is already double ended!
That Schweppe guy (whose name I can't pronounce properly either) made a disservice to the community by choosing "Deque" name (aka dequeue) which is a verb – an operation performed on queues. Should he've chosen, say, Biqueue (short for bidirectional queue) we'd not have this conversation now.
Furthermore I'm actually suprised I can do normal array operations like insert / delete at arbitrary position on a dequeue. Had we a proper "Queue" type would it also be the case? On one hand that's how real queues (in shops) behave. OTOH Queue is said to be a strict FIFO ADT and dequeue just "generalises" queue, for which elements can be added to or removed from either the front (head) or back (tail)". By providing those extra array operations we are doing something more and ideally we need to reflect that in the name. Conversely, by providing just FIFO + bidirectional ADT we may have a more optimal data structure for that less capable ADT. Similarly if we had "Stack" it could be more optimal than a more general "Array".
Forget the names, could array grow/shrink from both ends efficiently? I believe it could (on 64 bit platform at least): allocate a giant address block (say 10GB) and "point" array to the middle of it, there will be it's elements 0th, 1th, etc. Only a page size or so from that giant block will be initially mapped. You add items to the end – more pages got mapped from the end. You insert something at the beginning – new pages got mapped from the beginning and array "start" moves accordingly, 64 bit address space is huge to allow this, 32 bit is a different story.
5 posts were merged into an existing topic: One Terabyte Array Idea
I have moved several posts about about large arrays to a new thread that Tera created and then closed this one, since the discussion about naming Deque is already settled.
2 Likes