473,323 Members | 1,551 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,323 software developers and data experts.

Optimization of STL map's find

Hi,

I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".

One of my classes possesses an STL map of the structure

map< string, string myMap;

The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );

map< string, string >::const_iterator it = myMap.find( tmp.c_str() );

if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}

// Otherwise
string myString( lab );

return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?

And in general, do you have any suggestions how to improve the function
"findString"?

Regards,
Chris
Aug 6 '06 #1
7 6072
Christian Christmann wrote:
Hi,

I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".

One of my classes possesses an STL map of the structure

map< string, string myMap;

The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );

map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
map< string, string >::const_iterator it = myMap.find( tmp );
>
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
return it->second;
}

// Otherwise
string myString( lab );
Why again?

return tmp;
>
return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?
You could try a different comparison predicate: if many of your string have
a common prefix, lexicographic comparison may look at many characters
before being able to decide. In this case, short-lex order could take
advantage of strings being of different lengths.

Also, if your map is more or less static, i.e., built once and used
afterward for searching only, you could use

std::vector< std::pair< std::string, std::string

instead: put all pairs in there, sort, and do table lookup by binary search.
However, that should not make a big difference.

Another option is to use an unordered_map instead where you can play around
with a hash function.
And in general, do you have any suggestions how to improve the function
"findString"?
See above: I wondered why you are going through c_str(). Your map knows
strings, just use them.
Best

Kai-Uwe Bux
Aug 6 '06 #2
Christian:

Try implementing something like this:

//your map deffinition (take care of the memory!!!)
typedef map< string, string* my_map_t;

//your function deffinition
const string & findString( const string & lab );
const string & findString( const char * lab );

This way, the map::find funciton itself will execute more efficiently,
and you wont have to dereference the pointer or create a temp object in
your function, just return a reference to the map's string.

Hope this help.
Christian Christmann wrote:
Hi,

I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".

One of my classes possesses an STL map of the structure

map< string, string myMap;

The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );

map< string, string >::const_iterator it = myMap.find( tmp.c_str() );

if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}

// Otherwise
string myString( lab );

return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?

And in general, do you have any suggestions how to improve the function
"findString"?

Regards,
Chris
Aug 6 '06 #3

flagos wrote:
Christian:

Try implementing something like this:

//your map deffinition (take care of the memory!!!)
typedef map< string, string* my_map_t;

//your function deffinition
const string & findString( const string & lab );
const string & findString( const char * lab );

This way, the map::find funciton itself will execute more efficiently,
and you wont have to dereference the pointer or create a temp object in
your function, just return a reference to the map's string.

Hope this help.
Coud you please explain why this way helps memory? And, how?

Michael

Aug 6 '06 #4
Christian Christmann wrote:
string findString( const char *lab )
{
string tmp( lab );

map< string, string >::const_iterator it = myMap.find( tmp.c_str() );

if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}

// Otherwise
string myString( lab );

return myString;
}
Try this:
inline string findString( const char *lab )
{
map< string, string >::const_iterator it = myMap.find(lab);

if ( it != myMap.end() ) {
return it->second;
}

// Otherwise
return lab;
}

If this makes compile errors, try this:
inline string findString( const char *lab )
{
map< string, string >::const_iterator it = myMap.find(string(lab));

if ( it != myMap.end() ) {
return it->second;
}

// Otherwise
return string(lab);
}

Regards
Thorsten

Aug 6 '06 #5
Christian Christmann wrote:
Hi,

I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".

One of my classes possesses an STL map of the structure

map< string, string myMap;

The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );

map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
I'm confused as to why you make a local string object here and then
convert back to char* to then pass it back to something expecting a
string.
>
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
Again, why the temporary? etc...
}

// Otherwise
string myString( lab );

return myString;
}
You might want to consider putting the string in the map. in the
case it's not found. Any how, the below is a more succint way
of expressing the exact same thing (without all the extra copies).

string findString(const char* lab) {
map<string, string>::const_iterator it = myMap.find(lab);
if(it != myMap.end()
return it->second;
else
return lab;
}
Aug 6 '06 #6
If this makes compile errors, try this: inline string findString( const
char *lab ) {
map< string, string >::const_iterator it = myMap.find(string(lab));

if ( it != myMap.end() ) {
return it->second;
}
}
// Otherwise
return string(lab);
}
}
Just another idea: In order to avoid calling string's constructor, one
could return a reference:

inline const string& findString( const string&lab ) {
map< string, string >::const_iterator it = myMap.find(lab);

if ( it != myMap.end() ) {
return it->second;
}

// Otherwise
return lab
}


Aug 6 '06 #7

"Christian Christmann" <pl*****@yahoo.dewrote in message
news:44***********************@newsread4.arcor-online.net...
Hi,

I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".

One of my classes possesses an STL map of the structure

map< string, string myMap;

The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );

map< string, string >::const_iterator it = myMap.find( tmp.c_str() );

if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}

// Otherwise
string myString( lab );

return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?

you could use what I call a string-tree:

template<class T>

class CStringTree

{ private:

std::auto_ptr<CStringTreem_sChildren[256];

T m_s;

public:

void addEntry(const char *_p, const T &_r)

{ if (*_p)

{ if (!m_sChildren[*_p].get())

m_sChildren[*_p] = std::auto_ptr<CStringTree>(new
CStringTree);

m_sChildren[*_p].get()->addEntry(_p + 1, _r);

}

else

{ if (!m_sChildren[0].get())

m_sChildren[0] = std::auto_ptr<CStringTree>(new
CStringTree);

m_sChildren[0].get()->m_s = _r;

}

}

const T *findEntry(const char *_p)

{ if (*_p)

if (!m_sChildren[*_p].get())

return 0;

else

return m_sChildren[*_p].get()->findEntry(_p + 1);

else

if (!m_sChildren[0].get())

return 0;

else

return &m_sChildren[0].get()->m_s;

}

};
Creating an entry in a string tree may take more time than creating an entry
in a map.
But finding an entry is considerable faster.

Aug 6 '06 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Dave | last post by:
Hello all, I have written an expression interpreter, and a profiler has told me that a specific part of it is in need of optimization. My purpose in posting to this newsgroup is to solicit...
3
by: mcassiani | last post by:
Hi, I need use map faster as possible (I store in the map data about open network connections). First a question, this code fragment is from "The C++ Programming........
10
by: MariusI | last post by:
I stumbled over an optimization (or lack of one, to be specific) when viewing IL opcodes generated by the compiler using ms .net 2003. I was testing fast pixel manipulation using Bitmap.LockBits...
3
by: Jazzkt | last post by:
I wrote a little code using the map container available in the STL of C++. The trouble I am having is that the find() member function is working properly. When I try to find a key, if that key is...
4
by: Mervin Williams | last post by:
I am building a web application that will have a single form that will be populated with data from 8-10 tables. The easiest way to implement the data tier would be to use DataSets and Data...
0
by: Ole Nielsby | last post by:
I just wonder if this is possible with C++/clr. I'm trying to .NET-enable an interpreter for a Lisp flavoured language, the interpreter written in NASM which I have managed to port to MASM....
3
by: telnet2008 | last post by:
Hi,everyone: the questionly code: #include <iostream> using namespace std; class test { int x;
6
by: wqe | last post by:
Hi,everyone: the questionly code: #include <iostream> using namespace std; class test { int x;
6
by: baudolino | last post by:
I have a map<string, time_t>; string represents a filesystem path, time_t is a timestamp associated with that path. My problem is to find the best version of a directory and its subdirectories,...
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: 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...
1
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...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

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.