摘要: 主类模板
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) |
编辑 收藏
摘要: 类型选择是一种编译时的类型计算技术,也就是根据条件判断来匹配对应的类型,功能形如运行时的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) |
编辑 收藏
本文就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 春秋十二月 阅读(1747) |
评论 (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 春秋十二月 阅读(2504) |
评论 (1) |
编辑 收藏
摘要: 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) |
编辑 收藏
摘要: 关于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) |
编辑 收藏
摘要: 在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) |
编辑 收藏