Re: [boost] Container optimized for "insert once"

From: Peter Dimov (pdimov_at_[hidden])
Date: 2004-09-07 16:32:12

Rob Stewart wrote:
> From: Stefan Slapeta <stefan_at_[hidden]>
>>
>> I'm looking for an associative container which is optimized for
>> one-time insertion and avoids much of the overhead of std::map
>> therefore. IIRC Andrei once published something like this: a vector
>> of pairs that was sorted once and accessed by binary search.
>
> std::vector + std::sort + std::binary_search?
>
> (You'd populate the vector with your data, run std::sort on it,
> and then just use std::binary_search from that point forward.)
>
> Other search algorithms which might prove more efficient for your
> data type, of course.

FWIW, if you decide to go with the above, be sure to profile it against a 
std::map first. You may be surprised. Not to mention hash_map, if you have 
one.