c++中hashmap的实现原理
2014-04-29 12:17:52 body7 阅读数 2570

今天开始刷CC150,最前面的概念hashmap迷惑了

查了一下,在java中所有类型都有一个内建函数hashcode(), 这个函数能获取任何类型的hash值,帮助简历hash索引,所以任何类型都可以用java中的hashmap实现。 ps:equal函数


在C++中,找了半天貌似没有一个标准的回答,以下来自stackflow:

The STL has hash_map, but the C++ Standard Library does not.

Due to a common misconception, you may think of the C++ Standard Library as "the STL", or of parts of your toolchains implementation of the C++ Standard Library as "an STL implementation". It is not.

It is also a great shame that both MSVC++ and GCC (which implement hash_map as a compiler-specific extension), place it in the std namespace, which is highly misleading. *sigh*

C++11 has introduced std::unordered_map, which is not dissimilar.


意思是hashmap在C++中有,是STL但不是C++ 标准库,俩概念不一样,囧。

C++11推出unordered_map,用途比原来的hashmap要广,因为不单只支持一些简单的类型了。

但是貌似compare函数还得自己写。

实现方法伪代码:

//define a hash_map in cpp
//hash_map<int,string> hmap;//定义一个实例
//hmap.insert(pair<int,string>(10,"sfsfd"));//插入一个pair对象,
//hmap.insert(hash_map<int,string>::value_type(34,"sddsf"));//value_type就是pair类型的

hash_map<int, student> buildmap(student [])
{
	hash_map<int,student> map = new hash_map<int, student>;
	for(element in student)
	{
		map.insert(selement.getID(),element);   //so there should be a inner method to get the ID which is the key you want to use
	}
	return(map);

}

//unordered_map  similar to hash map, but is the new standard in C++11

总而言之,hashmap查找速度很快,一般是定值,map是logn


2017-07-24 13:58:09 LarsellBidder 阅读数 183

先来看一段代码

#include <stdio.h>


int Add(int a,int b)
{
return a+b;
}
double Add(double a,double b)
{
return a+b;
}
int main()
{
return 0;
}

在c语言编译器下是错误的,根本编译不过去,编译器会报出Add重定义的错误。

函数重载:为方便使用,c++中对函数可以进行重载。也就是说,在同一作用域类,一组函数的函数名可以相同,参数列表可不同(参数个数不同,参数类型不同),返回类型可同可不同。

不如下面的代码:

#include <iostream>
using namespace std;


int Add(int a,int b,int c)
{
return a+b+c;
}
int Add(int a,int b)
{
return a+b;
}
double Add(double a,double b)
{
return a+b;
}
double Add(int a,double b)
{
return a+b;
}
int main()
{
cout<<Add(1,2)<<endl;
cout<<Add(2,2,3)<<endl;
cout<<Add(3.14,2.25)<<endl;
cout<<Add(1,2.23)<<endl;
return 0;
}

在c++编译器中是可以编译过的,而且不会报出错误。

因为在c++的编译过程中对函数名的解析不同。


c++程序中调用c编译器编译后的函数为什么要加extern "C"?

C++语言支持函数重载,C语言不支持函数重载。函数被C++编译后在库中的名字与C语言不同,例如 int Add(int x,int y); 在被C编译器编译后为_Add,而C++则会产生像?Add@@YAHHH@Z之类的名字,所以C++提供了C连接交换指定符号extern “C”来解决名字匹配问题。



2015-09-15 13:04:44 xuchenhuics 阅读数 314

文章转自:http://www.blogbus.com/wanderer-zjhit-logs/161830653.html

虚函数的定义要遵循以下重要规则: 

1.如果虚函数在基类与派生类中出现,仅仅是名字相同,而形式参数不同,或者是返回类型不同,那么即使加上了virtual关键字,也是不会进行滞后联编的。 

2.只有类的成员函数才能说明为虚函数,因为虚函数仅适合用与有继承关系的类对象,所以普通函数不能说明为虚函数。 

3.静态成员函数不能是虚函数,因为静态成员函数的特点是不受限制于某个对象。 

4.内联(inline)函数不能是虚函数,因为内联函数不能在运行中动态确定位置。即使虚函数在类的内部定义定义,但是在编译的时候系统仍然将它看做是非内联的。 

