23

因此,vtable是一个由编译器维护的表,其中包含指向该类中的虚函数的函数指针。

将派生类的对象分配给祖先类的对象称为向上转换。

向上转换是使用基类指针或引用处理派生类实例/对象;对象未“分配给”,这意味着覆盖值 ala operator= 调用。
(感谢:托尼 D

现在,如何在运行时知道应该调用“哪个”类的虚函数?

vtable 中的哪个条目是指应该在运行时调用的“特定”派生类的函数?

4

9 回答 9

18

您可以想象(尽管 C++ 规范没有这样说)vtable 是一个标识符(或一些其他可用于“查找有关类本身的更多信息”的元数据)和函数列表。

所以,如果我们有这样的类:

class Base
{
  public:
     virtual void func1();
     virtual void func2(int x);
     virtual std::string func3();
     virtual ~Base();
   ... some other stuff we don't care about ... 
};

然后编译器会生成一个像这样的 VTable:

struct VTable_Base
{
   int identifier;
   void (*func1)(Base* this);
   void (*func2)(Base* this, int x);
   std::string (*func3)(Base* this); 
   ~Base(Base *this);
};

然后编译器将创建一个类似这样的内部结构(这不可能编译为 C++,它只是为了显示编译器实际上做了什么——我称之为Sbase区分实际class Base

struct SBase
{
   VTable_Base* vtable;
   inline void func1(Base* this) { vtable->func1(this); }
   inline void func2(Base* this, int x) { vtable->func2(this, x); }
   inline std::string func3(Base* this) { return vtable->func3(this); }
   inline ~Base(Base* this) { vtable->~Base(this); }
};

它还构建了真正的 vtable:

VTable_Base vtable_base = 
{ 
   1234567, &Base::func1, &Base::func2, &Base::func3, &Base::~Base 
};

而在构造函数中Base,它将设置vtable = vtable_base;.

然后,当我们添加一个派生类时,我们会覆盖一个函数(默认情况下是析构函数,即使我们没有声明一个):

class Derived : public Base
{
    virtual void func2(int x) override; 
};

编译器现在将制作这个结构:

struct VTable_Derived
{
   int identifier;
   void (*func1)(Base* this);
   void (*func2)(Base* this, int x);
   std::string (*func3)(Base* this); 
   ~Base(Derived *this);
};

然后做同样的“结构”建筑:

struct SDerived
{
   VTable_Derived* vtable;
   inline void func1(Base* this) { vtable->func1(this); }
   inline void func2(Base* this, int x) { vtable->func2(this, x); }
   inline std::string func3(Base* this) { return vtable->func3(this); }
   inline ~Derived(Derived* this) { vtable->~Derived(this); }
};

当我们Derived直接使用而不是通过Base类使用时,我们需要这种结构。

(我们也依赖于~Derived调用的编译器链~Base,就像继承的普通析构函数一样)

最后,我们构建一个实际的 vtable:

VTable_Derived vtable_derived = 
{ 
   7654339, &Base::func1, &Derived::func2, &Base::func3, &Derived::~Derived 
};

同样,Derived构造函数将为Dervied::vtable = vtable_derived所有实例设置。

编辑以回答评论中的问题:编译器必须小心地将各种组件放在两者中VTable_DerivedSDerived使其与VTable_Baseand匹配SBase,以便当我们有指向 的指针时BaseBase::vtableandBase::funcN()匹配Derived::vtableand Derived::FuncN。如果这不匹配,那么继承将不起作用。

如果添加了新的虚函数Derived,它们必须放在继承自的虚函数之后Base

结束编辑。

所以,当我们这样做时:

Base* p = new Derived;

p->func2(); 

代码将查找SBase::Func2,这将使用正确的Derived::func2(因为实际的vtable内部p->vtableVTable_Derived(由与Derived结合调用的构造函数设置new Derived)。

于 2014-11-05T08:58:03.257 回答
8

我将采取与其他答案不同的路线,并尝试仅填补您知识中的特定空白,而无需过多介绍细节。我将介绍足以帮助您理解的机制。

因此,vtable 是由编译器维护的表,其中包含指向该类中的虚函数的函数指针。

更准确的说法如下:

每个具有虚方法的类,包括从具有虚方法的类继承的每个类,都有自己的虚表。类的虚拟表指向特定于该类的虚拟方法,即继承方法、覆盖方法或新添加的方法。这种类的每个实例都包含一个指向与该类匹配的虚拟表的指针。

向上转换是使用基类指针或引用处理派生类实例/对象;(...)

也许更有启发性:

向上转换意味着对 class 实例的指针或引用Derived被视为是对 class 实例的指针或引用Base。然而,实例本身仍然是纯粹的Derived.

(当指针被“视为指向的指针Base”时,这意味着编译器生成代码来处理指向 的指针Base。换句话说,编译器和生成的代码并不比他们正在处理指向Base.因此,被“视为”的指针必须指向一个对象,该对象至少提供与Base.Derived

至此,我们可以回答您问题的第一个版本。

现在,如何在运行时知道应该调用“哪个”类的虚函数?

假设我们有一个指向Derived. 首先我们向上转换它,因此它被视为指向Base. 然后我们在向上转换的指针上调用一个虚方法。由于编译器知道该方法是虚拟的,因此它知道在实例中查找虚拟表指针。虽然我们将指针视为指向 的实例Base,但实际对象的值并未改变,其中的虚拟表指针仍指向 的虚拟表Derived。所以在运行时,方法的地址是从Derived.

现在,特定方法可能继承自Base或被覆盖在Derived. 不要紧; 如果继承,则虚表中的方法指针Derived只包含与虚表中对应方法指针相同的地址Base。换句话说,两个表都指向该特定方法的相同方法实现。如果被覆盖,则 的虚拟表中的方法指针与 的虚拟表中Derived的相应方法指针不同Base,因此对 的实例的方法查找Derived将找到被覆盖的方法,而对 的实例的查找将找到该方法的Base原始版本——不管指向实例的指针是否被视为指向Base或指向Derived.

最后,现在应该可以直接解释为什么您的问题的第二个版本有点误导:

vtable 中的哪个条目是指应该在运行时调用的“特定”派生类的函数?

这个问题假定 vtable 查找首先是按方法,然后是按类。反之亦然:首先,实例中的 vtable 指针用于查找正确类的 vtable。然后,该类的 vtable 用于查找正确的方法。

于 2014-11-08T10:44:13.423 回答
5

vtable 中的哪个条目是指应该在运行时调用的“特定”派生类的函数?

无,它不是 vtable 中的条目,而是 vtable 指针,它是每个对象实例的一部分,它确定哪些是该特定对象的正确虚函数集。这样,根据所指向的实际 vtable,从 vtable 调用“第一个虚拟方法”可能会导致为同一多态层次结构中的不同类型的对象调用不同的函数。

实现可能会有所不同,但我个人认为最合乎逻辑和执行力的事情是让 vtable 指针成为类布局中的第一个元素。这样,您可以取消引用对象的地址,以根据位于该地址中的指针的值来确定其类型,因为给定类型的所有对象都将具有指向相同 vtable 的指针,该 vtable 是为每个唯一创建的具有虚拟方法的对象,这是启用覆盖某些虚拟方法的功能所必需的。

upcasting 和 vtables 如何协同工作以确保正确的动态绑定?

向上转型本身并不是严格需要的,向下转型也不是。请记住,您已经在内存中分配了对象,并且它已经将其 vtable 指针设置为该类型的正确 vtable,这是确保它的原因,向下转换不会更改该对象的 vtable,它只会更改您操作的指针。

当您想要访问在基类中不可用且在派生类中声明的功能时,需要向下转换。但在你尝试这样做之前,你必须确保特定对象属于或继承声明该​​功能的类型,这是dynamic_cast进来的地方,当你动态转换时,编译器会生成对该 vtable 条目的检查,以及它是否继承从另一个表请求的类型,在编译时生成,如果是,则动态转换成功,否则失败。

访问对象的指针并不指向要调用的正确的虚函数集,它只是作为开发人员可以参考 vtable 中哪些函数的标准。这就是为什么使用不执行运行时检查的 C 风格或静态转换是安全的,因为这样您就只能将量规限制为基类中可用的函数,而这些函数在派生类中已经可用,所以有没有错误和伤害的余地。这就是为什么在向下转换时必须始终使用动态转换或其他仍然基于虚拟调度的自定义技术,因为您必须确保对象的关联 vtable 确实包含您可能调用的额外功能。

否则,您将获得未定义的行为,并且是“不良行为”,这意味着很可能会发生致命的事情,因为将任意数据解释为要调用的特定签名函数的地址是一个非常大的禁忌。

另请注意,在静态上下文中,即在编译时知道类型是什么时,编译器很可能不会使用 vtable 来调用虚函数,而是使用直接静态调用甚至内联某些函数,这将使它们快多了。在这种情况下,向上转换和使用基类指针而不是实际对象只会削弱这种优化。

于 2014-11-08T12:03:10.497 回答
4

铸造 铸造是一个与变量相关的概念。所以可以转换任何变量。它可以向上或向下铸造。

char charVariable = 'A';
int intVariable = charVariable; // upcasting

int intVariable = 20;
char charVariale = intVariable; // downcasting 

对于系统定义的数据类型向上转换或向下转换基于您当前的变量,它主要与编译器分配给两个比较变量的内存量有关。

如果您分配的变量分配的内存少于要转换的类型,则称为强制转换。

如果您分配的变量分配的内存比要转换的类型多,则称为向下转换。 当试图转换的值不适合分配的内存区域时,向下转换会产生一些问题。

类级别的向上转换 就像系统定义的数据类型一样,我们可以有基类和派生类的对象。因此,如果我们要将派生类型转换为基类型,则称为向下转换。这可以通过指向派生类类型的基类指针来实现。

class Base{
    public:
        void display(){
          cout<<"Inside Base::display()"<<endl;
    }
};
class Derived:public Base{
    public:
      void display(){
           cout<<"Inside Derived::display()"<<endl;
    }
};

int main(){
   Base *baseTypePointer = new Derived(); // Upcasting
   baseTypePointer.display();  // because we have upcasted we want the out put as Derived::display() as output

}

输出

Base::display() 内部

例外

内部派生::display()

在上述情况下,输出并不例外。这是因为我们在对象中没有 v-table 和 vptr(虚拟指针),尽管我们已将派生类型分配给基指针,但基指针将调用 Base::display()。

为了避免这个问题,c++ 给了我们虚拟的概念。现在需要将基类显示功能更改为虚拟类型。

virtual void display()

完整代码是:

class Base{
    public:
        virtual void display(){
          cout<<"Inside Base::display()"<<endl;
    }
};
class Derived:public Base{
    public:
      void display(){
           cout<<"Inside Derived::display()"<<endl;
    }
};

int main(){
   Base *baseTypePointer = new Derived(); // Upcasting
   baseTypePointer.display();  // because we have upcasted we want the out put as Derived::display() as output

}

输出

内部派生::display()

例外

内部派生::display()

要理解这一点,我们需要了解 v-table 和 vptr;当编译器找到一个虚函数和一个函数时,它将为每个类(基础类和所有派生类)生成一个虚表。

如果存在虚函数,则每个对象都将包含指向相应类 vtable 的 vptr(虚拟指针),而 vtable 将包含指向相应类虚函数的指针。当您通过 vptr 调用该函数时,将调用虚拟函数,它将调用相应的类函数,我们将获得所需的输出。

在此处输入图像描述

于 2014-11-12T13:41:47.110 回答
4

多态性和动态调度(超删节版)

注意:我无法为虚拟基的多重继承提供足够的信息,因为它没有太多简单的东西,而且细节会使说明变得混乱(进一步)。这个答案演示了用于实现动态分派的机制,假设只有单一继承。

解释跨模块边界可见的抽象类型及其行为需要一个通用的应用程序二进制接口 (ABI)。当然,C++ 标准不需要实现任何特定的 ABI。

ABI 将描述:

  • 虚拟方法调度表(vtables)的布局
  • 运行时类型检查和强制转换操作所需的元数据
  • 名称装饰(又名修饰)、调用约定和许多其他内容。

以下示例中的两个模块external.somain.o都假定已链接到同一运行时。静态和动态绑定优先考虑位于调用模块中的符号。


外部库

external.h(分发给用户):

class Base
{
    __vfptr_t __vfptr; // For exposition

public:

    __attribute__((dllimport)) virtual int Helpful();
    __attribute__((dllimport)) virtual ~Base();
};

class Derived : public Base
{
public:

    __attribute__((dllimport)) virtual int Helpful() override;

    ~Derived()
    {
        // Visible destructor logic here.


        // Note: This is in the header!


        // __vft@Base gets treated like any other imported symbol:
        // The address is resolved at load time.
        //
        this->__vfptr = &__vft@Base;
        static_cast<Base *>(this)->~Base();
    }
};

__attribute__((dllimport)) Derived *ReticulateSplines();

外部.cpp:

#include "external.h" // the version in which the attributes are dllexport

__attribute__((dllexport)) int Base::Helpful()
{
    return 47;
}
__attribute__((dllexport)) Base::~Base()
{
}

__attribute__((dllexport)) int Derived::Helpful()
{
    return 4449;
}

__attribute__((dllexport)) Derived *ReticulateSplines()
{
    return new Derived(); // __vfptr = &__vft@Derived in external.so
}

external.so(不是真正的二进制布局):

__vft@Base:
[offset to __type_info@Base] <-- in external.so
[offset to Base::~Base] <------- in external.so
[offset to Base::Helpful] <----- in external.so

__vft@Derived:
[offset to __type_info@Derived] <-- in external.so
[offset to Derived::~Derived] <---- in external.so
[offset to Derived::Helpful] <----- in external.so

Etc...

__type_info@Base:
[null base offset field]
[offset to mangled name]

__type_info@Derived:
[offset to __type_info@Base]
[offset to mangled name]

Etc...

使用外部库的应用程序

特殊.hpp:

#include <iostream>
#include "external.h"

class Special : public Base
{
public:

    int Helpful() override
    {
        return 55;
    }

    virtual void NotHelpful()
    {
        throw std::exception{"derp"};
    }
};

class MoreDerived : public Derived
{
public:

    int Helpful() override
    {
        return 21;
    }

    ~MoreDerived()
    {
        // Visible destructor logic here

        this->__vfptr = &__vft@Derived; // <- the version in main.o
        static_cast<Derived *>(this)->~Derived();
    }
};

class Related : public Base
{
public:

    virtual void AlsoHelpful() = 0;
};

class RelatedImpl : public Related
{
public:

    void AlsoHelpful() override
    {
        using namespace std;

        cout << "The time for action... Is now!" << endl;
    }
};

主.cpp:

#include "special.hpp"

int main(int argc, char **argv)
{
    Base *ptr = new Base(); // ptr->__vfptr = &__vft@Base (in external.so)

    auto r = ptr->Helpful(); // calls "Base::Helpful" in external.so
    // r = 47

    delete ptr; // calls "Base::~Base" in external.so



    ptr = new Derived(); // ptr->__vfptr = &__vft@Derived (in main.o)

    r = ptr->Helpful(); // calls "Derived::Helpful" in external.so
    // r = 4449

    delete ptr; // calls "Derived::~Derived" in main.o



    ptr = ReticulateSplines(); // ptr->__vfptr = &__vft@Derived (in external.so)

    r = ptr->Helpful(); // calls "Derived::Helpful" in external.so
    // r = 4449

    delete ptr; // calls "Derived::~Derived" in external.so



    ptr = new Special(); // ptr->__vfptr = &__vft@Special (in main.o)

    r = ptr->Helpful(); // calls "Special::Helpful" in main.o
    // r = 55

    delete ptr; // calls "Base::~Base" in external.so



    ptr = new MoreDerived(); // ptr->__vfptr = & __vft@MoreDerived (in main.o)

    r = ptr->Helpful(); // calls "MoreDerived::Helpful" in main.o
    // r = 21

    delete ptr; // calls "MoreDerived::~MoreDerived" in main.o


    return 0;
}

主.o:

__vft@Derived:
[offset to __type_info@Derivd] <-- in main.o
[offset to Derived::~Derived] <--- in main.o
[offset to Derived::Helpful] <---- stub that jumps to import table

__vft@Special:
[offset to __type_info@Special] <-- in main.o
[offset to Base::~Base] <---------- stub that jumps to import table
[offset to Special::Helpful] <----- in main.o
[offset to Special::NotHelpful] <-- in main.o

__vft@MoreDerived:
[offset to __type_info@MoreDerived] <---- in main.o
[offset to MoreDerived::~MoreDerived] <-- in main.o
[offset to MoreDerived::Helpful] <------- in main.o

__vft@Related:
[offset to __type_info@Related] <------ in main.o
[offset to Base::~Base] <-------------- stub that jumps to import table
[offset to Base::Helpful] <------------ stub that jumps to import table
[offset to Related::AlsoHelpful] <----- stub that throws PV exception

__vft@RelatedImpl:
[offset to __type_info@RelatedImpl] <--- in main.o
[offset to Base::~Base] <--------------- stub that jumps to import table
[offset to Base::Helpful] <------------- stub that jumps to import table
[offset to RelatedImpl::AlsoHelpful] <-- in main.o

Etc...

__type_info@Base:
[null base offset field]
[offset to mangled name]

__type_info@Derived:
[offset to __type_info@Base]
[offset to mangled name]

__type_info@Special:
[offset to __type_info@Base]
[offset to mangled name]

__type_info@MoreDerived:
[offset to __type_info@Derived]
[offset to mangled name]

__type_info@Related:
[offset to __type_info@Base]
[offset to mangled name]

__type_info@RelatedImpl:
[offset to __type_info@Related]
[offset to mangled name]

Etc...

召唤是(或可能不是)魔法!

根据方法和可以在绑定端证明的内容,可以静态或动态绑定虚拟方法调用。

动态虚方法调用将从成员指向的虚表中读取目标函数的地址__vfptr

ABI 描述了函数在 vtable 中的排序方式。例如:它们可能按类排序,然后按字典顺序按损坏的名称(包括有关 const-ness、参数等的信息)。对于单继承,这种方法保证一个函数的虚拟调度索引总是相同的,不管有多少不同的实现。

在此处给出的示例中,析构函数放置在每个 vtable 的开头(如果适用)。如果析构函数是微不足道的和非虚拟的(未定义或什么都不做),编译器可能会完全忽略它,并且不为其分配 vtable 条目。

Base *ptr = new Special{};
MoreDerived *md_ptr = new MoreDerived{};

// The cast below is checked statically, which would
// be a problem if "ptr" weren't pointing to a Special.
//
Special *sptr = static_cast<Special *>(ptr);

// In this case, it is possible to
// prove that "ptr" could point only to
// a Special, binding statically.
//
ptr->Helpful();

// Due to the cast above, a compiler might not
// care to prove that the pointed-to type
// cannot be anything but a Special.
//
// The call below might proceed as follows:
//
// reg = sptr->__vptr[__index_of@Base::Helpful] = &Special::Helpful in main.o
//
// push sptr
// call reg
// pop
//
// This will indirectly call Special::Helpful.
//
sptr->Helpful();

// No cast required: LSP is satisfied.
ptr = md_ptr;

// Once again:
//
// reg = ptr->__vfptr[__index_of@Base::Helpful] = &MoreDerived::Helpful in main.o
//
// push ptr
// call reg
// pop
//
// This will indirectly call MoreDerived::Helpful
//
ptr->Helpful();

上面的逻辑对于任何需要动态绑定的调用站点都是一样的。ptr在上面的示例中,确切的类型或sptr指向并不重要;代码只会加载一个已知偏移量的指针,然后盲目地调用它。


类型铸造:起起落落

在翻译转换或函数调用表达式时,编译器必须可以使用有关类型层次结构的所有信息。象征性地,铸造只是遍历有向图的问题。

这个简单的 ABI 中的向上转换可以完全在编译时执行。编译器只需检查类型层次结构以确定源类型和目标类型是否相关(类型图中存在从源到目标的路径)。根据替换原则,指向 a 的指针MoreDerived也指向 aBase并且可以这样解释。对于此层次结构中的所有类型,该__vfptr成员的偏移量相同,因此 RTTI 逻辑不需要处理任何特殊情况(在 VMI 的某些实现中,它需要从类型 thunk 中获取另一个偏移量来获取另一个 vptr 等等上...)。

然而,向下铸造是不同的。由于从基类型转换为派生类型涉及确定指向的对象是否具有兼容的二进制布局,因此有必要执行显式类型检查(从概念上讲,这是“证明”额外信息存在于编译时假定的结构)。

请注意,该类型有多个 vtable 实例Derived:一个 inexternal.so和一个 in main.o。这是因为为Derived(其析构函数)定义的虚拟方法出现在每个包含external.h.

尽管这两种情况的逻辑相同,但此示例中的两个图像都需要有自己的副本。这就是为什么不能单独使用地址来执行类型检查的原因。

然后通过从运行时解码的源类型开始遍历类型图(在两个图像中复制)来执行向下转换,比较重整的名称,直到匹配编译时目标。

例如:

Base *ptr = new MoreDerived();

// ptr->__vfptr = &__vft::MoreDerived in main.o
//
// This provides the code below with a starting point
// for dynamic cast graph traversals.

// All searches start with the type graph in the current image,
// then all other linked images, and so on...

// This example is not exhaustive!

// Starts by grabbing &__type_info@MoreDerived
// using the offset within __vft@MoreDerived resolved
// at load time.
//
// This is similar to a virtual method call: Just grab
// a pointer from a known offset within the table.
//
// Search path:
// __type_info@MoreDerived (match!)
//
auto *md_ptr = dynamic_cast<MoreDerived *>(ptr);

// Search path:
// __type_info@MoreDerived ->
// __type_info@Derived (match!)
//
auto *d_ptr = dynamic_cast<Derived *>(ptr);

// Search path:
// __type_info@MoreDerived ->
// __type_info@Derived ->
// __type_info@Base (no match)
//
// Did not find a path connecting RelatedImpl to MoreDerived.
//
// rptr will be nullptr
//
auto *rptr = dynamic_cast<RelatedImpl *>(ptr);

上面代码中的任何一点都不ptr->__vfptr需要更改。C++ 中类型推导的静态性质要求实现在编译时满足替换原则,这意味着对象的实际类型在运行时不能改变。


概括

我已经将这个问题理解为关于动态调度背后的机制的问题。

对我来说,“vtable 中的哪个条目是指应该在运行时调用的“特定”派生类的函数?,正在询问 vtable 是如何工作的。

这个答案旨在证明类型转换仅影响对象数据的视图,并且这些示例中的动态调度的实现独立于它运行。然而,在多重继承的情况下,类型转换确实会影响动态调度,其中确定要使用哪个vtable 可能需要多个步骤(具有多个基的类型的实例可能有多个 vptr)。

于 2014-11-13T08:42:32.233 回答
2

让我试着用一些例子来解释它:-

class Base  
 {  
 public:  
    virtual void function1() {cout<<"Base :: function1()\n";};  
    virtual void function2() {cout<<"Base :: function2()\n";};  
    virtual ~Base(){};
};  

class D1: public Base  
{  
public:  
   ~D1(){};
   virtual void function1() { cout<<"D1 :: function1()\n";};
};  

class D2: public Base  
{  
public:  
   ~D2(){};
   virtual void function2() { cout<< "D2 :: function2\n";};  
}; 

因此,编译器将为每个类生成三个 vtable,因为这些类具有虚函数。(尽管它依赖于编译器)。

注意:- vtables 只包含指向虚函数的指针。非虚拟函数仍将在编译时解析...

你说得对,vtables 不仅仅是指向函数的指针。这些类的 vtables 就像这样:-

用于基础的 vtable:-

&Base::function1 ();
&Base::function2 ();
&Base::~Base ();

D1 的虚表:-

&D1::function1 ();
&Base::function2 ();
&D1::~D1();

D2 的虚表:-

&Base::function1 ();
&D2::function2 ();
&D2::~D2 ();

vptr 是一个指针,用于在该表上进行查找。多态类的每个对象都在其中为 vptr 分配了额外的空间(尽管 vptr 在对象中的位置完全取决于实现)。通常 vptr 位于对象的开头。

考虑到所有因素,如果我调用 func,编译器会在运行时检查 b 实际指向的内容:-

void func ( Base* b )
{
  b->function1 ();
  b->function2 ();
}

假设我们将 D1 的对象传递给 func。编译器将以下列方式解析调用:-

首先它将从对象中获取 vptr,然后它将使用它来获取要调用的函数的正确地址。所以,在这种情况下,vptr 将允许访问 D1 的 vtable。当它查找 function1 时,它将获得在基类中定义的 function1 的地址。在调用function2的情况下,它将获得base的function2的地址。

希望我已经澄清了您的疑虑,使您满意...

于 2014-11-08T06:15:46.347 回答
2

我相信,最好通过在 C 中实现多态来解释这一点。鉴于这两个 C++ 类:

class Foo {
    virtual void foo(int);
};

class Bar : public Foo {
    virtual void foo(int);
    virtual void bar(double);
};

C 结构定义(即头文件)如下所示:

//For class Foo
typedef struct Foo_vtable {
    void (*foo)(int);
} Foo_vtable;

typedef struct Foo {
    Foo_vtable* vtable;
} Foo;

//For class Bar
typedef struct Bar_vtable {
    Foo_vtable super;
    void (*bar)(double);
}

typedef struct Bar {
    Foo super;
} Bar;

如您所见,每个类有两个结构定义,一个用于 vtable,一个用于类本身。另请注意,这两个结构都class Bar包含一个基类对象作为它们的第一个成员,这允许我们向上转换:两者(Foo*)myBarPointer(Foo_vtable*)myBar_vtablePointer都是有效的。因此,给定 a ,通过以下方式找到成员Foo*的位置是安全的foo()

Foo* basePointer = ...;
(basePointer->vtable->foo)(7);

现在,让我们看看我们如何实际填充 vtables。为此,我们编写了一些使用一些静态定义的 vtable 实例的构造函数,这就是 foo.c 文件的样子

#include "..."

static void foo(int) {
    printf("Foo::foo() called\n");
}

Foo_vtable vtable = {
    .foo = &foo,
};

void Foo_construct(Foo* me) {
    me->vtable = vtable;
}

这确保可以(basePointer->vtable->foo)(7)在已传递给的每个对象上执行Foo_construct(). 现在,代码Bar非常相似:

#include "..."

static void foo(int) {
    printf("Bar::foo() called\n");
}

static void bar(double) {
    printf("Bar::bar() called\n");
}

Bar_vtable vtable = {
    .super = {
        .foo = &foo
    },
    .bar = &bar
};

void Bar_construct(Bar* me) {
    Foo_construct(&me->super);    //construct the base class.
    (me->vtable->foo)(7);    //This will print Foo::foo()
    me->vtable = vtable;
    (me->vtable->foo)(7);    //This will print Bar::foo()
}

我为成员函数使用了静态声明以避免必须为每个实现发明一个新名称,从而static void foo(int)限制了函数对源文件的可见性。但是,它仍然可以通过使用函数指针从其他文件中调用。

这些类的用法可能如下所示:

#include "..."

int main() {
    //First construct two objects.
    Foo myFoo;
    Foo_construct(&myFoo);

    Bar myBar;
    Bar_construct(&myBar);

    //Now make some pointers.
    Foo* pointer1 = &myFoo, pointer2 = (Foo*)&myBar;
    Bar* pointer3 = &myBar;

    //And the calls:
    (pointer1->vtable->foo)(7);    //prints Foo::foo()
    (pointer2->vtable->foo)(7);    //prints Bar::foo()
    (pointer3->vtable->foo)(7);    //prints Bar::foo()
    (pointer3->vtable->bar)(7.0);  //prints Bar::bar()
}

一旦你知道它是如何工作的,你就会知道 C++ vtables 是如何工作的。唯一的区别是,在 C++ 中,编译器完成了我自己在上面的代码中所做的工作。

于 2014-11-08T11:26:35.593 回答
2

该实现是特定于编译器的。在这里,我将做一些与编译器如何完成的实际知识无关的想法,而只是为了按要求工作所需的一些最低要求。请记住,具有虚拟方法的类的每个实例在运行时也知道它属于哪个类。

假设我们有一个长度为 10 的基类和派生类链(因此派生类有一个 gran gran ... gran Father )。我们可以将这些类称为 base0 base1 ... base9 其中 base9 派生自 base8 等。

这些类中的每一个都将方法定义为: virtual void doit(){ ... }

假设在基类中,我们在一个名为“dowith_doit”的方法中使用该方法,该方法在任何派生类中都未被覆盖。c++ 的语义意味着根据我们手头实例的基类,我们必须将手头实例的基类中定义的“doit”应用于该实例。

本质上,我们有两种可能的方法: a) 为任何这样的虚拟方法分配一个数字,对于派生类链中定义的每个方法,该数字必须不同。在这种情况下,数字也可以是方法名称的哈希值。每个类都定义了一个包含 2 列的表,第一列保存方法的编号,第二列保存函数的地址。在这种情况下,每个类都会有一个 vtable,其中的行数与类内定义的虚拟方法的数量一样多。该方法的执行是通过在类中搜索所考虑的方法来实现的。该搜索可以通过二等分线性(慢)完成(当存在基于方法数量的顺序时)。

b) 为任何此类方法分配一个逐渐增加的整数(对于类链中的每个不同方法),并为每个类定义一个只有一列的表。对于在类中定义的虚方法,函数地址将是由方法编号定义的原始地址。会有很多行带有空指针,因为每个类并不总是覆盖以前类的方法。为了提高效率,实现可以选择用所考虑的类的祖先类中的地址来填充空行。

为了有效地使用虚拟方法,基本上不存在其他简单的方法。

我想在实际实现中只使用第二种解决方案(b),因为与案例(b)的执行效率相比,用于非现有方法的空间开销之间的权衡有利于案例 b(也考虑到方法是数量有限 - 可能是 10 20 50 但不是 5000 )。

于 2014-11-09T09:16:19.333 回答
2

在实例化每个具有至少一个虚函数的类时,都会获得一个隐藏成员,通常称为 vTable(或虚拟调度表,VDT)。

class Base {
hidden: // not part of the language, just to illustrate.
  static VDT baseVDT; // per class VDT for base
  VDT *vTable; // per object instance
private:
  ...
public:
  virtual int base1();
  virtual int base2();
  ...
};

vTable 包含指向 Base 中所有函数的指针。

作为 Base 构造函数的隐藏部分,vTable 被分配给 baseVDT。

VDT Base::baseVDT[] = { 
  Base::base1, 
  Base::base2 
};

class Derived : public Base {
hidden:
  static VDT derivedVDT; // per class VDT for derived
private:
  ...
public:
  virtual int base2();
  ...
};

Derived 的 vTable 包含指向 Base 中定义的所有函数的指针,后跟 Derived 中定义的函数。当 Derived 类型的对象被构​​造时,vTable 被设置为 derivedVDT。

VDT derived::derivedVDT[] = { 
  // functions first defined in Base
  Base::base1, 
  Derived::base2, // override
  // functions first defined in Derived are appended
  Derived::derived3 
}; // function 2 has an override in derived.

现在如果我们有

Base *bd    = new Derived;
Derived *dd = new Derived;
Base *bb    = new Base;

bd指向一个派生类型的对象,他的 vTable 指向派生

所以函数调用

x = bd->base2();
y = bb->base2();

实际上是

// "base2" here is the index into vTable for base2.
x = bd->vTable["base2"]();  // vTable points to derivedVDT
y = bb->vTable["base2"]();  // vTable points to baseVDT

由于 VDT 的构造,两者的指数相同。这也意味着编译器在编译时就知道索引。

这也可以实现为

// call absolute address to virtual dispatch function which calls the right base2.
x = Base::base2Dispatch(bd->vTable["base2"]); 

inline Base::base2Dispatch(void *call) {
  return call(); // call through function pointer.
}

这与 O2 或 O3 将是相同的。


有一些特殊情况:

dd 指向派生或更多派生对象,final然后声明 base2

z = dd->base2();

实际上是

z = Derived::base2();  // absolute call to final method.

如果 dd 指向 Base 对象或其他任何未定义行为的对象,编译器仍然可以执行此操作。

另一种情况是,如果编译器看到只有少数来自 Base 的派生类,它可以为 base2 生成 Oracle 接口。[在 2012 年或 2013 年的某个 C++ 会议上获得 MS 或 Intel 编译器专家后免费?显示(~500%?)更多代码平均提供(2+倍?)加速]

inline Base::base2Dispatch(void *call) {
  if (call == Derived::base2)  // most likely from compilers static analysis or profiling.
    return Derived::base2(); // call absolute address
  if (call == Base::base2)
    return Base::base2(); // call absolute address

  //  Backup catch all solution in case of more derived classes
  return call(); // call through function pointer.
}

你到底为什么要作为编译器这样做???更多代码不好,不需要的分支会降低性能!

因为在许多架构上调用函数指针非常慢,乐观的例子

从内存中获取地址,3+ 个周期。等待 ip 值时的延迟管道,10 个周期,在某些处理器上 19+ 个周期。

如果最复杂的现代 cpu 可以预测实际跳转地址 [BTB] 以及它可以进行分支预测,那么这可能是一种损失。否则,~8 条额外指令将轻松保存由于流水线停顿而丢失的 4*(3+10) 条指令(如果预测失败率低于 10-20%)。

如果两个 if 中的分支都预测(即评估为假),则丢失的约 2 个周期很好地被内存延迟覆盖以获取调用地址,我们的情况也不会更糟。
如果其中一个 if 是错误预测的,那么 BTB 很可能也是错误的。然后错误预测的成本大约是 8 个周期,其中 3 个由内存延迟支付,正确的不采取或第二个如果可以节省一天,或者我们支付全部 10+ 管道停顿。
如果仅存在 2 种可能性,其中一种被采用,我们从函数指针调用中保存管道停顿,我们将最大。得到一个错误预测导致没有(显着)比直接调用更差的性能。如果记忆延迟更长并且结果被正确预测,则效果会大得多。

于 2014-11-10T16:29:13.713 回答