On Tue, 29 Jan 2013 15:08:36 -0500, Dmitry Olshansky
<[email protected]> 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