5.构造函数不能是虚函数,因为构造的时候,对象还是一片未定型的空间,只有构造完成后,对象才是具体类的实例。 

6.析构函数可以是虚函数,而且通常声名为虚函数。

 

C++中的虚函数的作用主要是实现了多态的机制。关于多态,简而言之就是用父类型别的指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”,这是一种泛型技术。所谓泛型技术,说白了就是试图使用不变的代码来实现可变的算法。比如:模板技术,RTTI技术,虚函数技术,要么是试图做到在编译时决议,要么试图做到运行时决议。

关于虚函数的使用方法,我在这里不做过多的阐述。大家可以看看相关的C++的书籍。在这篇文章中,我只想从虚函数的实现机制上面为大家 一个清晰的剖析。

当然,相同的文章在网上也出现过一些了,但我总感觉这些文章不是很容易阅读,大段大段的代码,没有图片,没有详细的说明,没有比较,没有举一反三。不利于学习和阅读,所以这是我想写下这篇文章的原因。也希望大家多给我提意见。

言归正传,让我们一起进入虚函数的世界。

虚函数表

对C++ 了解的人都应该知道虚函数(Virtual Function)是通过一张虚函数表(Virtual Table)来实现的。简称为V-Table。 在这个表中,主是要一个类的虚函数的地址表,这张表解决了继承、覆盖的问题,保证其容真实反应实际的函数。这样,在有虚函数的类的实例中这个表被分配在了 这个实例的内存中,所以,当我们用父类的指针来操作一个子类的时候,这张虚函数表就显得由为重要了,它就像一个地图一样,指明了实际所应该调用的函数。

这里我们着重看一下这张虚函数表。在C++的标准规格说明书中说到,编译器必需要保证虚函数表的指针存在于对象实例中最前面的位置(这是为了保证正确取到虚函数的偏移量)。 这意味着我们通过对象实例的地址得到这张虚函数表,然后就可以遍历其中函数指针,并调用相应的函数。

听我扯了那么多,我可以感觉出来你现在可能比以前更加晕头转向了。 没关系,下面就是实际的例子,相信聪明的你一看就明白了。

假设我们有这样的一个类:

class Base {

public:

virtual void f() { cout << "Base::f" << endl; }

virtual void g() { cout << "Base::g" << endl; }

virtual void h() { cout << "Base::h" << endl; }

};

按照上面的说法,我们可以通过Base的实例来得到虚函数表。 下面是实际例程:

typedef void(*Fun)(void);

Base b;

Fun pFun = NULL;

cout << "虚函数表地址:" << (int*)(&b) << endl;

cout << "虚函数表 — 第一个函数地址:" << (int*)*(int*)(&b) << endl;

/*这里的一点争议的个人看法*/

原文认为(int*)(&b)是虚表的地址,而很多网友都说,(包括我也认为):(int *)*(int*)(&b)才是虚表地址

而(int*)*((int*)*(int*)(&b)); 才是虚表第一个虚函数的地址。

其实看后面的调用pFun = (Fun)*((int*)*(int*)(&b)); 就可以看出,*((int*)*(int*)(&b));转成函数指针给pFun,然后正确的调用到了虚函数virtual void f()。

// Invoke the first virtual function

pFun = (Fun)*((int*)*(int*)(&b));

pFun();

实际运行经果如下:(Windows XP+VS2003, Linux 2.6.22 + GCC 4.1.3)

虚函数表地址:0012FED4

虚函数表 — 第一个函数地址:0044F148

Base::f

通过这个示例,我们可以看到,我们可以通过强行把&b转成int *,取得虚函数表的地址,然后,再次取址就可以得到第一个虚函数的地址了,也就是Base::f(),这在上面的程序中得到了验证(把int* 强制转成了函数指针)。通过这个示例,我们就可以知道如果要调用Base::g()和Base::h(),其代码如下:

(Fun)*((int*)*(int*)(&b)+0); // Base::f()

(Fun)*((int*)*(int*)(&b)+1); // Base::g()

(Fun)*((int*)*(int*)(&b)+2); // Base::h()

这个时候你应该懂了吧。什么?还是有点晕。也是,这样的代码看着太乱了。没问题,让我画个图解释一下。如下所示:

