Most efficient data structure: Fast sorted insertion, closest value searching

Question

Basically:

• Fast, sorted insert.
• Returns position of where an item would be inserted if it's not found in the data structure.

An array with binary search satisfies my second requirement, but it's still prohibitively slow for insertion. What solution might work best?

Answer 1

Red-black trees and skip lists meet your requirements, among others. For an example in C++, look at std::set, std::map, etc. and their lower_/upper_bound and equal_range methods.

Answer 2

Many flavors of search tree fit your requirements. I'd use a 2-3 tree, or maybe a treap if I was feeling lazy.

Answer 3

A binary search tree.