数据结构与算法(二)概述

数据结构与算法都比较严谨,找了一篇通俗的介绍篇。

http://www.matrix67.com/blog/archives/90

《数据结构与算法分析》

4月7日买起来看,前几天才看完。这可以说明很多问题,比如,学习很紧张,没有时间;书本身很好,很有看头;看书看得很细心,很有耐心。
    打算大致写一下书里的内容。
    Data Structures and Algorithm Analysis in C, Second Edition,机械工业出版社。封面很丑,一个黑底版,上面有些大理石花纹,正中间生硬的摆一个原版封面,同样丑。一共12章,近400页。
    400多页是很多的。我们必须要“把厚书读薄”,厚的变薄的,薄的变一页,一页变一行,一行变成一个字。因此,我要在有限的字数内把整本书说完。

    算法分析,就是复杂度的问题。复杂度只算“最要命的”,比如,执行n^2的算法前来个快排根本不拖速度,n^2多的都豁出去了不在乎区区一个nlogn。书里对复杂度进行了严格的定义,包括O()、o()、Θ()、Ω()四种符号。简单地说,O(n^2)就是顶破天了搞个n^2次;o(n^2)就是天花板不到n^2,比n^2矮一点(比如希尔排序就是o(n^2),因为它再倒霉也达不到n^2);Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2,比如所有基于比较的排序都是Ω(nlogn);Θ(n^2)就是说它即是O(n^2)又是Ω(n^2),被天花板和水泥地夹在中间了,动不了了,就是它了。这里面有一个经典的例子,就是最大子序列(找数列中连续一段数之和最大)的四种算法,复杂度分别为O(n^3)、O(n^2)、O(nlogn)和O (n)。这书一个特色在于,对每种数据结构都有严格的算法复杂度证明,这往往是看上去最头痛的部分。

    表、栈和队列是三个基本的数据结构。说穿了表就是把数据找起来排排坐吃果果,找什么东西都来把整个队伍找一遍。栈就是一个桶,后放进去的先拿出来,它下面本来有的东西要等它出来之后才能出来,就好像你看到了一个丑人不可能今天的中饭还没吐出来就先把早饭吐出来了。栈是拿来模拟多个过程的调用的(比如递归),实际点的用途就是表达式计算队列好比堵车,先进去的先出来。先进队先买票,不能插队。常拿来实现广搜

    树,是一种植物,有很多枝枝丫丫。不同的是这里的树是倒着的,树枝朝下长。最上面叫根,尖尖的地方叫树叶,生出树叶的是他爸,他爸生的是他儿子。不管是根是树叶还是儿子还是儿子他爸都叫节点。我们常常把数据储存在节点上,并且以后还要不断地插入、改变和删除数据。
    二叉树就是每个分叉的地方最多分两个岔,而且还分得清左右。二叉查找树就是说把数据存在节点上,而且左边的都比他爸小,右边的都比他爸大,以后要找哪个数就可以只找其中的一边,一半一半地扔掉。在二叉查找树里也可以插入一个数,删掉一个数(只有一个儿子好办,有两个就把右边的最小的一个拿来替代这个),找最小的数(一直往左走),找最大的数(一直往右走),但是容易搞着搞着的树就变畸形了,比如说左边猛起长右边萎缩导致以后往左边走要走很久。我们就需要一种方法来让树左右差不多一样多而且左边的值仍然比右边的小。事实上这种方法已经找到了,而且不只一种方法,而是一卡车的方法,比如AVL、Splay、红黑树、Treap等。几种方法都靠一个叫“旋转”的技巧,就是把几个节点怎么个一转,左边的就跑到右边去了一点。看下面这个图你就明白了。

         ①                   ②
        /        旋转       / 
      ②   ZZ    ——>    XX  ①
     /                        / 
    XX  YY                    YY  ZZ

