data-structure-deque

A deque of O(sqrt(n)) complexity on access, insert and remove, with an optimization for O(logn) access based on fenwick tree.

You may found the optimized version here. This one is four times faster than Sqrt Vector version on large data.

This repo is migrated from my GitHub gist.

Failed Attempts and Other Implementations

• Linked List: O(n) access, O(1) insert & remove
• Ring Buffer: O(1) access, O(n) insert & remove (Like the one bundled with GNU C++ STL)
• Sqrt Vector: O(sqrt(n)) access, O(sqrt(n)) insert & remove
• Chunk Vector: O(n/chunk_size) access, O(n) insert & move

Related Works

Another data-structure project I've done is a B+ Tree built from scratch. This B+ tree supports on-disk persistence, on-demand paging and LRU. I've written several unit tests for it.