Checking if integer falls in range using only < operator

Question

I need to come up with some code that checks if a given integer falls within the bounds of a range. (The range is represented by a pair of integers.)

So, given a range r defined as an std::pair<int, int>, and a test integer n, I want to say:

if (n >= r.first && n <= r.second)

The catch is, I need to use a std::less<int> comparison functor to do this, which means I can only work with the less than operator.

I'm trying to come up with the equivalent expression. I'm pretty sure I have it correct, but I'm not entirely confident.

The expression I came up with is:

( !cmp(n, r.first) && !cmp(r.second, n) )

where cmp is an instance of std::less<int>

Did I do that correctly?

Answer 1

Polling others is not the best way to verify correctness. :)

Instead, consider your problem. Everything you are dealing with is an int, so all values involved can be represented as an int. No addition or subtraction is involved, so you needn't worry about leaving the representable range. So, we can fall back to standard math using standard integers, and leave the messiness of machine representations behind.

You are given a range closed at both ends [n, m] and a value p to test for membership in that range. You have one operator on integers that you can use, <. All the standard boolean operators are fair game.

Now, you can simply think about sets. You want to reject all p such that p < n or p > m. All other values of p are acceptable. Put another way, p is part of the desired set if

not ((p < n) or (m < p))

Using DeMorgan's laws, this is equivalent to

(not (p < n)) and (not (m < p))

Representing that using the standard C++ operators (rather than the alternative spellings provided by <iso646.h>), we get what you proposed, but using different names:

!<(p, n) && !<(m, p)

Renaming <() to cmp(), n to r.first, m to r.second, and p to n, we get precisely what you proposed:

!cmp(n, r.first) && !cmp(r.second, n)

So, yup, looks correct to me.

Answer 2

Yes, not of less-than is equivalent to greater than or equal to, in fact in many older programming languages <= is actually called ngt for not greater than and >= is nlt