Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to check whether type $A$ is a subtype of type $B$ is to traverse the graph of the subtype hierarchy starting at $A$ to see whether type $B$ appears 'above' it. This surely is not the most efficient way to implement subtype tests.

What techniques exist to efficiently implement subtype testing for modern OO languages?

I'm interested in efficiency both in terms of time and memory and any trade-offs between the two.


Yves Caseau gave a method for efficiently encoding type hierarchies as bit vectors. See Efficient handling of multiple inheritance hierarchies.

  • 7
    $\begingroup$ Can you provide some more details, to make your answer more self-contained? $\endgroup$ Jun 2 '12 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.