注意:在上面这个图中,我在虚函数表的最后多加了一个结点,这是虚函数表的结束结点,就像字符串的结束符“\0”一样,其标志了虚函数表的结束。这个结束标志的值在不同的编译器下是不同的。在WinXP+VS2003下,这个值是NULL。而在Ubuntu 7.10 + Linux 2.6.22 + GCC 4.1.3下,这个值是如果1,表示还有下一个虚函数表,如果值是0,表示是最后一个虚函数表。

下面,我将分别说明“无覆盖”和“有覆盖”时的虚函数表的样子。没有覆盖父类的虚函数是毫无意义的。我之所以要讲述没有覆盖的情况,主要目的是为了给一个对比。在比较之下,我们可以更加清楚地知道其内部的具体实现。

一般继承(无虚函数覆盖)

下面,再让我们来看看继承时的虚函数表是什么样的。假设有如下所示的一个继承关系:

请注意,在这个继承关系中,子类没有重载任何父类的函数。那么,在派生类的实例中,其虚函数表如下所示:

对于实例:Derive d; 的虚函数表如下:

我们可以看到下面几点:

1)虚函数按照其声明顺序放于表中。

2)父类的虚函数在子类的虚函数前面。

我相信聪明的你一定可以参考前面的那个程序,来编写一段程序来验证。

一般继承(有虚函数覆盖)

覆盖父类的虚函数是很显然的事情,不然,虚函数就变得毫无意义。下面,我们来看一下,如果子类中有虚函数重载了父类的虚函数,会是一个什么样子?假设,我们有下面这样的一个继承关系。

为了让大家看到被继承过后的效果,在这个类的设计中,我只覆盖了父类的一个函数:f()。那么,对于派生类的实例,其虚函数表会是下面的一个样子:

我们从表中可以看到下面几点,

1)覆盖的f()函数被放到了虚表中原来父类虚函数的位置。

2)没有被覆盖的函数依旧。

这样,我们就可以看到对于下面这样的程序,

Base *b = new Derive();

b->f();

由b所指的内存中的虚函数表的f()的位置已经被Derive::f()函数地址所取代,于是在实际调用发生时,是Derive::f()被调用了。这就实现了多态。

多重继承(无虚函数覆盖)

下面,再让我们来看看多重继承中的情况,假设有下面这样一个类的继承关系。注意:子类并没有覆盖父类的函数。

对于子类实例中的虚函数表,是下面这个样子:

我们可以看到:

1) 每个父类都有自己的虚表。

2) 子类的成员函数被放到了第一个父类的表中。(所谓的第一个父类是按照声明顺序来判断的)

这样做就是为了解决不同的父类类型的指针指向同一个子类实例,而能够调用到实际的函数。

多重继承(有虚函数覆盖)

下面我们再来看看,如果发生虚函数覆盖的情况。

下图中,我们在子类中覆盖了父类的f()函数。

下面是对于子类实例中的虚函数表的图:

我们可以看见,三个父类虚函数表中的f()的位置被替换成了子类的函数指针。这样,我们就可以任一静态类型的父类来指向子类,并调用子类的f()了。如:

Derive d;

Base1 *b1 = &d;

Base2 *b2 = &d;

Base3 *b3 = &d;

b1->f(); //Derive::f()

b2->f(); //Derive::f()

b3->f(); //Derive::f()

b1->g(); //Base1::g()

b2->g(); //Base2::g()

b3->g(); //Base3::g()

安全性

每次写C++的文章,总免不了要批判一下C++。这篇文章也不例外。通过上面的讲述,相信我们对虚函数表有一个比较细致的了解了。水可载舟,亦可覆舟。下面,让我们来看看我们可以用虚函数表来干点什么坏事吧。

一、通过父类型的指针访问子类自己的虚函数

我们知道,子类没有重载父类的虚函数是一件毫无意义的事情。因为多态也是要基于函数重载的。虽然在上面的图中我们可以看到Base1的虚表中有Derive的虚函数,但我们根本不可能使用下面的语句来调用子类的自有虚函数:

Base1 *b1 = new Derive();

b1->f1(); //编译出错

任何妄图使用父类指针想调用子类中的未覆盖父类的成员函数的行为都会被编译器视为非法,所以,这样的程序根本无法编译通过。但在运行时,我们可以通过指针的方式访问虚函数表来达到违反C++语义的行为。(关于这方面的尝试,通过阅读后面附录的代码,相信你可以做到这一点)

