[keith_analog]

A few years ago, our research group published a data structure, called Chunked Sequence, that is similar to the Finger Tree. In short, Chunked Sequence features the same asymptotic profile as does Finger Tree (neglecting persistence) and, in addition, offers strong guarantees with respect to constant factors. Very roughly speaking, Chunked Sequence is to Finger Tree what b-tree is to red-black tree.

We've implemented Chunked Sequences as a package of C++ header files and provided source code on github. To the client, Chunked Sequence looks like STL deque, but with additional methods to allow split at a specified position and concatenate, both in logarithmic time. The operations which push and pop on the ends of the Chunked Sequence are approximately as fast as those of STL deque, and in certain use patterns much faster.

http://deepsea.inria.fr/chunkedseq/

[osivertsson]

Cool.

But please provide clear licensing information (preferably a permissive free software license). Right now I can't find anything at all about what terms you are releasing this source code under.

Therefore most people will be unable to use it, which is a shame.

[keith_analog]

Thanks for the comment! We are using the MIT license. I've updated the source code in the git repository accordingly.

[pmarreck]

http://choosealicense.com/

[davexunit]

Which MIT license?

[keith_analog]

Thanks again! We're using the Expat license.