C 語言中實現泛型

一般在寫 C 程序時用 typedef 將容器中元素的類型抽象，無法在同一個程序中用到兩種類型，而本文試圖在一個程序中用到兩種不同類型的容器，比如實現類似於 C++ 中的 vector 和 vector。核心技術是將元素類型定義為 void *，管它什麼類型，都用 void * 類型的指針指向真正的數據，與此同時，類型的大小是個重要信息，比如一般地，char 為1個字節，double 為 4 個字節。

本文以模仿 STL 中的 vector 類寫了一個 C 語言的 vector 結構體，為了體現封裝性，將 Vector 類型定義為 vector *，程序如下：

1、Vector 的接口

/********************************************************************
	created:	2014/02/07 22:24
	filename:	vector.h
	author:		Justme0 (http://blog.csdn.net/justme0)

	purpose:	Vector 的接口
*********************************************************************/
#ifndef vector_h__
#define vector_h__

typedef struct vector * Vector;
typedef void ** vec_iterator;

Vector vec_construct(int data_size);
void vec_destruct(Vector V);
int vec_size(Vector V);
vec_iterator vec_begin(Vector V);
vec_iterator vec_end(Vector V);
void vec_insert_n(Vector V, vec_iterator position, int n, void *pelem);
void vec_push_back(Vector V, void *pelem);

#endif // vector_h__

/********************************************************************
	created:	2014/02/07 22:25
	filename:	vector.c
	author:		Justme0 (http://blog.csdn.net/justme0)

	purpose:	Vector 的實現
*********************************************************************/
#include "vector.h"
#include 
#include 
#include 
#include 
#include 
#include 

typedef struct vector vector;
typedef void * vec_value_type;

struct vector {
	vec_iterator start;
	vec_iterator finish;
	vec_iterator end_of_storage;

	int elem_size;
};

/*
** data_size:容器中數據的類型的大小
*/
Vector vec_construct(int data_size) {
	Vector V = (vector *)malloc(sizeof(vector));
	if (NULL == V) {
		exit(OVERFLOW);
	}

	V->start = NULL;
	V->finish = NULL;
	V->end_of_storage = NULL;
	V->elem_size = data_size;

	return V;
}

void vec_destruct(Vector V) {
	vec_iterator ite;
	for (ite = V->start; ite != V->finish; ++ite) {
		free(*ite);
	}
	free(V->start);
	free(V);
}

vec_iterator vec_begin(Vector V) {
	return V->start;
}

vec_iterator vec_end(Vector V) {
	return V->finish;
}

int vec_size(Vector V) {
	return vec_end(V) - vec_begin(V);
}

void vec_insert_n(Vector V, vec_iterator position, int n, void *pelem) {
	int old_size = 0;
	int new_size = 0;
	int insert_index = 0;
	vec_iterator ite = NULL;	// 移動元素時的目的指針
	vec_iterator old_finish = NULL;

	if (0 == n) {
		return ;
	}

	insert_index = position - V->start;
	old_size = vec_size(V);
	new_size = old_size + n;

	// 先檢查剩余空間是否足夠，不夠則擴容
	if (V->end_of_storage - V->finish < n) {
		const int new_capacity = old_size + __max(old_size, n);
		vec_value_type *new_base = (vec_value_type *)realloc(V->start, new_capacity * sizeof(vec_value_type));
		if (NULL == new_base) {
			exit(OVERFLOW);
		}
		V->start = new_base;
		V->end_of_storage = V->start + new_capacity;
	}
	V->finish = V->start + new_size;
	old_finish = V->start + old_size;	// old_finish 所指空間可能不是原來的
	position = V->start + insert_index;

	// 移動元素
	// 源區間：[position, old_finish)
	// 目的區間：[position + n, old_finish + n)
	for (ite = old_finish + n - 1; ite >= position + n; --ite) {
		assert(V->start <= ite && ite < V->finish);
		assert(V->start <= ite - n && ite - n < V->finish);

		*ite = *(ite - n);
	}

	// 插入n個新元素至[position, position + n)
	for (; ite >= position; --ite) {
		*ite = malloc(V->elem_size);
		if (NULL == *ite) {
			exit(OVERFLOW);
		}

		memcpy(*ite, pelem, V->elem_size);
	}
}

void vec_push_back(Vector V, void *pelem) {
	vec_insert_n(V, vec_end(V), 1, pelem);
}

/********************************************************************
	created:	2014/01/27 11:46
	filename:	main.cpp
	author:		Justme0 (http://blog.csdn.net/justme0)

	purpose:	在C語言中用 void * 實現泛型（測試程序）
*********************************************************************/

#include 
#include "vector.h"

/*
** 輸出 char 類型
*/
void output_c(Vector V) {
	vec_iterator iter;
	for (iter = vec_begin(V); iter != vec_end(V); ++iter) {
		printf("%c\n", *(char *)*iter);	// 輸出時注意 iter 的真正類型是 void **
	}
}

/*
** 輸出 double 類型
*/
void output_d(Vector V) {
	vec_iterator iter;
	for (iter = vec_begin(V); iter != vec_end(V); ++iter) {
		printf("%.2f\n", *(double *)*iter);	// 輸出時注意 iter 的真正類型是 void **
	}
}

/*
** 測試 char 類型
*/
void test1() {
	char ch = 'A';
	int cnt = 5;

	Vector my_vec = vec_construct(sizeof(char));

	while (cnt--) {
		vec_push_back(my_vec, &ch);
		++ch;
	}
	output_c(my_vec);

	printf("size is %d\n", vec_size(my_vec));

	vec_destruct(my_vec);
}

/*
** 測試 double 類型
*/
void test2() {
	double d = 3.142;
	int cnt = 13;

	Vector my_vec = vec_construct(sizeof(double));

	while (cnt--) {
		vec_push_back(my_vec, &d);
		++d;
	}
	output_d(my_vec);

	printf("size is %d\n", vec_size(my_vec));

	vec_destruct(my_vec);
}

int main(int argc, char **argv) {
	test1();
	printf("\n");
	test2();

	return 0;
}

4、運行結果

A
B
C
D
E
size is 5

3.14
4.14
5.14
6.14
7.14
8.14
9.14
10.14
11.14
12.14
13.14
14.14
15.14
size is 13
請按任意鍵繼續. . .