Yes, exactly. One thing to keep in mind is that it's surprisingly common for a sorted array to outperform a binary search tree because of cache locality and po

Yes, exactly. One thing to keep in mind is that it's surprisingly common for a sorted array to outperform a binary search tree because of cache locality and pointer indirection being slow, even though random inserts into arrays are slow. Especially for small sets or when reads greatly outnumber writes. Boost has flat_map and flat_set for this.