S
Siemel Naran
jmoy said:Thanks everybody for your interest. To eliminate possible overhead
from std::string, I used char * (code below). But the gain is only
about 5%. Profiling shows that both in the earlier and latter versions
most of the time is taken by the function _Rb_tree::lower_bound which
is called by map::lower_bound (in the original case this is in turn
called by map:perator[]).
Take a look at lower_bound in tree.h (or some name like _tree.h or
stl_tree.h). It's pretty straightforward. Then compare it to your own
version and see what's different. Also, what does your profiler say about
functions that lower_bound calls, as maybe the bottleneck is here?
Maybe instruction page caching. But just a wild guess.
Instead of the code below, you could try tom_usenet's reading into a string
idea, which seems like it does the same thing, but looks simpler.
struct Cstring_less
{
bool operator()(const char *s, const char *t) const{
return strcmp(s,t)<0;
}
};
typedef std::map<const char *,long,Cstring_less> Map;
Map words;
const long maximum=std::numeric_limits<long>::max();
void insert(const char *s)
{
Map::iterator p=words.lower_bound(s);
if (p==words.end()||strcmp(p->first,s)!=0){//Not found
char *dup=new char[strlen(s)+1];
strcpy(dup,s);
std:
p=words.insert(p,tuple);
}else{//Found
if (p->second<maximum)
p->second++;
}
}