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

source
https://wiki.c2.com/?ImplementingMultipleDispatch

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:

PC1

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

PC2G

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.

Backlinks

Want to receive my 🖋 posts as I publish them?