一年十二月谁主春秋

摘要: 主类模板 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 春秋十二月阅读(4425) | 评论 (1) | 编辑收藏

模板元编程（3）：类型选择

摘要: 类型选择是一种编译时的类型计算技术，也就是根据条件判断来匹配对应的类型，功能形如运行时的if else和switch case控制结构。在这里仿真运行时的条件语句，实现了类型选择，包括if单分支、if多分支和switch case三种结构，关于其原理及细节就不多讲了，直接看如下代码（1）if单分支 Code ... 阅读全文

posted @ 2012-06-06 13:49 春秋十二月阅读(1910) | 评论 (1) | 编辑收藏

基于特定小范围关键字的原位统计排序

摘要: 基本原理在数据输入随机分布的情况下，快速排序具有较好的性能表现，但当元素个数比其关键字的取值范围大，而这个范围相对较小时，使用一种关键字索引统计排序会快很多，因为它的时间复杂度是线性的，基本原理是使用数组（为描述方便，特称统计数组），其下标对应关键字的值，存储元素按待排序关键字的值统计的出现次数，然后再按元素关键字的值，结合统计数组，放回到最终位置上。常规的实现... 阅读全文

posted @ 2012-05-31 12:11 春秋十二月阅读(1734) | 评论 (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生成。

#define LOKI_TYPELIST_METHOD_DEF(name)\
2

template <class TList>\
3

struct name;\
4

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）。

#define LOKI_TYPELIST_SIZE_SPEC_DEF0(name)\
2

template<>\
3

struct name##Size<NullType>\
4

{\
5

enum { value = 0 };\
6

};\
7

#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

#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

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

#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）。

#define LOKI_TYPELIST_TYPE_SPEC_DEF0(name)\
2

template<>\
3

struct name##Type<NullType>\
4

{\
5

typedef NullType type;\
6

};\
7

#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

#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

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

#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宏来做编译期诊断结果正确性。

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

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

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

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

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

return 0;
18

}

posted @ 2012-05-29 01:03 春秋十二月阅读(1747) | 评论 (2) | 编辑收藏

三路划分快速排序--针对重复关键字的改进

基本原理
   快速排序算法是一种分治排序算法，影响其性能的因素有划分元素的选择、小的子文件的处理、重复关键字等，本文论述针对重复关键字的改进实现。首先来回顾下一般的算法实现，其流程如下：
   a. 选择一个划分元素，这个元素在划分后将在最终的位置上，通常是选择最右端元素作为划分点。
   b. 从左端开始扫描，直到找到大于划分元素的元素；同时从右端开始扫描，直到找到小于划分元素的元素，再交换使扫描停止的这两个元素。
   c. 继续步骤b，直到左指针不小于右指针，最后再交换左指针元素和划分元素。
   d. 在左指针左侧和右侧区间(区间不包括左指针元素)重复以上过程，直至元素个数为0或1。
   在划分的过程中，位于左指针左侧的元素都比划分元素小，右侧的元素都比划分元素大，如下图所示

   由上述可见，一般的算法实现针对大量重复关键字的输入情况，其性能表现很差，例如如果一个文件完全由相等的值(只有一个值)组成，那么它就不需要再进行任何排序，但前面的算法依然划分直至得到小的子文件，无论文件有多大。针对这一情况，可以作实质性的改进，从而避免处理元素相同的子区间，提高效率。改进的算法实现主要问题在于如何处理与划分元素相等的情况，这里的基本思想是将区间划分为三个部分，左部分小于划分元素，中间部分等于划分元素，右部分大于划分元素，然后再在左右两部分进行子处理，具体的流程如下：
   a'. 选择左端元素、中间元素和右端元素的中值作为划分元素，也就是三者取中划分，这样能有效避免划分区间的最坏情况。
   b'. 从左端开始扫描，直到找到不小于划分元素的元素；同时从右端开始扫描，直到找到不大于划分元素的元素，再交换使扫描停止的这两个元素。如果左指针元素等于划分元素，那么与左端的元素交换，并递增左端位置(初始化为文件最左位置)；如果右指针元素等于划分元素，那么与右端元素交换，并递减右端位置(初始化为文件最右位置)。
   c'. 继续步骤b'，直到左指针不小于右指针。
   d'. 交换最左端区间和左指针左侧区间(不包括左指针元素)，这一过程会递减左端位置；交换最右端区间和左指针右侧区间(包括左指针元素)，这一过程会递增右端位置。
   e'. 在最左端和最右端区间重复以上过程，直至元素个数为0或1。
   在划分的过程中，与划分元素相等的元素分布在最左端和最右端，如下图所示

