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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk