Re: Performance of the std::map during a search
<mveygman@gmail.com> wrote in message
news:d2e7c7db-4636-4e17-8c30-dd4aa5f41b9b@s19g2000prg.googlegroups.com...
On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhost> wrote:
Hi,
<mveyg...@gmail.com> wrote in message
news:1f4f63f2-3359-44a2-a8d4-ad6a35776931@c4g2000hsg.googlegroups.com...
Hi,
I am writing code that is using std::map and having a bit of an issue
with its performance.
It appears that the std::map is significantly slower searching for an
element then a sequential search in a vector.
Here is the test code:
....
int main(int argc, char **argv)
{
std::map< unsigned int, unsigned int > test_map;
std::vector< unsigned int > test_vector;
std::cout << "Setting up the test" << std::endl;
for (unsigned int i=0; i < 1000000; ++i)
{
test_map[i]=i;
test_vector.push_back(i);
}
std::random_shuffle(test_vector.begin(), test_vector.end());
time_t seed = time(NULL);
srand(seed);
unsigned long vec_start = get_current_time();
for(unsigned int i=0; i < 500000; ++i)
{
unsigned int value_to_find = rand() % 1000000;
std::vector< unsigned int >::const_iterator end_itr =
test_vector.end();
std::vector< unsigned int >::const_iterator itr =
test_vector.begin();
for( ; itr == end_itr ; ++itr )
Since itr == end_itr is always false, the loop always exists immediatly, so you
don't search the vector at all.
This should be itr != end.
If I change this, the vector version takes a lot more time .
{
if( *itr == value_to_find )
{
break;
}
}
}
unsigned long vec_end = get_current_time();
srand(seed);
unsigned long map_start = get_current_time();
for(unsigned int i=0; i < 500000; ++i)
{
unsigned int value_to_find = rand() % 1000000;
std::map< unsigned int, unsigned int >::iterator itr =
test_map.find(value_to_find);
}
unsigned long map_end = get_current_time();
std::cout << "Vec Test took " << (vec_end - vec_start) << "
microseconds. Map test took " << (map_end - map_start) << "
microseconds." << std::endl;
}