Cache-Friendly Search Trees; or, In Which Everything Beats std::set

Jeffrey Barratt, Brian Zhang

While a lot of work in theoretical computer science has gone into optimizing the runtime and space usage of data structures, such work very often neglects a very important componen…