2005-07-23

Note to self: lexicographic ordering

The following (pseudo-C++) code is the correct way of writing lexicographic "less than" function for the tuple of two items:

bool less_than(const pair &p1, const pair &p2)
{
if(p1.first == p2.first)
return p1.second < p2.second;
return p1.first < p2.first;
}
This code cannot be rewritten using only boolean operators. My mistake was writing

return
(p1.first < p2.first) ||
(p1.second < p2.second);
This does not work! Analogous combination with && also doesn't work. It could be rewritten to use the ?: operator, but with doubtful benefits. Note to self: don't try being too smart again!

1 comment:

Anonymous said...

We follow two rules in the matter of optimization:
Rule 1. Don't do it.
Rule 2 (for experts only). Don't do it yet - that is, not until you have a perfectly clear and unoptimized solution.
-- M. A. Jackson