C++Talk.NET

Hans Aberg · Guest

I want to report that I for some time have been using a relations type
that I think might be suitable if say the C++ libraries should be
revamped. For example, the C++ associative containers library defines "x
is equal to y" with respect to a relation "<" to mean that "x < y && y <
x", which for example causes associative containers (as in the case of
std::set and std::map) to make two "<" comparisons" if there is a need to
make sure that a duplicate is not inserted.

The type I use is suitable for a relation "R" comparisons when there is a
need to know what both x R y and y R x are (as n the case of the
associative containers. I use the implementation (which says it all about
this type:
typedef int relate;

const relate unrelated = -2;
const relate less = -1;
const relate equal = 0;
const relate greater = 1;
The value unrelated = -2 covers up all the four possibilities in a typical
two bit signed integer implementation.

This then follows C/C++ conventions that for say
std::string x, y;
x.compare(y) is:
negative <=> x less than y
0 <=> x equal to y
positive <=> x greater than y
With the "relate" type, the return values now becomes specific.

I have found it useful to write functions like:
template<class X, class Y>
relate inequality_compare(const X& x, const Y& y) {
if (x < y) return less;
if (x > y) return greater;
if (x == y) return equal;
return unrelated;
}
I formerly experimented with the sgn function, but it turns out the there
is a risk of failure in the case of unsigned returns, e.g., the following
does not work:
unsigned x, y;
relate r = sgn(y - x);
because y - x will be treated as unsigned, and never can become negative.
One must write something like
relate r = sgn((int)y - (int)x)
but then some of the unsigned values of x and y become unusable for
correct comparisons. Hence, functions like inequality_compare seems
safest.

The C++ std containers lib comparison definition can be covered up by
using the function:
template<class X>
relate less_compare(const X& x, const X& y) {
if (x < y) return less;
if (y < x) return greater;
return equal;
}
If one has a relation object R that returns bool value, one might define
(pseudocode):
template relate relation_compare(const X& x, const X& y, const R& r) {
relate r1 = r(x, y), r2 = r(y, x);
if (r1 && !r2) return less;
if (r1 && r2) return equal;
if (!r1 && r2) return greater;
return unrelated;
}
which at least explains the connection between relations in the
traditional sense and the "relate" type.

Also, I found it useful to use two comparison functions
compare can return any "relate" value
total total order function, only returns the values less,
equal, greater; if an "unrelated" value situation cannot be
avoided, an exception should be thrown.
For example, a type like std::pair<int, int> has a natural total order,
the lexicographical order induced from "int", but no natural semantic
order function "compare".

The total order function "total" is the one to use if elements need to be
sorted in an associative containers without regards to its semantic
comparison: Sorting goes faster with it present even though it need not be
semantic with respect to the types innate value.

It is a function that C++ might supply by lexicographical ordering of
class data members (for pointers, either use dereferenced value, or let
the user indicate whether pointer or dereferenced value should used). The
point with it is that one can always put data types into an associative
container without having o worry about defining a comparison function
first.

By contrast, types need not have any natural semantic "compare" function
at all (as in the example std::pair<int, int> above).

Hans Aberg * Anti-spam: remove "remove." from email address.
* Email: Hans Aberg <remove.haberg (AT) member (DOT) ams.org>
* Home Page: <http://www.math.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]