二、访问non-public的虚函数

另外,如果父类的虚函数是private或是protected的,但这些非public的虚函数同样会存在于虚函数表中,所以,我们同样可以使用访问虚函数表的方式来访问这些non-public的虚函数,这是很容易做到的。

如:

class Base {

private:

virtual void f() { cout << "Base::f" << endl; }

};

class Derive : public Base{

};

typedef void(*Fun)(void);

void main() {

Derive d;

Fun pFun = (Fun)*((int*)*(int*)(&d)+0);

pFun();

}

#include <iostream.h>

class Base

{public :

int a1;

virtual void f(){

     cout<<(int*)this<<endl;

     cout<<a1<<endl;

    // cout<<"ff"<<endl;    

    //  g(3);

    //   a1=1;
}

void g(int b)

{

b=4;

a1=123;

cout<<"asdf"<<endl;

}

};
typedef void(*fun)(Base *) ;
void main()

{ Base a;

a.a1=123;

cout<<a.a1<<endl;

cout<<(int*)&a<<endl;

cout<<(int*)*(int *)(&a)<<endl;

cout<<*((int *)(&a))<<endl;
fun b=(fun)*(int*)*((int *)(&a));

cout<<(int*)&a<<endl;      

 b(&a);

结束语

C++这门语言是一门Magic的语言,对于程序员来说,我们似乎永远摸不清楚这门语言背着我们在干了什么。需要熟悉这门语言,我们就必需要了解C++里面的那些东西,需要去了解C++中那些危险的东西。不然,这是一种搬起石头砸自己脚的编程语言。


2016-07-22 09:32:35 ranxiaoxu123 阅读数 217

1. virtual关键字申明的函数叫做虚函数,虚函数肯定是类的成员函数。
2. 
存在虚函数的类都有一个一维的虚函数表叫做虚表。类的对象有一个指向虚表开始的虚指针。虚表是和类对应的,虚表指针是和对象对应的。
3. 
多态性是一个接口多种实现,是面向对象的核心。分为类的多态性和函数的多态性。
4. 
多态用虚函数来实现,结合动态绑定。
5. 
纯虚函数是虚函数再加上= 0
6. 
抽象类是指包括至少一个纯虚函数的类。

纯虚函数:virtual void breathe()= 0;即抽象类!必须在子类实现这个函数!即先有名称,没内容,在派生类实现内容!

我们先看一个例子:

[cpp] viewplaincopy

1.  #include <iostream>

2.  

3.  using namespace std;

4.  

5.  class animal  

6.  {  

7.  public:  

8.         void sleep()  

9.         {  

10.               cout<<"animal sleep"<<endl;  

11.        }  

12.        void breathe()  

13.        {  

14.               cout<<"animal breathe"<<endl;  

15.        }  

16. };  

17. class fish:public animal  

18. {  

19. public:  

20.        void breathe()  

21.        {  

22.               cout<<"fish bubble"<<endl;  

23.        }  

24. };  

25. void main()  

26. {  

27.        fish fh;  

28.        animal *pAn=&fh; // 隐式类型转换  

29.        pAn->breathe();  

30. }  


注意,在例1-1的程序中没有定义虚函数。考虑一下例1-1的程序执行的结果是什么?
答案是输出:animal breathe


       我们在main()函数中首先定义了一个fish类的对象fh,接着定义了一个指向animal类的指针变量pAn,将fh的地址赋给了指针变量pAn,然后利用该变量调用pAn->breathe()。许多学员往往将这种情况和C++的多态性搞混淆,认为fh实际上是fish类的对象,应该是调用fish类的breathe(),输出“fish bubble”,然后结果却不是这样。下面我们从两个方面来讲述原因。


1
编译的角度
C++
编译器在编译的时候,要确定每个对象调用的函数(要求此函数是非虚函数)的地址,这称为早期绑定(early binding),当我们将fish类的对象fh的地址赋给pAn时,C++编译器进行了类型转换,此时C++编译器认为变量pAn保存的就是animal对象的地址。当在main()函数中执行pAn->breathe()时,调用的当然就是animal对象的breathe函数。


2
内存模型的角度
我们给出了fish对象内存模型,如下图所示:


 

        我们构造fish类的对象时,首先要调用animal类的构造函数去构造animal类的对象,然后才调用fish类的构造函数完成自身部分的构造,从而拼接出一个完整的fish对象。当我们将fish类的对象转换为animal类型时,该对象就被认为是原对象整个内存模型的上半部分,也就是图1-1中的“animal的对象所占内存。那么当我们利用类型转换后的对象指针去调用它的方法时,当然也就是调用它所在的内存中的方法。因此,输出animal breathe,也就顺理成章了。

 

正如很多学员所想,在例1-1的程序中,我们知道pAn实际指向的是fish类的对象,我们希望输出的结果是鱼的呼吸方法,即调用fish类的breathe方法。这个时候,就该轮到虚函数登场了。

 

        前面输出的结果是因为编译器在编译的时候,就已经确定了对象调用的函数的地址,要解决这个问题就要使用迟绑定(late binding)技术。当编译器使用迟绑定时,就会在运行时再去确定对象的类型以及正确的调用函数。而要让编译器采用迟绑定,就要在基类中声明函数时使用virtual关键字(注意,这是必须的,很多学员就是因为没有使用虚函数而写出很多错误的例子),这样的函数我们称为虚函数。一旦某个函数在基类中声明为virtual,那么在所有的派生类中该函数都是virtual,而不需要再显式地声明为virtual

下面修改例1-1的代码,将animal类中的breathe()函数声明为virtual,如下:

[cpp] viewplaincopy

1.  #include <iostream>  

2.  

3.  using namespace std;

4.  

5.  class animal  

6.  {  

7.  public:  

8.      void sleep()  

9.      {  

10.         cout<<"animal sleep"<<endl;  

11.     }  

12.     virtual void breathe()  

13.     {  

14.         cout<<"animal breathe"<<endl;  

15.     }  

16. };  

17.   

18. class fish:public animal  

19. {  

20. public:  

21.     void breathe()  

22.     {  

23.         cout<<"fish bubble"<<endl;  

24.     }  

25. };  

26. 

27. void main()  

28. {  

29.     fish fh;  

30.     animal *pAn=&fh; // 隐式类型转换  

31.     pAn->breathe();  

32. }  


        
大家可以再次运行这个程序,你会发现结果是“fish bubble”,也就是根据对象的类型调用了正确的函数。
那么当我们将breathe()声明为virtual时,在背后发生了什么呢?



      编译器在编译的时候,发现animal类中有虚函数,此时编译器会为每个包含虚函数的类创建一个虚表(即vtable),该表是一个一维数组,在这个数组中存放每个虚函数的地址。对于例1-2的程序,animalfish类都包含了一个虚函数breathe(),因此编译器会为这两个类都建立一个虚表,(即使子类里面没有virtual函数,但是其父类里面有,所以子类中也有了)如下图所示:

 

        那么如何定位虚表呢?编译器另外还为每个类的对象提供了一个虚表指针(即vptr),这个指针指向了对象所属类的虚表。在程序运行时,根据对象的类型去初始化vptr,从而让vptr正确的指向所属类的虚表,从而在调用虚函数时,就能够找到正确的函数。对于例1-2的程序,由于pAn实际指向的对象类型是fish,因此vptr指向的fish类的vtable,当调用pAn->breathe()时,根据虚表中的函数地址找到的就是fish类的breathe()函数。

 

       正是由于每个对象调用的虚函数都是通过虚表指针来索引的,也就决定了虚表指针的正确初始化是非常重要的。换句话说,在虚表指针没有正确初始化之前,我们不能够去调用虚函数。那么虚表指针在什么时候,或者说在什么地方初始化呢?

 

        答案是在构造函数中进行虚表的创建和虚表指针的初始化。还记得构造函数的调用顺序吗,在构造子类对象时,要先调用父类的构造函数,此时编译器只看到了父类,并不知道后面是否后还有继承者,它初始化父类对象的虚表指针,该虚表指针指向父类的虚表。当执行子类的构造函数时,子类对象的虚表指针被初始化,指向自身的虚表。对于例2-2的程序来说,当fish类的fh对象构造完毕后,其内部的虚表指针也就被初始化为指向fish类的虚表。在类型转换后,调用pAn->breathe(),由于pAn实际指向的是fish类的对象,该对象内部的虚表指针指向的是fish类的虚表,因此最终调用的是fish类的breathe()函数。
要注意:对于虚函数调用来说,每一个对象内部都有一个虚表指针,该虚表指针被初始化为本类的虚表。所以在程序中,不管你的对象类型如何转换,但该对象内部的虚表指针是固定的,所以呢,才能实现动态的对象函数调用,这就是C++多态性实现的原理。

 

总结(基类有虚函数):

1. 每一个类都有虚表。
2. 
虚表可以继承,如果子类没有重写虚函数,那么子类虚表中仍然会有该函数的地址,只不过这个地址指向的是基类的虚函数实现。如果基类有3个虚函数,那么基类的虚表中就有三项(虚函数地址),派生类也会有虚表,至少有三项,如果重写了相应的虚函数,那么虚表中的地址就会改变,指向自身的虚函数实现。如果派生类有自己的虚函数,那么虚表中就会添加该项。
3. 
派生类的虚表中虚函数地址的排列顺序和基类的虚表中虚函数地址排列顺序相同。

 

        这就是C++中的多态性。当C++编译器在编译的时候,发现animal类的breathe()函数是虚函数,这个时候C++就会采用迟绑定(late binding)技术。也就是编译时并不确定具体调用的函数,而是在运行时,依据对象的类型(在程序中,我们传递的fish类对象的地址)来确认调用的是哪一个函数,这种能力就叫做C++的多态性。我们没有在breathe()函数前加virtual关键字时,C++编译器在编译时就确定了哪个函数被调用,这叫做早期绑定(early binding)。

C++
的多态性是通过迟绑定技术来实现的。

C++
的多态性用一句话概括就是:在基类的函数前加上virtual关键字,在派生类中重写该函数,运行时将会根据对象的实际类型来调用相应的函数。如果对象类型是派生类,就调用派生类的函数;如果对象类型是基类,就调用基类的函数。

虚函数是在基类中定义的,目的是不确定它的派生类的具体行为。

例:

定义一个基类:class Animal//动物。它的函数为breathe()//呼吸。
再定义一个类class Fish//。它的函数也为breathe()
再定义一个类class Sheep //羊。它的函数也为breathe()
为了简化代码,将Fish,Sheep定义成基类Animal的派生类。

然而FishSheepbreathe不一样,一个是在水中通过水来呼吸,一个是直接呼吸空气。所以基类不能确定该如何定义breathe,所以在基类中只定义了一个virtual breathe,它是一个空的虚函数。具本的函数在子类中分别定义。程序一般运行时,找到类,如果它有基类,再找它的基类,最后运行的是基类中的函数,这时,它在基类中找到的是virtual标识的函数,它就会再回到子类中找同名函数。派生类也叫子类。基类也叫父类。这就是虚函数的产生,和类的多态性(breathe)的体现。

这里的多态性是指类的多态性。
函数的多态性是指一个函数被定义成多个不同参数的函数,它们一般被存在头文件中,当你调用这个函数,针对不同的参数,就会调用不同的同名函数。例:Rect()//矩形。它的参数可以是两个坐标点(pointpoint)也可能是四个坐标(x1,y1,x2,y2)这叫函数的多态性与函数的重载。

类的多态性,是指用虚函数和延迟绑定来实现的。函数的多态性是函数的重载。

        
一般情况下(没有涉及virtual函数),当我们用一个指针/引用调用一个函数的时候,被调用的函数是取决于这个指针/引用的类型。即如果这个指针/引用是基类对象的指针/引用就调用基类的方法;如果指针/引用是派生类对象的指针/引用就调用派生类的方法,当然如果派生类中没有此方法,就会向上到基类里面去寻找相应的方法。这些调用在编译阶段就确定了。

        当设计到多态性的时候,采用了虚函数和动态绑定,此时的调用就不会在编译时候确定而是在运行时确定。不在单独考虑指针/引用的类型而是看指针/引用的对象的类型来判断函数的调用,根据对象中虚指针指向的虚表中的函数的地址来确定调用哪个函数。

2011-10-25 00:16:00 weixin_33701294 阅读数 6

多态是面向对象的基本特征之一。而虚函数是实现多态的方法。那么virtual function到底如何实现多态的呢?

1 基类的内存分布情况
请看下面的sample

class A
{
void g(){.....}
};
则sizeof(A)=1;
如果改为如下:
class A
{
public:
    virtual void f()
    {
       ......
    }
    void g(){.....}
}
则sizeof(A)=4! 这是因为在类A中存在virtual function,为了实现多态,每个含有virtual function的类中都隐式包含着一个静态虚指针vfptr指向该类的静态虚表vtable, vtable中的表项指向类中的每个virtual function的入口地址
例如 我们declare 一个A类型的object :
    A c;
    A d;
则编译后其内存分布如下:
image
从 vfptr所指向的vtable可以看出,每个virtual function都占有一个entry,例如本例中的f函数。而g函数因为不是virtual类型,故不在vtable的表项之内。说明:vtab属于类成员静态pointer,而vfptr属于对象pointer

2 继承类的内存分布状况
假设代码如下:
public B:public A
{
public :
    int f() //override virtual function
    {
        return 3;
    }
};


A c;
A d;
B e;
编译后,其内存分布如下:
image

从中我们可以看出,B类型的对象e有一个vfptr指向vtable address:0x00400030 ,而A类型的对象c和d共同指向类的vtable address:0x00400050a


3 动态绑定过程的实现
    我们说多态是在程序进行动态绑定得以实现的,而不是编译时就确定对象的调用方法的静态绑定。
    其过程如下:
    程序运行到动态绑定时,通过基类的指针所指向的对象类型,通过vfptr找到其所指向的vtable,然后调用其相应的方法,即可实现多态。
例如:
A c;
B e;
A *pc=&e; //设置breakpoint,运行到此处
pc=&c;
此时内存中各指针状况如下:
image
可以看出,此时pc指向类B的虚表地址,从而调用对象e的方法。

继续运行,当运行至pc=&c时候,此时pc的vptr值为0x00420050,即指向类A的vtable地址,从而调用c的方法。
这就是动态绑定!(dynamic binding)或者叫做迟后联编(lazy compile)。

 

为了更加透析多态的原理,我们可以debug 程序在runtime时候的对象内存分布情况。

以下面这段简单的程序为例

// SimpleStack.cpp : Defines the entry point for the console application.
//

#include
"stdafx.h"

class Base
{
public
:
   
int
m_data;
   
static int
m_staticvalue;
    Base(
int
data)
    {
        m_data
=
data;
    }
   
virtual void
DoWork()
    {
    }
};

class
AnotherBase
{
public
:
   
virtual void
AnotherWork()
    {}
   
};

class DerivedClass:public Base,public
AnotherBase
{
public
:
    DerivedClass(
int
t_data):Base(t_data)
    {}

   
virtual    void
  DoWork()
    {
    }

   
virtual void
AnotherWork()
    {
    }
};

int Base::m_staticvalue=1
;

int main(int argc, char*
argv[])
{
   
    DerivedClass b(
1
);
    b.DoWork();

   
return 0
;
}


 

当程序运行后我们设置很简单的breakpoint: bp simplestack!derivedclass::dowork. 断点命中后的call stack如下:

0:000> kb
ChildEBP RetAddr  Args to Child             
0012ff20 0040102a 00daf6f2 00daf770 7ffd7000 SimpleStack!
DerivedClass::DoWork
0012ff80 004012f9 00000001 00420e80 00420dc0 SimpleStack!main+0x2a
0012ffc0 7c817077 00daf6f2 00daf770 7ffd7000 SimpleStack!mainCRTStartup+0xe9
0012fff0 00000000 00401210 00000000 78746341 kernel32!BaseProcessStart+0x23


这时,我们可以看看DerivedClass对象的内存内分布情况:

0:000> dt SimpleStack!DerivedClass 0012ff74
   +0x000 __VFN_table : 0x0040c020  //指向虚表的指针1
   +0x004 m_data           : 1
   =0040d030 Base::m_staticvalue : 1  //(类成员)
   +0x008
__VFN_table : 0x0040c01c  //指向虚表的指针2

可以看到,DerivedClass对象中包含两个指向虚表的指针,地址分别为0x0040c020 和0x0040c01c 。一个为指向override了BaseClass的方法的虚表,一个指向orverride了AnotherBase方法的虚表。

可以查看对应虚表中的方法:

0:000> dds 0x0040c01c
0040c01c  00401140 SimpleStack!DerivedClass::AnotherWork
0040c020  00401110 SimpleStack!DerivedClass::DoWork
0040c024  004010e0 SimpleStack!Base::DoWork
0040c028  004011a0 SimpleStack!AnotherBase::AnotherWork
......

通过以上分析,应该可以透析多态的本质了。

 

这种看内存分配方案真的不错的,^-^

 

自己也试了一下,虽然常用VC,不过也没注意过

 

#include <iostream>
using namespace std;
class base2
{
public:
virtual std::string ff(){return "base2";}
protected:
private:
};
class base
{
public:
virtual std::string f1(){return "base";}
virtual std::string f2(){return "base";}
virtual std::string f3(){return "base";}
protected:
private:
};
class child : public base , public base2
{
public:
virtual std::string f2(){return "child";}
virtual std::string f3(){return "child";}
protected:
private:
};
class grant : public child
{
public:
virtual std::string f3(){return "grant";}
protected:
private:
};
void main()
{
base a;
child b;
grant c;
string sa = a.f1();
string sb = b.f1();
string sc = c.f1();
}
// 内存状态
- a {...}
- __vfptr 0x0042f024 const base::`vftable'
[0x0] 0x00401014 base::f1(void)
[0x1] 0x00401055 base::f2(void)
[0x2] 0x00401032 base::f3(void)
- b {...}
- base {...}
- __vfptr 0x0042f038 const child::`vftable'{for `base'}
[0x0] 0x00401014 base::f1(void)
[0x1] 0x00401050 child::f2(void)
[0x2] 0x0040106e child::f3(void)
- base2 {...}
- __vfptr 0x0042f034 const child::`vftable'{for `base2'}
[0x0] 0x00401023 base2::ff(void)
- c {...}
- child {...}
- base {...}
- __vfptr 0x0042f05c const grant::`vftable'{for `base'}
[0x0] 0x00401014 base::f1(void)
[0x1] 0x00401050 child::f2(void)
[0x2] 0x0040103c grant::f3(void)
- base2 {...}
- __vfptr 0x0042f058 const grant::`vftable'{for `base2'}
[0x0] 0x00401023 base2::ff(void)

