473,245 Members | 1,613 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,245 software developers and data experts.

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 4030
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: Kin Pang | last post by:
Hi, I have a routine where I'm using a std::map from a pair of ints to double for caching evaluation results. The cache depth could be upto say 1000 in depth. However, my application needs to...
44
by: jmoy | last post by:
I am a C programmer graduating to C++. As an exercise I wrote a program to count the number of times that different words occur in a text file. Though a hash table might have been a better choice,...
0
by: Erik Arner | last post by:
Hi, let's say I have a std::map<std::string,int> and I want to search the map for all keys that start with "foo". The regexp equivalent is to search for "foo*", or perhaps "^foo*". At present...
19
by: Erik Wikström | last post by:
First of all, forgive me if this is the wrong place to ask this question, if it's a stupid question (it's my second week with C++), or if this is answered some place else (I've searched but not...
3
by: Dan Trowbridge | last post by:
Hi everyone, In my attempt to port code from VS 6.0 to VS.NET I had some code break along the way, mostly due to not adhereing closely to the C++ standard. This may be another instance but I...
20
by: Dilip | last post by:
I understand the C++ standard does not talk about threading. My question here is directed more towards what happens when a STL container is used in a certain way. I'd appreciate any thoughts. I...
2
by: digz | last post by:
Hi, I am trying to write a program which has two threads one of them write to a map , and the other one deletes entries based on a certain criterion.. first I cannot get the delete portion to...
4
by: bb | last post by:
Hi, void fun(const std::map<std::string,int>& m1) { // How to make a case insensitive search of this map without making a copy? } cheers.
2
by: pssraju | last post by:
Hi, At present application was built on solaris 9 using sun studio 9 (Sun C++ 5.6) & rouguewave sorce pro 5. We are planning to port the same application onto SuSE Linux 9.5.0 using GCC 3.3.3 & RW...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.