这样一来左边就少了,如果左边的XX本来很多的话就可以往上提一层从而平衡。同样地,右边多了反过来做就是了。这只是最简单的“单旋转”,事实上还有很多其它的较复杂的旋转方法。Splay树就是把刚才访问过的节点转啊转啊转啊转转到最顶上去,Treap就是每个节点附加一个随机的数,随时通过旋转保持儿子的这些随机数比他爸大,其余的有点复杂。这些方法都能使二叉查找树相对地平衡一些,防止畸变导致的时间浪费。
    B-树和二叉查找树有两个不同,一个是节点不存数据,数据全在树叶子上,二个是它不一定是二叉。数据仍然左边小右边大方便查找。每个节点最多的儿子数有限制,最多三叉的叫2-3树,最多四叉的叫2-3-4树。因为只有树叶上有数据,所以可以递归地用分裂的方法处理新插入后出现的分叉比规定的最多的儿子个数时还多的情况。比如,2-3树中如果哪里分了四个岔,就把它重新分成两个两个的岔。我们还规定,除了根以外,每个节点最少的儿子数是规定的最多儿子数的一半,除不尽取上整。容易想到,删除的话可以把插入时的分裂反过来做,什么时候只剩一个儿子了就和旁边的合并起来。

    Hash表又叫散列表,一般用于判断有没有重复。比如我想找我们班有没有两个一天生的,我们不必每两个人都来比较一次,而是准备一个年历,让人一个一个上去在他的生日那天那里画一个圈,如果谁要画圈时发现那里已经有一个圈了,就找到了一对。这个很简单,不说了。

