大概两个星期前看到个题目（还是从TopLanguage过去的）：

设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度

为O（N），且只允许使用两个附加变量。

苦思冥想两个星期，今天写了段代码，基本实现“时间复杂度为O（N）”的要求，不过用的变量那就多了…
下面是我的杰作：

void mvArray(int *a, int k, int n)
{
	if (k % n == 0)		return ;
	int original = 0, instead = 0;
	int	x = n;
	instead = a[0];
	int target = 0;
	int j = 0;
	while (x--)
	{
		target = target + k%n< n ? j+k%n : (j+k%n)%n;
		instead = a[target];
		a[target] = a[j];
	}
}

假设有a[]={0,1,2,3,4,5,6,7,8,9}这样10个元素的数组，要求向右顺移7位。算法从数组的第一个元素开始，a[0]将移动到a[7]，此时a[7]被拿出来，算出a[7]要移动到的目标位，本例中为a[4]，那么a[4]的值被修改为原来a[7]的值，原来的a[4]被拿出来，继续如此循环下去。当目标位的原值与目标位即将被赋予的新值相等时，表示这一个环路已经完成全部的替换。将此次环路的开始位加1，继续下一个环路，直到达到数组元素的个数，跳出循环。此时该数组向右顺移7位的操作已经全部完成。 怎么样，是不是很复杂？连我自己都觉得复杂的不行。可就是写的这么复杂，也只完成题目一半的要求，使用的附加变量远远超过两个。 如果你有兴趣，可以自己试试写个函数出来。懒的写的就直接看下去吧，这里有一个非常优秀的解答。 Read the rest of this entry »

这篇博客本来上周日就应该写出来了，为什么呢？因为我周六晚上做梦的时候梦见这篇博文了，本来决定周日趁着还记得挺清楚直接写出来的，结果有事耽搁了，就一直拖到现在。周日早上我跟女朋友说做梦的事儿，她给了我一句评语，“你都快没生活情趣了，天天就想着这些东西。想着就算了，竟然还梦见了，天啊！”，哈哈。闲话少续，说说正经的。

—————————————————正式开始的分割线—————————————————-

上周在刘未鹏老大的TopLanguage(很遗憾，google groups被墙了，请翻墙查看该链接)里看到个讨论，似乎是说C++最佳面试题的，题目是“在类的成员函数中能不能调用delete this？”。由于我这个人忘性太大(上周五在toplanguage里潜水一下午看讨论，今天就忘光了)，把现在能想起来的部分内容记在这里。

在类的成员函数中能不能调用delete this？答案是肯定的，能调用，而且很多老一点的库都有这种代码。假设这个成员函数名字叫release，而delete this就在这个release方法中被调用，那么这个对象在调用release方法后，还能进行其他操作，如调用该对象的其他方法么？答案仍然是肯定的，调用release之后还能调用其他的方法，但是有个前提：被调用的方法不涉及这个对象的数据成员和虚函数。说到这里，相信大家都能明白为什么会这样了。

根本原因在于delete操作符的功能和类对象的内存模型。当一个类对象声明时，系统会为其分配内存空间。在类对象的内存空间中，只有数据成员和虚函数表指针，并不包含代码内容，类的成员函数单独放在代码段中。在调用成员函数时，隐含传递一个this指针，让成员函数知道当前是哪个对象在调用它。当调用delete this时，类对象的内存空间被释放。在delete this之后进行的其他任何函数调用，只要不涉及到this指针的内容，都能够正常运行。一旦涉及到this指针，如操作数据成员，调用虚函数等，就会出现不可预期的问题。

为什么是不可预期的问题？delete this之后不是释放了类对象的内存空间了么，那么这段内存应该已经还给系统，不再属于这个进程。照这个逻辑来看，应该发生指针错误，无访问权限之类的令系统崩溃的问题才对啊？这个问题牵涉到操作系统的内存管理策略。delete this释放了类对象的内存空间，但是内存空间却并不是马上被回收到系统中，可能是缓冲或者其他什么原因，导致这段内存空间暂时并没有被系统收回。此时这段内存是可以访问的，你可以加上100，加上200，但是其中的值却是不确定的。当你获取数据成员，可能得到的是一串很长的未初始化的随机数；访问虚函数表，指针无效的可能性非常高，造成系统崩溃。

Read the rest of this entry »

今天要说的是个经典的排序问题，从《编程珠玑》上看来的，题目是这样的：

输入：一个文件中存储着不超过10,000,000个正整数，且每个数都小于10,000,000。这些正整数不会
重复，而且相互独立，之间不存在关联关系。

输出：完成排序的正整数列表。

要求：时间复杂度和空间复杂度尽量低。

