What is it?
The Black-White Array (aka BWArr) is a fast, ordered data structure based on arrays with $O(\log N)$ memory allocations.
Data Structure
The idea of Black-White Array was invented and published by professor Z. George Mou in Black-White Array: A New Data Structure for Dynamic Data Sets. This repository contains the first public implementation.
Key features:
$O(\log N)$ memory allocations for Inserts - no pressure on GC;
memory allocations for Inserts - no pressure on GC; Fast insert, delete, and search operations $O(\log N)$ time amortized complexity;
time amortized complexity; Array-based and pointerless makes it CPU-friendly: cache locality / sequential iteration / etc;
Supports duplicate elements natively (multiset behavior) - no need for wrapping values into structs to make them unique;
Drop-in replacement for github.com/google/btree and github.com/petar/GoLLRB ;
... continue reading