堆,就是一陀一陀的东西。头重脚轻不算堆,要上面小下面大才算一个堆。堆是一棵二叉树,满足下面的始终比上面的大。它和二叉查找树比较起来既有好的又有不好的:好的就是要想知道数据里的最小值时根本就不用找了,直接就是最顶上的那个了;不好的就是堆除了这个以外基本上不能做别的事了。除了最顶上的那个以外,你几乎没办法控制其余的部分。当然,插入和删除数据这种基本操作还是可以做的。插入就是把数据暂时先放在最下面的某个位置,然后通过与它上面一个进行比较、交换不断往上冒直到已经到了自己的位置不能再向上为止。删除反起来,通过不断交换往下沉一直沉到底。因为是往下走,所以要考虑到一个把左边的放上来还是把右边的放上来的问题。当然,为了保证堆上小下大的性质,应该把小的一边换上来。刚才说过,由于你只能“看”到最顶上的东西,不知道中间部分是什么样,我们通常只删除最小的(最上面的)那个节点。其实堆还有一个最大的好处:容易写代码。因为我们可以有意让数据把树“排得满满的”,满到它是一行一行挨着排下来的。这叫做“完全二叉树”。我们可以给完全二叉树编个号,从上到下从左到右挨着数下来。根是1,找左儿子就乘2,找右儿子就乘2加1,找它爸就 div 2。以后叫谁就是谁,很方便。这样整个树就可以用一个数组实现了。由于堆基本上只用来找最小,因此如果某个问题要求很复杂的话,最好还是用成二叉查找树;当然,如果问题只要求插入、删除和找最小三种操作,你应该毫不犹豫地选择堆,毕竟找最小时堆方便得多,写起又简单。什么时候出现这种问题呢?比如说,我的女友排起队的,我每次要选一个最纯洁的,就是受那些的影响最小的人。每当我遇见了一个新的美女,我就把她放在这个队伍里合适的位置供我以后娱乐。这时,我只关心每次插入、取最小和删最小。这个队伍就可以用一个堆来优化。因此,堆还有一个形象的名字叫优先队列。如果谁问题目要求不找最小找最大怎么办,那人肯定是个傻子,把堆变通一下,上大下小不就完了吗?
    研究堆麻烦的地方就是堆的合并。如何把两个堆合并成一个堆?这个解决了很有用,至少上面的这些操作跟着全部统一了:插入就是与一个单节点的堆合并,删除根就是把根不要了,把根的左右两边(显然还是堆)合并起来。一个简单的办法就是递归地不断把根大的堆往根小的堆的右边合并,把新得到的堆替换原来的右儿子。注意递归过程中哪个根大哪个根小是不停在改变的。这样下来的结果就是典型的“右倾错误”,而且破坏了完全二叉树的完美。为此,我们想要随时保证堆的最右边尽量少。于是,干脆不要完全二叉树了,不过是多写几行代码嘛。这个不存在像二叉查找树那样“某一边越做越多”的退化问题,因为对于一个堆来说,反正我只管最顶上的东西,下面平不平衡无所谓,只要不挡我合并的道就行。于是,我们想到人为下一个能让堆尽量往左边斜的规定。这个规定就是,对于左右两个儿子来说,左边那个离它下面最近的两个儿子不全(有可能一个都没有)的节点的距离比右边那个的远。这规定看着麻烦,其实还真有效,最右边的路径的长比想像中的变得短得多。这就叫左式堆(左偏树)。这下合并倒是方便了,但合并着合并着要不了多少次右边又多了。解决的办法就是想办法随时保持左式堆的性质。办法很简单,你合并不是递归的吗?每次递归一层后再看看左右两边儿子离它下面没有两个儿子的节点哪个远,如果右边变远了就把左边右边调一下。由于我们已经没有用数组实现这玩意了,因此链表搞起很简单。这个对调左右的方法给了我们一个启发:哪里还要管什么到没有两个儿子的节点的距离嘛,既然我每次都在往右合并,我为什么不每次合并之后都把它对调到左边去呢?这种想法是可行的,事实上它还有一个另外的名字,叫斜堆。
    二项堆更强,它也是堆,也能合并,不过它已经超越了堆的境界了:它不是一个堆,而是满屋子的堆。也就是说,找最小值不能再一下子找到了,而是要把二项堆中的每个堆的顶部都看一下。二项堆的合并也很强,直接把根大的堆放在根小的堆的下面。这意味着二项堆的每个堆都可能不是二叉树了。这增加了编程的难度,不过可以用一个叫做“左儿子右兄弟”的技巧来解决问题。这个技巧,说穿了就是仍然用二叉树来表示多叉树:把树画好,然后规定节点的左儿子是下一层的最左边那个,右儿子就是它右边那个。就是说,左儿子才是真正的儿子,右儿子不过是一起生出来的。为了让二项堆好看些,让堆的个数和大小保持在一个能快速操作的数目和比例内,二项堆作出了一个明智的规定:每个堆的大小(总的节点个数)只能是1、2、4、8、16…中的一个,且每种大小的堆只能有一个。若干个互不相同的2的幂足以表示任意一个正整数,因此这个规定可以保证不管多大的二项堆都能表示出来。保持这个性质很简单,遇到两个大小相等的堆就合并起来成为一个大一号的堆。由于总是两个大小相等的堆在合并,因此二项堆中的每一个堆都有一个奇妙的样子,看看本文结束后下面附的一个大小为16的堆的示意图,再看一下,再看一下,你就能体会到了。图下面有一个用“左儿子右兄弟”法表示的同样的树,其中,往下走的线是左儿子,往右走的线是右儿子。
    最后简单说一下Fibonacci堆。保持一个跟着变的数组记录现在某个节点在堆中的位置,我们还是可以对堆里的数据进行一些操作的,至少像删除、改变数值等操作是完全可以的。但这个也需要耗费一些时间。Fibonacci堆相当开放,比二项堆更开放,它可以不花任何时间减少(只能是减少)某个节点的值。它是这样想的:你二项堆都可以养一屋子的堆,我为什么不行呢?于是,它懒得把减小了的节点一点一点地浮上去,而是直接就把它作为根拿出来当成一个新的堆。每次我要查最小值时我就再像二项堆一样(但不要求堆的大小了)一个个合并起来还原成一个堆。当然,这样的做法是有适用范围的,就是前面说的数值只能是减少。在什么时候需要一个数值只减少不增加的堆结构呢?莫过于Dijkstra一类的图论算法了。所以说,这些图论算法用Fibonacci堆优化可以进一步提速。
