Re: performance of map in MSVC 10b2
??? 2010-4-8 17:33, Ulrich Eckhardt ??????:
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. This doesn't help performance at
all. Suggestion: Unless this really represents your use case, I would
create a vector first, fill it like above and then shuffle the elements,
before using them as keys to insert.
i think you and Gordan are right, so i add 2 random_shuffle() in my new
test code, here comes the result:
MAP INSERT LOOKUP
std::map 26.59s 23.83s
boost::unorder_map 8.06s 3.77s
std::unorder_map 11.66s 5.95s
and the code is:
//---------------------------------------------------------
#define _SECURE_SCL 0
#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <boost/unordered_map.hpp>
#include <boost/progress.hpp>
using namespace std;
int main()
{
typedef std::unordered_map<int, string> map_t;
//typedef boost::unordered_map<int, string> map_t;
//typedef std::map<int, string> map_t;
const int size = 1E7;
vector<int> key_arr(size);
for(int i=0; i<size; ++i) {
key_arr[i] = i;
}
random_shuffle(key_arr.begin(), key_arr.end());
map_t imap;
{
boost::progress_timer t1;
boost::progress_display prog_bar(size);
for(int i=0; i<size; ++i) {
imap[ key_arr[i] ] = "test";
++prog_bar;
}
}
random_shuffle(key_arr.begin(), key_arr.end());
{
boost::progress_timer t2;
string buff;
for(int i=0; i<size; ++i) {
buff = imap[ key_arr[i] ];
}
}
return 0;
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]