On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostw rote:
Hi,
<mveyg...@gmail .comwrote in message
news:1f******** *************** ***********@c4g 2000hsg.googleg roups.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, stringDict;
Dict[ "boek" ] = "book";
Dict[ "winkel" ] = "shop";
map<string,stri ng>::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_tim e()
{
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.pus h_back(i);
}
std::random_shu ffle(test_vecto r.begin(), test_vector.end ());
time_t seed = time(NULL);
srand(seed);
unsigned long vec_start = get_current_tim e();
for(unsigned int i=0; i < 500000; ++i)
{
unsigned int value_to_find = rand() % 1000000;
std::vector< unsigned int >::const_iterat or end_itr =
test_vector.end ();
std::vector< unsigned int >::const_iterat or itr =
test_vector.beg in();
for( ; itr == end_itr ; ++itr )
{
if( *itr == value_to_find )
{
break;
}
}
}
unsigned long vec_end = get_current_tim e();
srand(seed);
unsigned long map_start = get_current_tim e();
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(v alue_to_find);
}
unsigned long map_end = get_current_tim e();
std::cout << "Vec Test took " << (vec_end - vec_start) << "
microseconds. Map test took " << (map_end - map_start) << "
microseconds." << std::endl;
}