有一个女人的男人很幸福。事实上,这是片面的。应该说,有不止一个女人的男人更幸福。但是,这样会坏了我的人品,而且被女的知道了也不好。两个耍得好的女人话很多,秘密在女人中传得很快。于是,我打算不同时和两个耍得好的女的耍朋友。后来我意识到,这样也不行。女人太无敌了,即使A与B耍得好,B与C耍得好,A和C的消息也是互通的。哪怕只有一个朋友关系也能把两群人联系在一起。我不得不改变策略,使得我的女朋友之间没有任何渠道传递信息。也就是说,在上面的A、B、C三个人中,虽然A和C没有直接的联系,但我也不能同时和A、C耍。不久后,我想知道,某两个女人是否可以通过某条“朋友链”传递信息。这就是所谓的等价关系——基本上算是判断一个无向图的连通性。就像很多个集合,每次选两个并成一个,而且我们随时想知道某两个元素经过前面的合并后是否在同一个集合内。怎么办呢?后来有一天,我发现那些小女生喜欢玩些认亲戚的游戏,什么谁是谁妈,谁是谁姐,谁是谁女儿之类的(不知道为什么这些疯女人喜欢搞这些)。我突然恍然大悟,我的问题可以用树结构来完成。亲戚的亲戚还是亲戚,但有一点总相同:所有亲戚的始祖总是一样的。始祖一样的都是一伙的。因此,把两个集合并在一起,只要让其中一个集合的根成为另一个集合中的某个元素的一个儿子就行了,这种家谱关系的改变将使前面的集合中所有的元素拥有和后面那个集合一样的鼻祖,而这将成为这些元素的“标志”。这个想法的灵感是来自女人世界的,因此女人还是有一定的作用。     这就叫并查集,又叫不相交集。它可以合并两个集合并且查询两个元素是否在同一集合。我们有一个很有效的剪枝:递归时顺便把路上经过的祖祖辈辈全部变成根的儿子。这样的程序只用2行来解决。function find_set(x:integer):integer;   begin   if x<>p[x] then p[x]:=find_set(p[x]);   exit(p[x]);end;
    p[x]表示元素x的父亲的位置。一开始,p[x]都等于x自己,表示自己一个人是一个集合。函数find_set(x)将返回x所在集合(一棵树)的根。     并查集还有些其它的剪枝和一些很复杂的效率分析问题,这里不多说了。
    写到这里,《数据结构与算法分析》中的几个大块内容算是说清楚了。由于本文的叙述调整了原书各章节的顺序且至此还没有涉及书里的一些小问题,因此这里想把遗漏下的一些小东西提一下。     有一些树结构可能要求同时满足多个要求。比如一个简单的问题:如果要求构造一个堆使得既能查找最小元素又能查找最大元素怎么办?这时,我们可以用一个特殊的方法来实现:树的单数层满足一种性质,树的双数层满足另一种性质。我们用一个叫做最小-最大堆的东西来实现前面说的问题。这个堆的双数层的数据小于它爸大于它爸的爸,单数层的数据反过来,大于它爸小于它爸的爸。用类似的方法,我们还可以设计一个二叉查找树,使得它能够支持含有2种不同类型元素的数据。在单数层按其中一种操作,在双数层按另一种操作,这样可以方便的查找同时位于两个不同类元素的指定区间内的数据。这种二叉查找树叫做2-d树。扩展2-d 树,我们可以得到k-d树。这些数据结构的具体实现方法这里不说了,书上本来也是作为一个习题介绍的。     书里的第7章花了近50页介绍并分析各种排序算法,分析得很全。其中第11节花了10页介绍外部排序。所谓外部排序,就是说怎样快速地把一个根本无法全部读入内存的大文件进行排序。很多排序之所以可行是因为它们可以随意读写任意一个指定的数。但在大文件里,我们无法实现“第1234567890个元素和第 123个元素交换位置”,更无法实现递归之类的操作,而只能像磁带一样“过一遍”,从头到尾扫一遍,由于文件太大内存不能接受,因此必须要读一截扔一截。于是,外部排序产生了。不要以为这个限制会把排序速度拖得很慢。事实上,外部排序同样突破了O(n^2)的界限。它借助了归并排序中的“合并两个已经有序的数组”的思想,因为这个操作可以边读就边做。把文件先拆成两个文件,再把每个文件处理成一段一段的等长有序序列(一段多大取决于内存能一次处理多大),然后不断从两个文件中各取一段出来合并。可以看到,每段有序序列的长度变长了,变成了2倍长。过不了几次,这个长度将变成文件的总长。注意,我们必须要让每次合并时为下次合并做好准备(就是说合并后的结果仍然要是两个分了段的文件)。一个好的方法是将合并的结果交替存在两个不同的新文件中。     第9章讲图论算法。讲了图的遍历(广搜和深搜)、AOV、AOE、Dijkstra、网络流、Prim、Kruskal和NP问题。在讲深搜时,我学到了两个新东西,用线性时间查找割点(去掉了的话图就不连通了的点)和强分支(有向图中的一个分支满足其中任两个点之间都可以互相到达)。后来发现黑书上也有,又觉得这个东西很不好说,因此这里不想说了。说到了黑书还想顺便补一句:黑书真的看不得——太多错误了。不是说LRJ怎么了,LRJ在真正的大问题上有他的思想和经验,但很多细节的概念他也是昏的,这不利于初学者接受知识。不信哪天我还要写一篇日志纠正黑书的错误。引用政治书上抨击“人性自私论”的经典语言:“从理论到实践都是错的”。     第10章讲“算法设计技巧”,大概是些贪心啊,分治啊,动规啊,回溯啊,随机化啊之类的。调度问题、Huffman树、装箱问题近似算法、最近点距分治算法、最优二叉查找树、Floyd-Warshall、跳跃表、Miller-Rabin素性测试、博弈算法等都在这章中有讲,并且讲得相当好。由于这不是本书的重点内容,这里也不说了。     第11章整章都在讲摊还分析。这是一个相当复杂的问题,是分析时间复杂度的一个有力工具。它的分析告诉我们的不是某一个操作的复杂度,而是重复执行某一个操作的平均复杂度。研究这个是很有必要的,因为我们会遇到一些“越变越慢”的退化情形和“自我保持不变”的自调整性等数据结构,单个操作并不能反映它真正的效率。
    到这里,这本书的所有东西都已经介绍完了。总的来说,这本书很值得一看(虽然有些地方翻译得很差)。它的理论性很强,证明过程完整(再复杂的分析它也证明得很清楚,满足那些刨根问底的人);整本书自成一个体系,前后呼应;习题具有研究性,与课文互相补充。事实上,这些都是国外教材共有的特点。这算是我完整读过的第一本国外教材,今后我还会读一些。这几天在看《组合数学》(仍然是这个出版社出版的),看完后也打算写一下“对《组合数学》一书中部分内容的形象理解”。读一本国外教材,你会发现它与国内书籍的不同并会从中获益更多。
    这篇文章就写到这里了。号称是一个5000字缩写,没想到写着写着已经超过8000字了。而且,这个并不是缩写,而是一些简单的、系统的、清晰的、形象化的思想和理解。这篇文章或许对已经知道一些有关知识的人有用,但不适合一点也没有接触过数据结构与算法分析的人。如果有一个人能从中收获一件东西,我写这个的目的也就达到了。
