468,504 Members | 1,992 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,504 developers. It's quick & easy.

Performance of the std::map during a search

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?

Dec 22 '07 #1
8 3538
mv******@gmail.com wrote:
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.
The elements in a map are sorted on insertion, what are you attempting
to do?

--
Ian Collins.
Dec 22 '07 #2
Hi,
<mv******@gmail.comwrote in message
news:1f**********************************@c4g2000h sg.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, stringDict;
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
Dec 22 '07 #3
On 2007-12-22 00:57, mv******@gmail.com wrote:
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.
For small collections that might be true, but for larger sets map should
be faster (if used correctly), unless perhaps if the vector is sorted
and you use a binary search.

--
Erik Wikstr├Âm
Dec 22 '07 #4
On Dec 22, 8:46 am, Erik Wikstr÷m <Erik-wikst...@telia.comwrote:
On 2007-12-22 00:57, mveyg...@gmail.com wrote:
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.

For small collections that might be true, but for larger sets map should
be faster (if used correctly), unless perhaps if the vector is sorted
and you use a binary search.

--
Erik Wikstr÷m

Operating key word being "should".

The assumption that I went in with was that this was the case and
worst case scenario would be that serial search of the vector and
serial search of the map would be on par for time. They are not even
close.

Regards,

Mikhail
Dec 24 '07 #5
On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostwrote:
Hi,

<mveyg...@gmail.comwrote in message

news:1f**********************************@c4g2000h sg.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, stringDict;
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;
}
Dec 24 '07 #6

<mv******@gmail.comwrote in message
news:d2**********************************@s19g2000 prg.googlegroups.com...
On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostwrote:
>Hi,

<mveyg...@gmail.comwrote in message

news:1f**********************************@c4g2000 hsg.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;
}
Dec 24 '07 #7
On Dec 24, 11:44 am, "Hans Bos" <hans....@xelion.nlwrote:
<mveyg...@gmail.comwrote in message

news:d2**********************************@s19g2000 prg.googlegroups.com...
On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostwrote:
Hi,
<mveyg...@gmail.comwrote in message
>news:1f**********************************@c4g2000 hsg.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;
}

That would explain everyting. :)))
Dec 24 '07 #8
On 2007-12-24 17:04, mv******@gmail.com wrote:
On Dec 22, 8:46 am, Erik Wikstr├Âm <Erik-wikst...@telia.comwrote:
>On 2007-12-22 00:57, mveyg...@gmail.com wrote:
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.

For small collections that might be true, but for larger sets map should
be faster (if used correctly), unless perhaps if the vector is sorted
and you use a binary search.

--
Erik Wikstr├Âm


Operating key word being "should".

The assumption that I went in with was that this was the case and
worst case scenario would be that serial search of the vector and
serial search of the map would be on par for time. They are not even
close.
Searching a map is O(log n) while a sequential search of a map is O(n),
which means that when the number of elements is large a map should be
faster. Exactly how many elements you need to have before the map is
faster depends on a lot of things but I would guess that with 1000
elements the map is almost always faster on a modern PC. On the other
hand if the vector is sorted then it might be faster searching the
vector using lower_bound() which is also O(log n), but most other
operations will still be faster on the map.

--
Erik Wikstr├Âm
Dec 25 '07 #9

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by Kin Pang | last post: by
44 posts views Thread by jmoy | last post: by
reply views Thread by Erik Arner | last post: by
19 posts views Thread by Erik Wikstr÷m | last post: by
2 posts views Thread by digz | last post: by
4 posts views Thread by bb | last post: by
reply views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.