隨筆-163 評論-223 文章-30 trackbacks-0

摘要: 主類模板 gcc從4.1.2版本開始提供了__sync_*系列的內置API，用于加減和邏輯運算，可以對1，2，4，8字節長度的數值或指針類型進行原子操作，為方便使用，筆者對這些API作了簡單的封裝。 Code highlighting produced by Actipro CodeHighlighter (freeware) http://... 閱讀全文

posted @ 2012-06-08 00:19 春秋十二月閱讀(4595) | 評論 (1) | 編輯收藏

模板元編程（3）：類型選擇

摘要: 類型選擇是一種編譯時的類型計算技術，也就是根據條件判斷來匹配對應的類型，功能形如運行時的if else和switch case控制結構。在這里仿真運行時的條件語句，實現了類型選擇，包括if單分支、if多分支和switch case三種結構，關于其原理及細節就不多講了，直接看如下代碼（1）if單分支 Code ... 閱讀全文

posted @ 2012-06-06 13:49 春秋十二月閱讀(2089) | 評論 (1) | 編輯收藏

基于特定小范圍關鍵字的原位統計排序

摘要: 基本原理在數據輸入隨機分布的情況下，快速排序具有較好的性能表現，但當元素個數比其關鍵字的取值范圍大，而這個范圍相對較小時，使用一種關鍵字索引統計排序會快很多，因為它的時間復雜度是線性的，基本原理是使用數組（為描述方便，特稱統計數組），其下標對應關鍵字的值，存儲元素按待排序關鍵字的值統計的出現次數，然后再按元素關鍵字的值，結合統計數組，放回到最終位置上。常規的實現... 閱讀全文

posted @ 2012-05-31 12:11 春秋十二月閱讀(1820) | 評論 (0) | 編輯收藏

模板元編程（2）：計算最值

本文就Loki編譯期技術中的類型列表Typelist作了一些擴展，增加了以下幾個方法：
• 獲取最大和最小長度，即求取Typelist中長度最大和最小的值
• 獲取最大和最小類型，即求取Typelist中長度最大和最小的類型

實現
   位于Loki::TL命名空間，利用遞歸計算最值結果，使用宏生成主類模板和特化類模板，其中后綴為DEFN(N為正整數)形式的宏中N表示特化類模板所帶的模板參數數量，使用DEF1宏定義對應的特化類模板的原因在于：當Typelist中存在非NullType類型時，保證結果的正確性。當N為2時參數取值：name為Max則b為true；name為Min則b為false。
   主類模板
   用于定義MaxSize、MinSize和MaxType、MinType主類模板，使用宏LOKI_TYPELIST_METHOD_DEF生成。

1

#define LOKI_TYPELIST_METHOD_DEF(name)\
2

template <class TList>\
3

struct name;\
4

5

LOKI_TYPELIST_METHOD_DEF(MaxSize)
6

LOKI_TYPELIST_METHOD_DEF(MinSize)
7

LOKI_TYPELIST_METHOD_DEF(MaxType)
8

LOKI_TYPELIST_METHOD_DEF(MinType)

最大(小)長度
對應類主模板分別為MaxSize和MinSize，每種有3個特化模板，使用宏LOKI_TYPELIST_SIZE_SPEC_DEFN生成（N為0、1、2）。

1

#define LOKI_TYPELIST_SIZE_SPEC_DEF0(name)\
2

template<>\
3

struct name##Size<NullType>\
4

{\
5

enum { value = 0 };\
6

};\
7

8

#define LOKI_TYPELIST_SIZE_SPEC_DEF1(name)\
9

template<class T>\
10

struct name##Size<Typelist<T,NullType> >\
11

{\
12

enum { value = sizeof(T) };\
13

};\
14

15

#define LOKI_TYPELIST_SIZE_SPEC_DEF2(name,b)\
16

template<class T,class U>\
17

struct name##Size<Typelist<T,U> >\
18

