Deque impl.

[Dmitry Olshansky]

31-Jan-2013 05:34, 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.
>

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