From: Peter Dimov (pdimov_at_[hidden])
Date: 2004-09-08 06:18:17
Stefan Slapeta wrote:
> David B. Held wrote:
>
>> 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.
>
> Yes. Furthermore, a default constructed vector is usually small and
> cheap, a map isn't (there is always at least one node instantiated).
Your call. I was just saying that you shouldn't take claims that a
vector<pair> is faster than a map for granted. BTW, pair<vector> has better
cache coherency and hence slightly faster lookups, and you get to use the
non-predicate version of lower_bound, which has lower abstraction penalty.