Package description

This package is a C++ template library that implements ordered, in-memory containers that are based on a B-tree-like data structure.

Like STL deque, our chunkedseq data structure supports fast constant-time update operations on the two ends of the sequence; and like balanced tree structures, such as STL rope, our chunkedseq supports efficient logarithmic-time split (at a specified position) and merge operations. However, unlike prior data structures, ours provides all of these operations simultaneously. Our research paper presents evidence to back this claim.

Key features of chunkedseq are:

• Fast constant-time push and pop operations on the two ends of the sequence.
• Logarithmic-time split at a specified position.
• Logarithmic-time concatenation.
• Familiar STL-style container interface.
• A segment abstraction to expose to clients of the chunked sequence the contiguous regions of memory that exist inside chunks.

Supported abstract data types

• Doubly ended queue
• Stack
• Bag
• Associative map

Advanced features

• Parallel processing
• Weighted container
• STL-style iterator
• Segments
• Customized data structures by cached measurement

Credits

The chunkedseq package is maintained by the members of the Deepsea Project. Primary authors include:

• Umut Acar
• Arthur Chargueraud
• Michael Rainey.