📝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:
P For an instance of C1, this array has two elements:
P C1 For an instance of G, this array has three elements:
P C2 G 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.