Optimization of STL map's find

  • Thread starter Christian Christmann
  • Start date
C

Christian Christmann

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
 
K

Kai-Uwe Bux

Christian said:
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 said:
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
 
F

flagos

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.
 
M

Michael

flagos said:
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
 
T

Thorsten Kiefer

Christian said:
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
 
R

Ron Natalie

Christian said:
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;
}
 
C

Christian Christmann

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
}
 
F

Frank Puck

Christian Christmann said:
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<CStringTree> m_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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top