首先想到的是归并排序(百度百科的解释在这里)，但由于归并要保存中间过程产生的有序数据列表，结合庞大的数据量，空间的消耗过大。

排除！

然后再来看常用的快速排序(百度百科的解释在这里)，快速排序不需要记录中间数据，但是快排是一种多趟程序，会频繁的读取文件(或者将全部数据读入内存，那就会存在和归并排序一样的缺点)，效率低。

再排除。

看看理想的算法流程应该像下面这样。

从这个理想图可以看出来，现在的问题归结为如何才能一次性的把这不超过10,000,000个正整数读入到内存中。

好了，现在我们正式介绍一下题目中的名词：位向量。所谓位向量就是由一些二进制位组成的向量。我们可以用位向量来表示一个数组，例如数组

{1,2,3,5,8,13}

可以表示成

{0,1,1,1,0,1,0,0,1,0,0,0,0,1}

索引值等于原数组中元素的位为1，否则为0。

这种表示法是有前提的

1) 数组中都是非负整数；

2) 数组中不存在重复的数;

3) 数组所有元素小于某个特定值。

具体来说就是，可以用20位来表示一个所有元素为非负整数，值各不相同且最大值不超过20的数组。

换句话说，在满足条件的情况下，这种表示法可以用一个bit表示一个正整数，那一次性读入10,000,000个正整数也就不成问题。我们的理想算法也就呼之欲出了，下面是步骤：

第一步，初始化这个比特位集合中的所有位为0

for i = [0,  10,000,000)

    bit[i] = 0

第二步，读入待排序的正整数

for each i in the input file

    bit[i] = 1

第三步，输出排序结果

for i = [0, 10,000,000)

    if bit[i] == 1

       write i on the output file

这三步即完成整个排序过程。怎么样，代码是不是简洁而高效？

再想想还有什么问题没有？对，问题是C++中并没有二进制位的数据类型。别担心，通过C++提供的位操作，我们仍然能够实现位向量表示法。代码实现如下：

const int bitsPerWord = 32;//int型为32位
const int shift = 5;       //2的5次方
const int mask = 0x1F;     //模数
const int n = 10000000;
static int a[1 + n / bitsPerWord];

void set(int i)
{
    a[i >> shift] |= (1 << (i & mask));
}
void clr(int i)
{
    a[i >> shift] &= ~(1 << (i & mask));
}
int test(int i)
{
    return a[i >> shift] & (1 << (i & mask));
}

如果你看不懂位操作，没关系，我也刚搞懂，下面是我加的一些注释，希望能有点帮助。

Read the rest of this entry »

从收藏夹里翻出个放了很久的帖子，内容是关于类对象中的虚函数指针和虚函数表的。想看具体内容请猛击这里。

根据帖子内容和自己的认识，总结以下几点：

1、虚函数表指针位于类对象内存模型中的最前端，也就是说，一个类对象在内存中的地址范围内，前4个字节存放的是虚函数表的首地址，可以通过这个首地址访问到虚函数表。在上面的帖子里的第一个示例中，虚函数表的首地址就是：(int*)(*(int *) &b)；

2、虚函数表中存放的是类对象的虚成员函数的首地址。虚函数表中的每一项又是一个指针，指向的是该虚成员函数的首地址，所以，可以通过虚函数表调用虚成员函数。还是上面帖子里的第一个例子，调用第一个虚成员函数的语句：

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

其中，(int*)*(int*)(&b)就是虚函数表的第一项的地址。反引用之后，*((int*)*(int*)(&b))得到的就是第一个虚成员函数的首地址。将其强制转换后赋给函数指针pFun，此时，pFun指向的就是第一个虚成员函数的首地址，所以pFun()能够调用到Base::f。

3、在无虚函数覆盖的继承关系中，“虚函数按照其声明顺序放于表中”，并且“父类的虚函数在子类的虚函数前面”。

4、在有虚函数覆盖的继承关系中，子类中的函数覆盖掉父类的虚函数，覆盖的虚函数放到了虚函数表中父类被覆盖虚函数的位置，而“没有被覆盖的函数依旧”。这样的虚函数表结构，在实际调用过程中形成了多态。

5、对于多重继承，在子类的内存模型中，“每个父类都有自己的虚表”，“子类的成员函数被放到了第一个父类的表中”，其中“所谓的第一个父类是按照声明顺序来判断的”。

6、存在覆盖的多重继承中，子类的覆盖函数将取代其覆盖掉的父类的虚函数在虚函数表中的位置。

其实想起来去看虚函数表相关内容是因为在《高质量程序设计指南-C++/C》上看到一句话：在C++动态决议的虚拟机制中使用的vtable就是一个用来保存虚成员函数的地址的函数指针数组。看完虚函数表相关内容之后，稍微调整帖子里第一个例子的代码：
Read the rest of this entry »