Tutorial :Method resolution order in C++



Question:

Consider the following class hierarchy:

  • base class Object with a virtual method foo()
  • an arbitrary hierarchy with multiple inheritance (virtual and non-virtual); each class is a subtype of Object; some of them override foo(), some don't
  • a class X from this hierarchy, not overriding foo()

How to determine which method will be executed upon a call of foo() on an object of class X in C++?

(I'm looking for the algorithm, not any specific case.)


Solution:1

There is no MRO in C++ like Python. If a method is ambiguous, it is a compile-time error. Whether a method is virtual or not doesn't affect it, but virtual inheritance will.


The algorithm is described in the C++ standard §[class.member.lookup] (10.2). Basically it will find the closest unambiguous implementation in the superclass graph. The algorithm works like this:

  1. Suppose you want to look up a function f in class C.

  2. We define a look-up set S(f, C) being a pair of sets (Î", Σ) representing all possibilities. (§10.2/3)

    • The set Î" is called the declaration set, which is basically all the possible f's.

    • The set Σ is called the subobject set, which contain the classes that these f's are found.

  3. Let S(f, C) include all f directly defined (or using-ed) in C, if any (§10.2/4):

    Î" = {f in C};  if (Î" != empty)    Σ = {C};  else    Σ = empty;  S(f, C) = (Î", Σ);  
  4. If S(f, C) is empty (§10.2/5),

    • Compute S(f, Bi) where Bi is a base class of C, for all i.

    • Merge each S(f, Bi) into S(f, C) one by one.

      if (S(f, C) == (empty, empty)) {    B = base classes of C;    for (Bi in B)      S(f, C) = S(f, C) .Merge. S(f, Bi);  }  
  5. Finally the declaration set is returned as the result of name resolution (§10.2/7).

    return S(f, C).Î";  
  6. The merge between two look-up sets (Î"1, Σ1) and (Î"2, Σ2) is defined as (§10.2/6):

    • If every class in Σ1 is a base class of at least one class in Σ2, return (Î"2, Σ2).
      (Similar for the reverse.)
    • Else if Î"1 ≠ Î"2, return (ambiguous, Σ1 ∪ Σ2).
    • Otherwise, return (Î"1, Σ1 ∪ Σ2)

      function Merge ( (Î"1, Σ1), (Î"2, Σ2) ) {       function IsBaseOf(Σp, Σq) {       for (B1 in Σp) {         if (not any(B1 is base of C for (C in Σq)))           return false;       }       return true;     }       if      (Σ1 .IsBaseOf. Σ2) return (Î"2, Σ2);     else if (Σ2 .IsBaseOf. Σ1) return (Î"1, Σ1);     else {        Σ = Σ1 union Σ2;        if (Î"1 != Î"2)          Î" = ambiguous;         else          Î" = Î"1;        return (Î", Σ);     }  }  

For example (§10.2/10),

struct V { int f(); };  struct W { int g(); };  struct B : W, virtual V { int f(); int g(); };  struct C : W, virtual V { };    struct D : B, C {     void glorp () {       f();       g();     }  };  

We compute that

S(f, D) = S(f, B from D) .Merge. S(f, C from D)          = ({B::f}, {B from D}) .Merge. S(f, W from C from D) .Merge. S(f, V)          = ({B::f}, {B from D}) .Merge. empty .Merge. ({V::f}, {V})          = ({B::f}, {B from D})   // fine, V is a base class of B.  

and

S(g, D) = S(g, B from D) .Merge. S(g, C from D)          = ({B::g}, {B from D}) .Merge. S(g, W from C from D) .Merge. S(g, V)          = ({B::g}, {B from D}) .Merge. ({W::g}, {W from C from D}) .Merge. empty          = (ambiguous, {B from D, W from C from D})  // the W from C is unrelated to B.  


Solution:2

Some detailed description with code.

vtable and vptr

vtable

Virtual Functions


Solution:3

If you are talking about G++ a vtable (Virtual Method Table) is used, you can get more specific details here. Not sure if every C++ compiler uses the same approach but I would say yes


Solution:4

If a method of a base class is virtual, every call to it through base or derived pointer/reference will call the appropriate method (The one furthest down the inheritance tree). If the method was declared virtual, you can't have it any other way later : declaring it virtual (or not) in derived classes won't change anything.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »