Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Comparison and Inheritance

February 22, 2013

We continue last week's discussion of comparison functions by thinking about how to compare objects from different parts of an inheritance hierarchy.

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

Suppose we have a Vehicle class from which we have derived Car, Truck, and other classes such as Airplane. How do we go about defining comparisons between objects of these various classes that will meet the C++ ordering requirements in a useful way?

Implementing these comparisons will have its own problems, because C++ objects are not polymorphic by themselves. To take advantage of polymorphism in C++, we must use pointers or references, perhaps directly, or perhaps through some kind of smart pointer class. Nevertheless, it is probably useful to think about the characteristics that such comparison functions might have before we worry about the details of implementing them.

The obvious problem in defining such operations is that there might well be an obvious strategy for comparing one Car with another, or one Truck with another — but it might not be obvious how to extend this strategy to allow comparing a Car with a Truck. For example, every Car might have a serial number, and every Truck might have a serial number, but these two kinds of serial numbers might be in completely different formats.

One's first temptation might be to use the obvious methods of comparing serial numbers between two objects of the same type, and then to say that two objects of different types are unrelated. In other words, define the < operation on two Vehicle objects to return false unless the two objects have the same type. In that case, < should compare the objects' contents (serial numbers, or any other of the objects' aspects we might choose).

This strategy is a disaster. To see why, consider two Car objects c1 and c2, and a Truck object t. Under this definition, c1 is unrelated to t, t is unrelated to c2, but one of c1 < c2 and c2 < c1 will be true. This behavior violates the C++ rules for order relations, because the unrelated operation is not transitive. In effect, when you're designing a comparison function, you should think of unrelated as meaning conceptually equivalent.

With this insight, let's revisit our original problem: We know how to compare two Cars, we know how to compare two Trucks, and we need to figure out how to compare a Car with a Truck. We can imagine this problem as if we had two stacks of cards, representing Cars and Trucks, respectively, and we want a way to shuffle these stacks of cards together into a single stack, while still preserving the ordering within each of the original stacks.

If the problem is described that way, it should be obvious that the easiest way to solve it is to put one stack on top of the other. Translating this solution into a comparison function is trivial: We decree that an object of one type is always less than an object of the other type, and continue to use the comparisons that we have already defined within each type. Another way to look at this solution is that each object becomes a string of two symbols, where the first one is the object's type, and we define ordering as dictionary ordering over these two-symbol strings.

The more general kind of "shuffling" is harder to define, because we need to be able to compare objects of different types while ensuring that the results of such comparisons are always consistent with each other. However, using dictionary order suggests one way of doing it: We find a string — such as a serial number — that describes each object, and then create a pair in which the first component is that string and the second component represents the type.

This strategy suggests a general technique: Represent each object's contents with a canonical value — a value of a single, well-defined type that already has an order relation defined on it. Then use the canonical values for comparison, perhaps appending the object's type if we want two objects of different types with the same canonical value to be ordered rather than conceptually equivalent.

That's the general strategy. Now it's your turn. Imagine an inheritance hierarchy with Number at its root and Integer and Real each derived from Number. Assume that an Integer is a container for an int, and Real is a container for a float. How would you define a comparison operation between two Numbers? How would you implement it? Beware: This problem is nowhere near as simple as it looks.

Related Reading






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

Zenju
2013-03-04T11:33:00

You're right. I misunderstood your remark to mean under what conditions can an int be represented by a C++ floating point type, while you talk about the opposite.


Permalink
ubm_techweb_disqus_sso_-076d85ab5a7fb01e89d15e4edfae1101
2013-03-04T08:13:20

in the general case this is what I would write in the base class:
class Base {
private:
virtual CanonicalForm getCannonicalform() const;
public:
bool operator < ( const Base& rhs )
{
const CannonicalForm& thisCanon = getCannonicalForm();
const CannonicalForm& rhsCanon = rhs.getCannonicalForm();
return thisCanon < rhsCanon;
}

where CannonicalForm can be anything from a special class to typedef std::string - as long as operator < is defined for it.


Permalink
ubm_techweb_disqus_sso_-827827c1d5102104330baa57f274a72e
2013-03-04T05:07:16

I don't follow. Here is what I think:

32-bit floats have 23-bit stored significand (24 bits if you count the hidden integer bit). The first float in that range is 1.0 * 2^24 = 2^24 which is representable in a 32-bit int without loss of precision.

The next 2^24-1 floats have sequential significands which map directly into the LSBs of the int.

Then, the exponent increments once for 1.0 * 2^24 = 2^25. This means the LSB of the int is always zero from now on. Starting at 2^26, two LSBs are zero, etc.

1.111...1 * 2^31 = 2^32 - 2^8 is the last float less than 2^32, and so the last float that fits in int32. So technically the range should be [2^24, 2^32-2^8].

But I think all these floats are convertible without loss of precision.

Similar logic should apply for 64-bit doubles with 53-bit stored (54-bit real) significands converting into 64-bit ints.

Actually I'm not sure what you mean by "32-bit double". Does the integer word size affect the sizes of float and double?


Permalink
Zenju
2013-02-27T11:00:57

... and doubles,
it is neither true for 32-bit ints and floats, or 64-bit ints and double.


Permalink
Zenju
2013-02-26T10:12:13

That's only true for 32-bit ints...


Permalink
ubm_techweb_disqus_sso_-827827c1d5102104330baa57f274a72e
2013-02-26T06:07:01

For floats in [2^24, INT_MAX], just cast to int since they have higher precision over the entire range.


Permalink
ubm_techweb_disqus_sso_-af28bad802450c26670348557588396b
2013-02-25T23:35:42

How do I implement it? Tediously, that's how.

floats have a larger range than ints, but lesser precision.

Ignoring negative values for the moment:

1. floats < 2^24 should mesh with ints in same range simply by casting ints to float and comparing.

2. floats > INT_MAX compare greater than all ints.

3. floats in the range [2^24,INT_MAX] are tricky. In this range, casting ints to float may lose precision (which you can detect by doing a roundtrip cast). Pseudo-code:

if ( int(float(i)) != i )
{
// Precision lost
return i < int(f);
}
else
{
// Precision retained
return float(i) < f;
}

... or something like that. I get the feeling I'm missing a case but I don't have time to think about it right now...


Permalink
Zenju
2013-02-24T11:54:05

To compare unrelated types (and float and int are neither subsets of one another) one could first consider the polymorphic type, then compare on the derived types:

bool operator<(const Number& lhs, const Number& rhs)
{
if (typeid(lhs) != typeid(rhs))
return typeid(lhs).before(typeid(rhs)); //in worst case, order is guaranteed to be stable only during each program run

return lhs.cmpLessSameType(rhs);
}

class Number
{
virtual bool cmpLessSameType(const Number& rhs) = 0; //precondition: typeid(*this) == typeid(rhs) in derived types
}

class Int : public Number
{
virtual bool cmpLessSameType(const Number& rhs)
{
assert(typeid(*this) == typeid(rhs));
return val_ < static_cast<const int&="">(other.val_);
}

int val_;
}

class Real : public Number
{
virtual bool cmpLessSameType(const Number& rhs)
{
assert(typeid(*this) == typeid(rhs));
return val_ < static_cast<const int&="">(other.val_);
}

float val_;
}


Permalink


Video