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

From: David B. Held (dheld_at_[hidden])
Date: 2004-09-07 23:51:55

Peter Dimov wrote:
> Rob Stewart wrote:
>> [...]
>> 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.

I'm not so sure speed is the issue vs. size.  Your typical std::map<>
implementation will take about 3 pointers + int + sizeof(data) per node,
whereas std::vector<> typically only has whole-container overhead.
Unless your nodes are extremely large, that's not an insignificant
amount of space overhead if you are only going to insert once.

Dave