{\
19

enum { tmp = name##Size<U>::value };\
20

enum { value = (b ? sizeof(T) > tmp : sizeof(T) < tmp) ? sizeof(T) : tmp };\
21

};\
22

23

LOKI_TYPELIST_SIZE_SPEC_DEF0(Max)
24

LOKI_TYPELIST_SIZE_SPEC_DEF0(Min)
25

LOKI_TYPELIST_SIZE_SPEC_DEF1(Max)
26

LOKI_TYPELIST_SIZE_SPEC_DEF1(Min)
27

LOKI_TYPELIST_SIZE_SPEC_DEF2(Max,true)
28

LOKI_TYPELIST_SIZE_SPEC_DEF2(Min,false)
29

30

#undef LOKI_TYPELIST_SIZE_SPEC_DEF0
31

#undef LOKI_TYPELIST_SIZE_SPEC_DEF1
32

#undef LOKI_TYPELIST_SIZE_SPEC_DEF2

最大(小)類型
對應類主模板分別為MaxType和MinType，每種有3個特化模板，使用宏LOKI_TYPELIST_TYPE_SPEC_DEFN生成（N為0、1、2）。

1

#define LOKI_TYPELIST_TYPE_SPEC_DEF0(name)\
2

template<>\
3

struct name##Type<NullType>\
4

{\
5

typedef NullType type;\
6

};\
7

8

#define LOKI_TYPELIST_TYPE_SPEC_DEF1(name)\
9

template<class T>\
10

struct name##Type<Typelist<T,NullType> >\
11

{\
12

typedef T type;\
13

};\
14

15

#define LOKI_TYPELIST_TYPE_SPEC_DEF2(name,b)\
16

template<class T,class U>\
17

struct name##Type<Typelist<T,U> >\
18

{\
19

typedef typename name##Type<U>::type R;\
20

typedef typename Select< b ? (sizeof(T)>sizeof(R)) : (sizeof(T)<sizeof(R)),T,R>::Result type;\
21

};\
22

23

LOKI_TYPELIST_TYPE_SPEC_DEF0(Max)
24

LOKI_TYPELIST_TYPE_SPEC_DEF0(Min)
25

LOKI_TYPELIST_TYPE_SPEC_DEF1(Max)
26

LOKI_TYPELIST_TYPE_SPEC_DEF1(Min)
27

LOKI_TYPELIST_TYPE_SPEC_DEF2(Max,true)
28

LOKI_TYPELIST_TYPE_SPEC_DEF2(Min,false)
29

30

#undef LOKI_TYPELIST_TYPE_SPEC_DEF0
31

#undef LOKI_TYPELIST_TYPE_SPEC_DEF1
32

#undef LOKI_TYPELIST_TYPE_SPEC_DEF2

這里用到了Loki中的Select組件來選擇類型。

示例
使用LOKI中的LOKI_STATIC_CHECK宏來做編譯期診斷結果正確性。

1

#define LOKI_TL4 LOKI_TYPELIST_4(double,int,short,char)
2

3

int main(int argc,char *argv[])
4

{
5

static const int max_val = Loki::TL::MaxSize<LOKI_TL4 >::value;
6

LOKI_STATIC_CHECK(max_val==sizeof(double),max_val_should_be_sizeof_double)
7

8

static const int min_val = Loki::TL::MinSize<LOKI_TL4 >::value;
9

LOKI_STATIC_CHECK(min_val==sizeof(char),min_val_should_be_sizeof_char)
10

11

typedef Loki::TL::MaxType<LOKI_TL4 >::type max_type;
12

LOKI_STATIC_CHECK((Loki::IsSameType<max_type,double>::value),max_type_should_be_double)
13

14

typedef Loki::TL::MinType<LOKI_TL4 >::type min_type;
15

LOKI_STATIC_CHECK((Loki::IsSameType<min_type,char>::value),min_type_should_be_char)
16

17

return 0;
18

}

posted @ 2012-05-29 01:03 春秋十二月閱讀(1922) | 評論 (2) | 編輯收藏

三路劃分快速排序--針對重復關鍵字的改進

基本原理
   快速排序算法是一種分治排序算法，影響其性能的因素有劃分元素的選擇、小的子文件的處理、重復關鍵字等，本文論述針對重復關鍵字的改進實現。首先來回顧下一般的算法實現，其流程如下：
   a. 選擇一個劃分元素，這個元素在劃分后將在最終的位置上，通常是選擇最右端元素作為劃分點。
   b. 從左端開始掃描，直到找到大于劃分元素的元素；同時從右端開始掃描，直到找到小于劃分元素的元素，再交換使掃描停止的這兩個元素。
   c. 繼續步驟b，直到左指針不小于右指針，最后再交換左指針元素和劃分元素。
   d. 在左指針左側和右側區間(區間不包括左指針元素)重復以上過程，直至元素個數為0或1。
   在劃分的過程中，位于左指針左側的元素都比劃分元素小，右側的元素都比劃分元素大，如下圖所示

   由上述可見，一般的算法實現針對大量重復關鍵字的輸入情況，其性能表現很差，例如如果一個文件完全由相等的值(只有一個值)組成，那么它就不需要再進行任何排序，但前面的算法依然劃分直至得到小的子文件，無論文件有多大。針對這一情況，可以作實質性的改進，從而避免處理元素相同的子區間，提高效率。改進的算法實現主要問題在于如何處理與劃分元素相等的情況，這里的基本思想是將區間劃分為三個部分，左部分小于劃分元素，中間部分等于劃分元素，右部分大于劃分元素，然后再在左右兩部分進行子處理，具體的流程如下：
   a'. 選擇左端元素、中間元素和右端元素的中值作為劃分元素，也就是三者取中劃分，這樣能有效避免劃分區間的最壞情況。
   b'. 從左端開始掃描，直到找到不小于劃分元素的元素；同時從右端開始掃描，直到找到不大于劃分元素的元素，再交換使掃描停止的這兩個元素。如果左指針元素等于劃分元素，那么與左端的元素交換，并遞增左端位置(初始化為文件最左位置)；如果右指針元素等于劃分元素，那么與右端元素交換，并遞減右端位置(初始化為文件最右位置)。
   c'. 繼續步驟b'，直到左指針不小于右指針。
   d'. 交換最左端區間和左指針左側區間(不包括左指針元素)，這一過程會遞減左端位置；交換最右端區間和左指針右側區間(包括左指針元素)，這一過程會遞增右端位置。
   e'. 在最左端和最右端區間重復以上過程，直至元素個數為0或1。
   在劃分的過程中，與劃分元素相等的元素分布在最左端和最右端，如下圖所示

在劃分完成后處理子文件前，需要對調區間，如步驟d'所述，結果如下圖所示

代碼實現
上面所有圖中的v代表劃分元素，最后列出代碼清單，函數quick_sort有兩個版本，一個是支持operator < 的默認實現，另一個是支持帶謂詞的自定義比較實現。在其中用到了實現三者取中值的__median函數，對應的也有兩個版本實現，如下所示

1

template<class _RandIt>
2

void quick_sort(_RandIt _first,_RandIt _last)
3

{
4

typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
5

if (!(_first<_last-1)) return;
6

7

_RandIt i = _first,j = _last-1,p = i,q = j,k;
8

_ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2));
9