C++中虚函数的实现原理

阅读数 1815

C++中的虚函数的作用主要是实现了多态的机制。关于多态,简而言之就是用父类型别的指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”,这是一种泛型技术。所谓泛型技术,说白了就是试图使用不变的代码来实现可变的算法。比如:模板技术,RTTI技术,虚函数技术,要么是试图做到在编译时决议,要么试图做到运行时决议。关于虚函数的使用方法,我在这里不做过

博文 来自: wscxr57

C++中const实现原理

阅读数 699

抛出问题#includeusingnamespacestd;intmain(){constinti=8;int*pt=(int*)&i;*pt=5;cout

博文 来自: win_turn

C++中多态的实现原理

阅读数 1433

1.用virtual关键字申明的函数叫做虚函数,虚函数肯定是类的成员函数。2.存在虚函数的类都有一个一维的虚函数表叫做虚表。类的对象有一个指向虚表开始的虚指针。虚表是和类对应的,虚表指针是和对象对应的。3.多态性是一个接口多种实现,是面向对象的核心。分为类的多态性和函数的多态性。4.多态用虚函数来实现,结合动态绑定。5.纯虚函数是虚函数再加上=0。6.抽象类是指包

博文 来自: SMF0504

C++中函数重载的实现原理

阅读数 935

函数重载一、什么是函数重载在同一作用域类,一组函数的函数名相同,参数列表不同(个数不同、类型不同),返回值可同可不同。二、为什么要用函数重载在我们之前学习的C中,我们对一个功能函数要实现不同类型的调用时,就必须得取不同的名称。如果调用的非常的多,就必须得起好多的名字,这样就大大增加了工作量,所以在C++中,我们就考虑到了函数重载。三、函数重载是怎么实现的呢?在C++的底层,有重命名机制,当然重命名时

博文 来自: wd6428

C++中多态的实现原理

阅读数 599

C++中多态的实现原理多态是面向对象的基本特征之一。而虚函数是实现多态的方法。那么virtualfunction到底如何实现多态的呢?1基类的内存分布情况请看下面的sampleclassA{voidg(){.....}};则sizeof(A)=1;如果改为如下:classA{public:   virtua

博文 来自: winson_jason
没有更多推荐了,返回首页