Pavol Droba wrote in
news:20060307091753.GU793@lenin.felcer.sk:
On Fri, Mar 03, 2006 at 11:29:58PM +0100, Olaf van der Spek wrote:
Well, this is a more complicated point. Small optimization you are
proposing does not really make any difference. I have read a paper
(I don't remember where),
Why not? Isn't a simple compare much faster than two table lookup?
Ok, maybe you are right. One compare will not cost much and it can
speedup few cases.
where author proposes to cache the results of tolower during the
comparison.
I'm not sure how that would work, could you explain?
I don't remember the details. The idea was to eliminate some of the
virual calls, that take place when dealing with locales. The algorihtm
was described on several pages. Unfortunaltely, I forgot where I have
seen that paper.
Regards, Pavol
I believe what you are looking for is found in Effective STL by Scott
Meyers (pages 229-237). On page 236-237 he writes a case insensitive
string comparison functor that has this optimization, here it is:
struct lt_str_2 :
public std::binary_function
{
struct lt_char {
const char* tab; lt_char(const char* t) : tab(t) {} bool
operator()(char x, char y) const {
return tab[x-CHAR_MIN] < tab[y-CHAR_MIN];
}
};
char tab[CHAR_MAX - CHAR_MIN + 1]; lt_str_2(const std::locale& L =
std::locale::classic()) {
const std::ctype<char>& ct = std::use_facet(L);
for (int i=CHAR_MIN; i<=CHAR_MAX; ++i)
tab[i-CHAR_MIN] = (char)i;
ct.toupper(tab, tab + (CHAR_MAX - CHAR_MIN + 1));
}
bool operator()(const std::string& x, const std::string& y) const {
return std::lexicographical_compare(x.begin(), x.end(),
y.begin(), y.end(),
lt_char(tab));
}
};
He then talks about the pros and cons of this. "This isn't a fully
general solution ..., if your were working with 32-bit UCS-4
characters." "This might be slower if you're creating an lt_str_2
function object, using it to compare a few short string, and then
throwing it away." "For any substantial use, though, lt_str_2 will be
noticeable faster"
I hope that I am allowed to reproduce this. If I am not, I humbly ask
Scott Meyers for forgiveness.
Andy