10

while(true)
11

{
12

while(*i < pivot) ++i;
13

while(pivot < *j) --j;
14

if (!(i < j)) break;
15

std::iter_swap(i,j);
16

17

if (!(*i < pivot) && !(pivot < *i))
18

std::iter_swap(p++,i);
19

if (!(*j < pivot) && !(pivot < *j))
20

std::iter_swap(q--,j);
21

++i; --j;
22

}
23

24

j = i - 1;
25

for(k = _first;k<p;--j,++k) std::iter_swap(k,j);
26

for(k = _last-1;k>q;++i,--k) std::iter_swap(k,i);
27

28

quick_sort(_first,j+1);
29

quick_sort(i,_last);
30

}
31

32

template<class _RandIt,class _Compare>
33

void quick_sort(_RandIt _first,_RandIt _last,_Compare _comp)
34

{
35

typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
36

if (!(_first < _last - 1)) return;
37

38

_RandIt i = _first,j = _last-1,p = i, q = j, k;
39

_ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2),_comp);
40

41

while(true)
42

{
43

while(_comp(*i,pivot)) ++i;
44

while(_comp(pivot,*j)) --j;
45

if (!(i < j)) break;
46

std::iter_swap(i,j);
47

48

if (!_comp(*i,pivot) && !_comp(pivot,*i))
49

std::iter_swap(p++,i);
50

if (!_comp(*j,pivot) && !_comp(pivot,*j))
51

std::iter_swap(q--,j);
52

++i; --j;
53

}
54

j = i - 1;
55

for(k = _first;k < p;++k,--j)
56

std::iter_swap(k,j);
57

for(k = _last - 1;k > q;--k,++i)
58

std::iter_swap(k,i);
59

60

quick_sort(_first,j+1,_comp);
61

quick_sort(i,_last,_comp);
62

}

