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?

Reputation: 3122

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

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?

Upvotes: 2

Answers (3)

Fred Nurk

Reputation: 14212

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.

Upvotes: 1

fabmilo

Reputation: 48310

A binary search tree.

Upvotes: 0

xscott

Reputation: 2420

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

Upvotes: 0

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

Answers (3)

Related Questions