Deque impl.

[Steven Schveighoffer]

On Tue, 29 Jan 2013 15:08:36 -0500, Dmitry Olshansky  
<dmitry.olsh at gmail.com> wrote

>
> I skimmed through it what caught my eye instantly: this deque exposes  
> too much of operations that are not required of any deque. The end  
> result is that it's pretty much always have to be an array (all these  
> indexed inserts, removals etc.). To put it plainly it *is* an array.
>
> To be honest deque can be implemented far better if random access as in  
> indexing, removal and such is dropped. Canonical interface is:
>
> front
> insertFront
> removeFront
> back
> insertBack
> removeBack
> length (and even this could be dropped sometimes)
> empty
>
> That is all.

Hm... I thought deque's major draw was that it had O(1) insertion/removal  
 from the front and back, and ALSO had O(1) indexing.

At least in C++, indexing is supposed to be constant.

My implementation (probably very naive) is two D arrays placed front to  
front.  This allows the O(1) insertion/removal and O(1) indexing.

http://dsource.org/projects/dcollections/browser/branches/d2/dcollections/Deque.d

-Steve