导读:阅读文本你将能够了解到C标准库对快速排序的支持、简单的索引技术、thunk技术的原理以及应用、C++虚函数调用以及接口多重继承实现、动态库中函数调用的实现原理、以及在各操作系统平台上的thunk实现方法、内存映射文件技术。
C语言的标准库<stdlib.h>中提供了一个用于快速排序的函数qsort,函数的签名如下:
/*
@note: 实现快速排序功能
@param: base 要排序的数组指针
@param: nmemb 数组中元素的个数
@param: size 数组中每个元素的size
@param: compar 排序元素比较函数指针, 用于比较两个元素。返回值分别为-1, 0, 1。
*/
void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));
这个函数要求提供一个排序的数组指针base, 数组的元素个数nmemb, 数组中每个元素的尺寸size,以及一个排序的比较器函数compar四个参数。下面的例子演示了这个函数的使用方法:
#include <stdlib.h>
typedef struct
{
int age;
char *name;
}student_t;
//按年龄升序排序的比较器函数
int agecomparfn(const student_t *s1, const student_t *s2)
{
return s1->age - s2->age;
}
int main(int argc, const char * argv[])
{
student_t students[] = {{20,"Tom"},{15,"Jack"},{30,"Bob"},{10,"Lily"},{30,"Joe"}};
size_t count = sizeof(students)/sizeof(student_t);
qsort(students, count, sizeof(student_t), &agecomparfn);
for (size_t i = 0; i < count; i++)
{
printf("student:[age:%d, name:%s]\n", students[i].age, students[i].name);
}
return 0;
}
函数排序后会将students中元素的内存存储顺序打乱。如果需求变为在不将students中的元素打乱情况下,仍希望按age的大小进行排序输出显示呢?为了解决这个问题可以为students数组建立一个索引数组,然后对索引数组进行排序即可。因为打乱的是索引数组中的顺序,而访问元素时又可以通过索引数组来间接访问,这样就可以实现原始数据内存存储顺序不改变的情况下进行有序输出。代码实现改为如下:
#include <stdlib.h>
typedef struct
{
int age;
char *name;
}student_t;
student_t students[] = {{20,"Tom"},{15,"Jack"},{30,"Bob"},{10,"Lily"},{30,"Joe"}};
size_t count = sizeof(students)/sizeof(student_t);
//按年龄升序索引排序的比较器函数
int ageidxcomparfn(const int *idx1ptr, const int *idx2ptr)
{
return students[*idx1ptr].age - students[*idx2ptr].age;
}
int main(int argc, const char * argv[])
{
//创建一个索引数组
int idxs[] = {0,1,2,3,4};
qsort(idxs, count, sizeof(int), &ageidxcomparfn);
for (size_t i = 0; i < count; i++)
{
//通过索引间接引用
printf("student[age:%d, name:%s]\n", students[idxs[i]].age, students[idxs[i]].name);
}
return 0;
}
从上面的代码中可以看出,排序时不再是对students数组进行排序了,而是对索引数组idxs进行排序了。同时在访问students中的元素时也不再直接通过下标访问,而是通过索引数组的下标来进行间接访问了。
索引技术是一种非常实用的技术,尤其是在数据库系统上应用最广泛,因为原始记录存储成本和文件IO的原因,移动索引中的数据要比移动原始记录数据要快而且方便很多,而且性能上也会大大的提升。当大量数据存储在内存中也是如此,数据记录在内存中因为排序而进行位置的移动要比索引数组元素移动的开销和成本大很多,而且如果涉及到多线程下要对不同的成员进行原始记录的排序时还需要引入锁的机制。 因此在实践中对于那些大数据块进行排序时,改为通过引入索引来进行间接排序将会使你的程序性能得到质的提高。
对比上面两个排序的实例代码实现就会发现通过索引进行排序时不得不将students数组从一个局部变量转化为一个全局变量了,原因是由于排序比较器函数compar的定义限制导致的。因为排序的对象从students变为idxs了,而排序比较器函数ageidxcomparfn的两个入参变为索引值的int类型的指针,如果不将students数组设置为全局变量那么比较器函数内部是无法访问students中的元素的,所以只能将students定义为一个全局数组。很明显这种解决方案是非常不友好而且无法进行扩展的,同一个比较器函数无法实现对不同的students数组进行排序。为了支持这种需要带扩展参数的间接排序,很多平台都提供了一个相应的非标准库扩充函数(比如Windows下的qsort_s, iOS/macOS的qsort_r, qsort_b等)。下面是采用iOS系统下的qsort_r函数来解决上述问题的代码: