Re: std::set: gratuitous comparisons?
On Mar 18, 1:01 am, Gerhard Fiedler <geli...@gmail.com> wrote:
On 2008-03-17 16:52:42, Paul Brettschneider wrote:
Strange, I would have thought that something as fundamental as the
standard containers would be "optimised to death". But apparently not
so.
Maybe this behavior /is/ the optimal way to treat the problem?
It's not.
How could making a useless comparison be the optimal way? I doubt it
makes the code shorter, so there isn't even an instruction-cache
argument. And don't forget that we're talking about templates, so
compares might be quite expensive. All in all I must admit that I'm not
following you..
I haven't looked at this particular code to be able to say how
it is in this case (note the "maybe"), but what I'm saying is
that including special treatment for one case often adds code
that needs to be run in all other cases, too. And that can
invert the effect.
That's not the case here. The function which does the extra
comparison is (in this case) called from a function in a way
where the extra comparison will always have the same results.
The function itself is doubtlessly called from elsewhere, as
well, where the comparison is necessary, but it's short enough
that it could have been provided in two versions, one which
makes the comparison, and one which doesn't. (I suspect,
although I've not verified, that in the case of std::set and
std::map, the comparison is always superfluous; that it is only
necessary in the case of std::multiset and std::multimap.)
Whether it's worth it or not is another matter. If comparisons
are very expensive, and there are a lot of insertions, it
doubtless is. But if comparisons are very expensive, you'd
probably want to use a different data structure (maybe a hash
table) anyway. Still, at first glance, it didn't seem like a
difficult optimization.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34