随笔-103  评论-224  文章-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 春秋十二月 阅读(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
 3int 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函数,对应的也有两个版本实现,如下所示
 1template<class _RandIt>
 2void 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(*< pivot) ++i;
13        while(pivot < *j) --j;
14        if (!(i < j)) break;
15        std::iter_swap(i,j);
16        
17        if (!(*< pivot) && !(pivot < *i)) 
18            std::iter_swap(p++,i);
19        if (!(*< 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
32template<class _RandIt,class _Compare>
33void 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)编辑 收藏
仅列出标题
共11页: First 3 4 5 6 7 8 9 10 11