(完)

数据结构与算法(一)基础

数据结构是一门研究非数值计算程序设计问题中,计算机的操作对象以及他们之间的关系和操作的学科

数据是用来描述现实世界的数字字符图像声音以及能够输入到计算机中并能被计算机识别的符号的集合

数据结构三方面内容:

(1)数据的逻辑结构指数据元素之间固有的逻辑关系

(2)数据的存储结构指数据元素及其关系在计算机内的表示

( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除,更新,查询,排序等

一.数据结构基础概念

逻辑结构包括:

(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。
(2)非线性结构,一个结点可能有多个直接前趋和后继。:集合,树形结构、图形结构

存储结构包括:

1)顺序存储,逻辑相邻的结点存储在物理上相邻的存储单元内。逻辑顺序与存储顺序一致
2)链接存储,结点间的逻辑关系由附加指针字段表示,1.逻辑顺序与存储顺序不一致2.每个节点存取的费时不同
3)索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。
4)散列存储,按结点的关键字直接计算出存储地址。

(操作)算法时间复杂度

是该算法的时间耗费,是求解问题规模n的函数。记为O(n)。
时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

评价算法的标准:正确性,高效性,健壮性(容错),可读性。

抽象数据类型的形式描述为:

ADT = ( D,S,P )

  其中:D 是数据对象,

S 是 D 上的关系集,

P 是 D 的基本操作集。

ADT 抽象数据类型名 {

 数据对象: 数据对象的定义

 数据关系: 数据关系的定义

 基本操作: 基本操作的定义

} ADT 抽象数据类型名

