C 語言有哪些復用數據結構的方法?
就像 C++ 的模板,在 C 中怎麼實現?難道要一個類型寫一份代碼?
__typeof__ 是很好用, 給一個泛型動態數組的例子:
#pragma once
#include &
#include &
#define DA_(ElemType) struct {size_t size; size_t cap; ElemType* data;}
#define DA_INIT(da) do {
__typeof__(da) _da_DA_INIT = (da);
_da_DA_INIT-&>size = 0;
_da_DA_INIT-&>cap = 8;
_da_DA_INIT-&>data = malloc(sizeof(__typeof__(_da_DA_INIT-&>data)) * 8);
} while(0)
#define DA_CLEANUP(da) do {
__typeof__(da) _da_DA_CLEANUP = (da);
_da_DA_CLEANUP-&>size = 0;
_da_DA_CLEANUP-&>cap = 0;
free(_da_DA_CLEANUP-&>data);
_da_DA_CLEANUP-&>data = NULL;
} while(0)
#define DA_PUSH(da, e) do {
__typeof__(da) _da_DA_PUSH = (da);
if (_da_DA_PUSH-&>size == _da_DA_PUSH-&>cap) {
_da_DA_PUSH-&>cap *= 2;
_da_DA_PUSH-&>data = realloc(_da_DA_PUSH-&>data, sizeof(__typeof__(e)) * _da_DA_PUSH-&>cap);
}
_da_DA_PUSH-&>data[_da_DA_PUSH-&>size++] = *e;
} while(0)
#define DA_SIZE(da) ((da)-&>size)
#define DA_AT(da) ({
__typeof__(da) _da_DA_AT = (da);
assert(_da_DA_AT-&>size &> i);
_da_DA_AT-&>data + i;
})
使用例:
DA_(int) da;
DA_INIT(da); // 初始化堆內存
DA_PUSH(da, 3);
DA_PUSH(da, "foo"); // 出錯, 編譯器會檢查類型
DA_CLEANUP(da); // 釋放堆內存
(編輯修改: __typeof__ 是 GCC 和 Clang 的擴展, 並不是標準的一部分)
另一種方法不用 __typeof__, 就是很長很長的宏了... 可以用靜態結構體保存泛型參數信息 (當泛型參數不僅僅是類型, 還有函數之類的時候適用). 用起來也 happy, 同樣以泛型動態數組為例:
#pragma once
#include &
#include &
#define DA_(DAType, ElemType)
struct DAType {size_t size; size_t cap; ElemType* data;};
static void DAType##_DA_init(struct DAType* da) {
da-&>size = 0;
da-&>cap = 8;
da-&>data = malloc(sizeof(ElemType) * 8);
}
static void DAType##_DA_cleanup(struct DAType* da) {
da-&>size = 0;
da-&>cap = 0;
free(da-&>data);
da-&>data = NULL;
}
static void DAType##_DA_push(struct DAType* da, ElemType e) {
if (da-&>size == da-&>cap) {
da-&>cap *= 2;
da-&>data = realloc(da-&>data, sizeof(ElemType) * da-&>cap);
}
da-&>data[da-&>size++] = e;
}
static size_t DAType##_DA_size(struct DAType* da) {
return da-&>size;
}
static ElemType* DAType##_DA_at(struct DAType* da, size_t i) {
assert(da-&>size &> i);
return da-&>data + i;
}
static struct {
void (*init)(struct DAType*);
void (*cleanup)(struct DAType*);
void (*push)(struct DAType*, ElemType);
size_t (*size)(struct DAType*);
ElemType* (*at)(struct DAType*, size_t);
} const DAType = {
.init = DAType##_DA_init,
.cleanup = DAType##_DA_cleanup,
.push = DAType##_DA_push,
.size = DAType##_DA_size,
.at = DAType##_DA_at
};
用起來就像這樣
DA_(IntArray, int);
...
struct IntArray d;
IntArray.init(d);
IntArray.push(d, 4);
IntArray.size(d);
IntArray.at(d, 0);
IntArray.cleanup(d);
第一種方法,用宏給每個類型展開一份實現(不推薦)第二種方法,用void*通用指針,元素用堆內存保存——參考libcstl的實現第三種方法,具體參考linux內核裡面各種數據結構的實現,需要gcc的typeof擴展,我還沒仔細研究過,看上去不是很美觀
我找到的一些資料:
1. OOC(Object-Oriented C)
oop - Can you write object oriented code in C?http://www.cs.rit.edu/~ats/books/ooc.pdf還有一些庫實現:http://ooc-coding.sourceforge.net/甚至語言(ooc language,提供了一個叫做 rock 的編譯器):https://ooc-lang.org/2.就是前面回答的知友提到的用 void * 類型的指針來實現泛型。這也有一些例子:
nanomsg 實現的 list,queue 等數據結構:nanomsg/src/utils at master · nanomsg/nanomsg · GitHub12 年的時候,在 C語言吧 看到一個帖子,用的也是這種方法:
【 C 語言吧 · 編寫xx管理系統必看,內有指導教程】_c語言吧3. 效仿 CPython 的做法
看看 CPython 是如何用 C 這樣不那麼面向對象的語言來構建 Python 這樣一門面向對象編程語言的。比如,PyObject 是這樣定義的:cpython/object.h at master · python/cpython · GitHub然後,PyDictObject 是這樣定義的:cpython/dictobject.h at master · python/cpython · GitHub由於 PyDictObject 和 PyObject 具有相同的結構體頭部,看起來就像是 PyDictObject 繼承自 PyObject 一樣。此外,PyDictObject * 轉換為 PyObject * 也變得合理了。具體可以讀一下《Python 源碼剖析》
4. Glib
GLibC Analog To STL根據 wikipedia,glib 中實現了這些數據結構:鏈表、哈希表、字元串、二叉樹、動態數組等等。5. c-algorithmshttps://github.com/fragglet/c-algorithms---關於如何OO以及如何擴充數據就不說了,方法已經被普遍使用。主要面臨的問題是如何在復用代碼中獲得客戶擴展數據類型,所以很多人會想到type of。我想說的是如果有c99 compound literal的支持,輔以宏,可以實現幾乎完整范型那套東,以及在編譯器優化給力的情況下,不輸於c++的性能。參見之前我的有關回答http://www.zhihu.com/question/26717742/answer/33785456
你是說復用常見容器和演算法么?klib是純c打造,宏製作。優點,速度快。缺點,跟模板一樣不好調試,不好理解。
把模板寫在一個單獨的文件里,通過#define + #include那個文件的方式生成各個模板的實例
void指針和函數指針(例如標準庫里的qsort)
推薦閱讀: