31-Jan-2013 05:34, Steven Schveighoffer пишет:
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.
Hm I must be getting rusty as I'd thought it doesn't have indexing.
Anyway indexing is okay just not insertion in the middle. So throw in
opIndex among the above.
Then the only layout left to propose is an array of blocks. Then
indexing is done like:
blocks[idx>>N][idx&mask]
if block size is power of 2. Not half-bad and still O(1).
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
--
Dmitry Olshansky
