Optimization of STL map's find

[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

[Kai-Uwe Bux]

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

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

[Michael]

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

[Thorsten Kiefer]

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

[Ron Natalie]

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

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

[Frank Puck]

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