Re: Performance of the std::map during a search
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.
Has anyone run into this before?
Do you use map.find ? Otherwise post some code.
e.g.
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
map<string, string> Dict;
Dict[ "boek" ] = "book";
Dict[ "winkel" ] = "shop";
map<string,string>::iterator Found = Dict.find( "boek" );
if( Found != Dict.end() )
{
cout << Found->first << " translates to " << Found->second << " (or
vice versa) " << endl;
}
else
{
cout << "No such word" << endl;
}
return 0;
}
Regards, Ron AF Greve
http://www.InformationSuperHighway.eu
Here is the test code:
#include <map>
#include <vector>
#include <iostream>
#include <ostream>
#include <sys/time.h> /* gettimeofday */
unsigned long get_current_time()
{
struct timeval tv;
long usec;
gettimeofday (&tv, NULL);
usec = tv.tv_sec * 1000000;
usec += tv.tv_usec;
return usec;
}
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 )
{
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;
}