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.