Re: performance of map in MSVC 10b2
On Thu, 8 Apr 2010 03:33:00 CST, Ulrich Eckhardt <eckhardt@satorlaser.com> wrote:
Maps are trees, sorted by the key. Since your key increases monotonically,
every time you insert an element that insert takes place at the same branch
of the tree, so it becomes unbalanced.
No it doesnt. The trees used are self-balancing like Red-Black trees, AVL trees,
Scapegoat Trees
If they were not self-balancing, the complexity requirements for std::map would
not be met.
This doesn't help performance at
all.
Nonsense. He should be able enter key-values pairs in montonically increasing
order, decreasing order, random order and it
should make no real difference to speed of std::map.find(). The only increase of
speed whould be a suitable hint for insert().
I don't know enough about how the unordered_maps are implemented to make an
educated guess about their behaviour.
The are implemented using hashing.
for(int i=0; i<size; ++i) {
buff = imap[i];
}
This test is fine, unless of course the map stays unbalanced somehow, which
would mess up the lookup time.
This can happen if keys hash to the same collision point.
But unordered_map should at some point grow and rehash.
Stephen Howe
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]