Note that the original article describes space complexity as "N + O(sqrt N)", i.e., there are N records and O(sqrt N) extra space.

Their data structure is considerably more complex than traditional implementations of std::deque, I wonder if it is actually of any practical interest.