從上面實現可看出，與一般的實現相比，劃分過程多了兩個if及for循環，if測試用來將找到的重復元素放在左右兩端；for循環用來交換區間，將重復元素再放在中間，這額外的工作量只與找到的重復關鍵字的個數成線性，因此，即使在沒有重復關鍵字的情況下，它也運行得很好，平均時間復雜度為O(NlgN)。

posted @ 2012-05-19 14:48 春秋十二月閱讀(2730) | 評論 (1) | 編輯收藏

模板元編程（1）：選擇API

摘要: C與C++ API的比較在c語言中，API體現為c函數，如操作系統提供的一系列API，在c++中，API體現為自由函數，這里的自由函數是指除普通成員函數、靜態成員函數、友元函數外的能在某命名空間作用域或全局空間內直接訪問的函數，而這更多地體現為函數模板，如stl提供的一系列算法swap、count和sort等。相對于c API，c++ API具有類型安全和封... 閱讀全文

posted @ 2011-12-24 19:08 春秋十二月閱讀(2986) | 評論 (2) | 編輯收藏

真彩色靜態框CColorStatic類的設計實現

摘要: 關于cstatic控件的自繪，網上也有很多的代碼及文章，更有其界面畫得很漂亮的、多種多樣的功能。近來我自行封裝實現了一個真彩色靜態框類，目標初衷是從顏色、字體、光標入手，改變原始標準cstatic的色彩風格，使界面初步美化，具有好看的效果。同時作為一個基礎簡單的類來維護，為后續的功能增強及美化提供參考擴展，這個CColorStatic類的特點及功能如下：（1）文... 閱讀全文

posted @ 2011-12-18 00:54 春秋十二月閱讀(3784) | 評論 (1) | 編輯收藏

使用子類化截獲窗口消息

摘要: 在《多標簽視圖類CTabView的設計實現》一文中，CTabView從CBasicSubClassWnd私有繼承，重寫其虛函數SubWindowProc，捕獲WM_DRAWITEM和TTN_GETDISPINFO消息，從而實現了DrawItem和UpdateTooltipText虛函數回調機制，支持派生類的自定義處理，而CBasicSubClassWnd就是一個... 閱讀全文

posted @ 2011-12-11 11:07 春秋十二月閱讀(2323) | 評論 (0) | 編輯收藏

多標簽視圖類CTabView的設計實現

摘要: 在MFC9（在vc2008和vc2010中，已經有了CTabView的現成類）以前的版本中，有CListView,CTreeView,CEditView,CRichEditView等控件視圖類，但就是沒有類似的CTabView類，因工作需要，最近在做一個簡單的多標簽IE瀏覽器，開發環境是vs2005，基本框架是sdi + chtmlview + ctabview... 閱讀全文

posted @ 2011-12-11 00:47 春秋十二月閱讀(5317) | 評論 (3) | 編輯收藏

觀察者模式之應用: 系統托盤圖標類的設計

摘要: 關于系統托盤圖標類，網上也有很多的代碼，但都不太簡潔靈活易用，為了這一目的，本人自行封裝了一個API版本的實現類，這個類的設計思想來源于觀察者模式，從而較好地解耦了托盤通知消息的發送、接收、處理這三者間的關系，使這三者可以是同一個對象，也可以是不同的對象，具體的情況可根據業務邏輯靈活選擇控制，主要包括以下幾方面的特點：1）對于托盤通知消息的接收處理，提供了一個默... 閱讀全文

posted @ 2011-12-04 03:15 春秋十二月閱讀(1978) | 評論 (0) | 編輯收藏

僅列出標題

本博客所有隨筆均為原創，因為不定期維護更新，所以轉載請注明出處，如有問題和建議，請留言或評論，發表您的寶貴意見，藉此平臺以分享交流、共同進步。 聯系方式：微信math-engineer

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(80)

隨筆分類(162)

隨筆檔案(163)

文章分類(30)

詩詞作品集(30)

關注的開源項目

LLVM
編譯系統
nginx
高性能Web服務器
OpenSSL
密碼學庫
suricata
網絡IPS引擎

積分與排名

積分 - 422360
排名 - 55

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(80)

隨筆分類(162)

隨筆檔案(163)

文章分類(30)

關注的開源項目

最新隨筆

積分與排名

最新評論

閱讀排行榜

評論排行榜