二.各类数据结构特点(算法时间复杂度)

    索引 插入 删除 查询 排序
  静态数组 O(1) O(1)  
  动态数组 O(1) O(n) O(n) O(n)  
  单链表 O(n) O(1) O(1) O(n)  
  双链表 O(n) O(1) O(1) O(n)  
  二叉排序树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  红黑树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  B树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  笛卡尔树 O(log(n)) O(log(n)) O(log(n))  
  哈希表 O(1) O(1) O(1)  
             
             
             
排序:

image

C++ 虚函数表解析

转载自耗子叔酷壳网(http://coolshell.cn/articles/7992.html

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

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

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

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

虚函数表

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

这里我们着重看一下这张虚函数表。C++的编译器应该是保证虚函数表的指针存在于对象实例中最前面的位置(这是为了保证取到虚函数表的有最高的性能——如果有多层继承或是多重继承的情况下)。 这意味着我们通过对象实例的地址得到这张虚函数表,然后就可以遍历其中函数指针,并调用相应的函数。

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

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

1

2

3

4

5

6

7

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的实例来得到虚函数表。 下面是实际例程:

1

2

3

4

5

6

7

8

9

10

11

12

typedef void(*Fun)(void);

Base b;

Fun pFun = NULL;

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

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

// 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(),其代码如下:

1

2

3

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

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

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

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

01

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

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

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

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

02

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

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

03

我们可以看到下面几点:
1)虚函数按照其声明顺序放于表中。
2)父类的虚函数在子类的虚函数前面。

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

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

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

04

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

05

我们从表中可以看到下面几点,
1)覆盖的f()函数被放到了虚表中原来父类虚函数的位置。
2)没有被覆盖的函数依旧。

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

1

2

3

Base *b = new Derive();

b->f();

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

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

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

06

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

07

我们可以看到:
1) 每个父类都有自己的虚表。
2) 子类的成员函数被放到了第一个父类的表中。(所谓的第一个父类是按照声明顺序来判断的)

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

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

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

08

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

09

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

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

1

2

3

4

5

6

7

8

9

10

11

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的虚函数,但我们根本不可能使用下面的语句来调用子类的自有虚函数:

1

2

Base1 *b1 = new Derive();

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

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

二、访问non-public的虚函数

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

如:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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();

}

结束语

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

附录一:VC中查看虚函数表

我们可以在VC的IDE环境中的Debug状态下展开类的实例就可以看到虚函数表了(并不是很完整的)

附录 二:例程

下面是一个关于多重继承的虚函数表访问的例程:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

#include <iostream>

using namespace std;

class Base1 {

public:

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

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

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

};

class Base2 {

public:

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

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

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

};

class Base3 {

public:

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

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

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

};

class Derive : public Base1, public Base2, public Base3 {

public:

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

virtual void g1() { cout << "Derive::g1" << endl; }

};

typedef void(*Fun)(void);

int main()

{

Fun pFun = NULL;

Derive d;

int** pVtab = (int**)&d;

//Base1's vtable

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

pFun = (Fun)pVtab[0][0];

pFun();

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

pFun = (Fun)pVtab[0][1];

pFun();

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

pFun = (Fun)pVtab[0][2];

pFun();

//Derive's vtable

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

pFun = (Fun)pVtab[0][3];

pFun();

//The tail of the vtable

pFun = (Fun)pVtab[0][4];

cout<<pFun<<endl;

//Base2's vtable

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

pFun = (Fun)pVtab[1][0];

pFun();

//pFun = (Fun)*((int*)*(int*)((int*)&d+1)+1);

pFun = (Fun)pVtab[1][1];

pFun();

pFun = (Fun)pVtab[1][2];

pFun();

//The tail of the vtable

pFun = (Fun)pVtab[1][3];

cout<<pFun<<endl;

//Base3's vtable

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

pFun = (Fun)pVtab[2][0];

pFun();

//pFun = (Fun)*((int*)*(int*)((int*)&d+1)+1);

pFun = (Fun)pVtab[2][1];

pFun();

pFun = (Fun)pVtab[2][2];

pFun();

//The tail of the vtable

pFun = (Fun)pVtab[2][3];

cout<<pFun<<endl;

return 0;

}

注:本文年代久远,所有的示例都是在32位机上跑的。