📝Constant-time “is-a” type check with single inheritance



In the case of single inheritance, there’s a simple implementation technique that will allow you to compute the IS-A predicate in constant time. (I.e. it allows you, in constant time, to check if an object is an instance of a class or one of its subclasses.)

To do this, we associate a unique identifier with every class. Now suppose we have a root class P with subclasses C1 and C2, while C2 itself has a subclass G. In every instance, instead of storing a pointer to a method table, we store a pointer to an array of class identifiers.

For an instance of P, this array has one element:


For an instance of C1, this array has two elements:


For an instance of G, this array has three elements:


Now to check if an object is an instance of, say, C2, do the following:

  • Check if the array has at least 2 elements.

  • Check if the second element is C2.

Obviously, this takes only constant time.