flatsets

Flatsets are set-like containers that store elements in a flat, contiguous sequence, typically a dynamically sized array. The elements are kept in a defined order, usually determined by a comparator, and duplicate elements are not allowed. The flat storage favors cache locality and compact memory usage compared to tree-based structures.

Operations on a flatset rely on the sorted arrangement. Membership tests, insertions, and deletions are usually implemented with binary search to locate positions, and insertions must place new elements at the correct sorted position while ensuring there are no duplicates. Iteration over a flatset yields elements in their sorted order, and range queries can leverage the same contiguous storage.

Performance characteristics differ from other common set implementations. Lookups generally run in O(log n) time due to binary search, while insertions and deletions can be O(n) in the worst case because elements may need to be shifted to maintain the sorted order. However, because storage is contiguous, traversal and iteration are typically very fast, and memory overhead is often lower than in tree-based sets or hash-based containers. Building a flatset from a sorted sequence can be done in linear time.

Use cases for flatsets include read-heavy workloads with relatively small to medium-sized sets, where fast iteration and compact memory footprint are important and the cost of inserting new elements is acceptable. They are commonly implemented as a wrapper around a vector, and are an alternative to std::set or std::unordered_set when the data access pattern benefits from contiguity and sorted storage.