Brodnik's data structure in practice, revisited

Abstract

In 1999, Brodnik et al. proposed an alternative data structure to dynamic arrays for efficient data stream processing. Despite its theoretical promise, this structure has received limited implementation and evaluation on modern computer architectures. This work presents a novel C++-compatible implementation of Brodnik's structure, specifically designed as a container for use with the stack adapter. We evaluate the performance of this implementation across different application scenarios, including sorting and examining its effectiveness as the underlying container for priority_queue, and stack adapters. When employed as the underlying container for stack operations, our implementation demonstrates significant time performance advantages over the standard vector implementation while achieving substantial space savings. Compared to the default stack container, deque, Brodnik's structure matches the temporal performance while delivering improved space efficiency. These results establish the practical viability of Brodnik's theoretical framework in contemporary computing environments and highlight new opportunities for efficient data stream processing in performance-critical applications.