On 01/31/2013 02:48 AM, bearophile wrote:
Steven Schveighoffer:
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.
Amortized O(1) insert/removal, and hard O(1) for indexing. And the
multiplicative constants must be low.
My implementation (probably very naive) is two D arrays placed front
to front. This allows the O(1) insertion/removal and O(1) indexing.
What's the memory behavour if you keep using it like a queue (adding
at the end and removing from the head)?
See my first comment:
http://forum.dlang.org/thread/[email protected]#post-kkfkonazfgsuqddkuimy:40forum.dlang.org
I did not find such a method in his deque impl. (I did only check all
the find of chrome for front though).
Bye,
bearophile
