C語言實作通用資料結構的高效設計

  近期在閱讀一個開源的C++代碼。裡面用到了大量的STL裡面的東西。或許是自己一直用C而非常少用C++來實作算法的原因。STL裡面大量的模闆令人心煩。一直對STL的效率表示懷疑，但在網上搜到這樣一個文章，說C的标準庫裡面高速排序比STL的标準排序要慢！于是，便認真的看了下二者的源代碼，發現C++裡面的std::sort綜合運用了部分高速排序和堆排序算法，而C标準庫裡面用的是通用資料結構的高速排序，C标準庫裡面的qsort之是以比std::sort慢。是由于C語言中為了适配全部的資料結構使用了空指針。以下以更為簡單的插入排序為例說明這個問題。

插入排序的算法實作代碼：

        上述插入排序的實作僅僅能針對整數類型進行排序，假設資料類型是浮點型。則要自己又一次把代碼拷貝一份。而且更改函數名以及資料類型。

假設是雙精度的，又或者是對自己定義的結構體數組進行排序呢？ 顯然，這不是一種非常好的解決方式。 而用空指針能夠解決問題。

通用資料類型的插入排序實作代碼：

        上述通用插入排序的實作有一個限制。就是待排序數組裡面每個元素的大小不能超過4k，當然對于簡單的系統提前定義好的資料類型，數組元素的大小最大為double，僅僅有8個位元組，這是遠遠的足夠用的。假設你自己定義的結構體的大小太大，比如大于這裡設定的4K，則沒有必要用此方法排序，由于此時資料移動會占用大部分時間，此時應該考慮用索引排序的方法。

       上面的方法盡管攻克了随意資料類型的問題，可是其效率并不怎麼高。相對于上述第一段代碼而言，簡單的指派語句必須得調用一個函數來拷貝資料。簡單的比較語句，則須要調用外部傳入一個函數指針得到比較結果。

這是效率低下的根本原因。

       而C++模闆參數的出現，僅僅須要寫一份代碼，編譯器依據你調用時候的資料類型自己主動生成新的代碼。其有用宏也能夠完畢通用的功能。這裡給出C語言宏的代碼。C++模闆的代碼也非常easy。

上面的宏定義能夠看做是一種模闆定義，能夠用于随意資料類型。

假設你要對整數進行排序。非常easy，用以下的兩個宏。一個宏定義比較運算。一個宏為函數定義：

這樣就有一個用于整數排序的函數insert_sort_int可用，假設是你自己定義的結構體類型，則相同僅僅須要寫這兩個宏就能夠了。

結尾：

用C++模闆産生的代碼大小是不使用模闆的非常多倍，而用C語言的空指針能夠支援随意資料類型，代碼大小非常小，而用C語言的宏定義産生模闆函數的代碼大小理論上和使用STL的大小是一樣的。

經過本人測試。随便一個特定資料結構的高速排序遞歸實作，都比c++ stl裡面的std::sort要快。

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5126167.html，如需轉載請自行聯系原作者