在划分完成后处理子文件前，需要对调区间，如步骤d'所述，结果如下图所示

代码实现
上面所有图中的v代表划分元素，最后列出代码清单，函数quick_sort有两个版本，一个是支持operator < 的默认实现，另一个是支持带谓词的自定义比较实现。在其中用到了实现三者取中值的__median函数，对应的也有两个版本实现，如下所示

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

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

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

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

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

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

quick_sort(_first,j+1);
29

quick_sort(i,_last);
30

}
31

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

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

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

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

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

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 春秋十二月阅读(2504) | 评论 (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 春秋十二月阅读(2830) | 评论 (2) | 编辑收藏

真彩色静态框CColorStatic类的设计实现

摘要: 关于cstatic控件的自绘，网上也有很多的代码及文章，更有其界面画得很漂亮的、多种多样的功能。近来我自行封装实现了一个真彩色静态框类，目标初衷是从颜色、字体、光标入手，改变原始标准cstatic的色彩风格，使界面初步美化，具有好看的效果。同时作为一个基础简单的类来维护，为后续的功能增强及美化提供参考扩展，这个CColorStatic类的特点及功能如下：（1）文... 阅读全文

posted @ 2011-12-18 00:54 春秋十二月阅读(3501) | 评论 (1) | 编辑收藏

使用子类化截获窗口消息

摘要: 在《多标签视图类CTabView的设计实现》一文中，CTabView从CBasicSubClassWnd私有继承，重写其虚函数SubWindowProc，捕获WM_DRAWITEM和TTN_GETDISPINFO消息，从而实现了DrawItem和UpdateTooltipText虚函数回调机制，支持派生类的自定义处理，而CBasicSubClassWnd就是一个... 阅读全文

posted @ 2011-12-11 11:07 春秋十二月阅读(2141) | 评论 (0) | 编辑收藏

多标签视图类CTabView的设计实现

摘要: 在MFC9（在vc2008和vc2010中，已经有了CTabView的现成类）以前的版本中，有CListView,CTreeView,CEditView,CRichEditView等控件视图类，但就是没有类似的CTabView类，因工作需要，最近在做一个简单的多标签IE浏览器，开发环境是vs2005，基本框架是sdi + chtmlview + ctabview... 阅读全文

posted @ 2011-12-11 00:47 春秋十二月阅读(4682) | 评论 (3) | 编辑收藏

观察者模式之应用: 系统托盘图标类的设计

摘要: 关于系统托盘图标类，网上也有很多的代码，但都不太简洁灵活易用，为了这一目的，本人自行封装了一个API版本的实现类，这个类的设计思想来源于观察者模式，从而较好地解耦了托盘通知消息的发送、接收、处理这三者间的关系，使这三者可以是同一个对象，也可以是不同的对象，具体的情况可根据业务逻辑灵活选择控制，主要包括以下几方面的特点：1）对于托盘通知消息的接收处理，提供了一个默... 阅读全文

posted @ 2011-12-04 03:15 春秋十二月阅读(1823) | 评论 (0) | 编辑收藏

仅列出标题

常用链接

留言簿(28)

随笔分类(102)

随笔档案(103)

文章分类(30)

关注的开源项目

技术联盟

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