Comment by detrino

Re benchmarking vs other data structures: Here is a B+Tree based sequence container I made: https://github.com/det/segmented_tree

Basically, it has O(log n) everything like a binary search tree you suggested but also very good constant factors.

By default, leaves hold 1024/sizeof(T) elements and branches hold 47 elements, so it can access up to 13,289,344 8 byte elements with only 4 levels.