随笔-99  评论-224  文章-30  trackbacks-0
 
     摘要:    在面向对象开发时,对实际问题分析进而抽象出一种类型,往往会考虑到2个方面:1)类型的内部成员和方法的定义描述 2)类型的多实例存取操作。其中第1点是类型本身数据结构的设计,第2点是类型容器数据结构的选择设计。在stl中,容器有序列式和关联式两种,前者代表有vector,list,deque等;后者代表有set,multiset,map,multimap等,对于一...  阅读全文
posted @ 2011-07-16 12:23 春秋十二月 阅读(1711) | 评论 (0)编辑 收藏
     摘要: 需求分析    在数据结构中,树有两种存储方式,一种是链式存储,另一种是顺序存储。前者就是使用指针来记录树结点间的关系,在新增结点或删除结点时,只需改变与父结点或兄弟结点的指针值即可,实现较为简单;后者就是使用数组来存储,可以用相对偏移量来记录树结点间的关系,在新增结点或删除结点时,则不仅是改变与父结点或兄弟结点的相对偏移量,还需要改变其它结点的相对偏移量,实现较为...  阅读全文
posted @ 2011-07-13 15:10 春秋十二月 阅读(3473) | 评论 (9)编辑 收藏
继承情景
   我们知道一个空的类,也就是其内部没有非静态数据成员,没有虚指针(包括指向虚函数表和虚基类子对象的指针),它的大小通常为1,当然在某些对齐要求严格系统上可能是另一个数(通常是4),如果空类被继承,那么派生类的大小会怎么样呢?一个支持C++标准和EBO的编译器对此会进行空基类的优化,也就是不给空的基类子对象分配空间,换句话说,空基类子对象的地址和其派生类实例的地址是相同的。从编译器实现的角度来看,需要考虑继承时的不同情况,下图中P表示父类,C表示子类,圆形表示空类,矩形表示非空类。单继承EBO情况如下图所示
   EBO-1反映的是空类派生自空基类,EBO-2反映的是非空类派生自空基类,EBO-3、EBO-4反映的是在继承链中,对空基类的优化能不能传递到后代中。多继承EBO如下图所示
   EBO-5反映的是空类派生自两个空基类,EBO-6反映的是非空类派生自两个空基类,EBO-6反映的是空类派生自一个非空基类和一个空基类,EBO-7反映的是非空类派生自一个非空基类和一个空基类。以上8种情况,不论是单继承还是多继承,一个完全支持EBO的编译器就应该能把空基类部分都优化掉。

优化应用
   由于空基类优化技术节省了对象不必要的空间,提高了运行效率,因此成为某些强大技术的基石,基于类型定义类如stl中的binary_function、unary_function、iterator、iterator_traits的实现复用;基于策略类如内存管理、多线程安全同步的实现复用。当某个类存在空类类型的数据成员时,也可考虑借助EBO优化对象布局,例如下
1template<typename T1,typename T2>
2class EBO
3{
4private:
5    T1 m_t1;
6    T2 m_t2;
7}
;
   当T1和T2为空类时,可以改进如下
1template<typename T1,typename T2>
2class EBO : T1, T2
3{
4}
;
   
   更进一步,如果T1或T2为非类类型,如基本内建类型、函数指针等;或T1和T2类型相同时,则直接继承它们会导致编译错误,怎么办呢?这时可以添加一个中间层来解决,代码如下
 1template<typename T1,typename T2,bool isSame,bool isFirstEmpty,bool isSecondEmpty>
 2class EBO_IMPL;
 3
 4template<typename T1,typename T2>
 5class EBO_IMPL<T1,T2,false,false,false>
 6{
 7    T1 m_t1;
 8    T2 m_t2;
 9}
;
10
11template<typename T1,typename T2>
12class EBO_IMPL<T1,T2,false,true,true> : T1,T2
13{
14}
;
15
16template<typename T1,typename T2>
17class EBO_IMPL<T1,T2,false,true,false> : T1
18{
19    T2 m_t2;
20}
;
21
22template<typename T1,typename T2>
23class EBO_IMPL<T1,T2,false,false,true> : T2
24{
25    T1 m_t1;
26}
;
27
28template<typename T1,typename T2>
29class EBO_IMPL<T1,T2,true,false,false>
30{
31    T1 m_t1;
32    T2 m_t2;
33}
;
34
35template<typename T1,typename T2>
36class EBO_IMPL<T1,T2,true,true,true> : T1
37{
38    T2 m_t2;
39}
;
40
41template<typename T1,typename T2>
42class EBO : EBO_IMPL<T1,T2,boost::is_same<T1,T2>::value,boost::is_empty<T1>::value,boost::is_empty<T2>::value>
43{
44}
;
   为了简便,直接使用了boost中的is_same,is_empty元函数来判断类型的属性,实际上boost中已经实现了EBO的选择运用工具即compressed_pair类模板,研究其源码可发现,该工具充分考虑到了T1和T2实际类型的各种情况,is_empty的判断是运用sizeof来比较类型大小确定的。替换compressed_pair后,代码如下
1template<typename T1,typename T2>
2class EBO: boost::compressed_pair<T1,T2>
3{
4}
;
posted @ 2011-07-10 12:58 春秋十二月 阅读(2056) | 评论 (0)编辑 收藏
   著名的千千静听音乐播放器,其界面简洁优雅、美观大方,特别是它那种几个窗口像磁石般相互吸引,当拖动主窗口时,粘在一起的其它窗口会跟随着一起移动,当拖动其它窗口时,又能脱离不粘在一起,这种窗口效果让用户操作方便,省心省力。为描述方便,本文称这种效果为多窗口的组合分离,它的主要特点是仅用鼠标任意移动窗口,就可组合或分离,当组合在一起时,移动某窗口(如主窗口,暂称为老板窗口)能整体移动,移动其口窗口(非老板窗口,暂称为工人窗口)又能将自己脱离出来。近来由于工作需要实现了类似于此的窗口效果,经过几天的测试,终于稳定。在开发过程中,考虑了以下几个问题:
     (1)  组合分离的条件如何决定判断。
     (2)  当窗口大小改变时,包括最小化,最大化,缩放窗口等,如何保证不影响组合分离,能正常整体移动。
     (3)  窗口个数是可变的,当新建或销毁窗口时,如何保证不影响组合分离,能正常整体移动(千千静听窗口个数是有限的,而且可能只是隐藏窗口)。
     (4)  采用什么数据结构较好,如何维护任意两个窗口间的距离关系(相交或相切视为组合,相离视为分离)。
     (5)  当拖动老板窗口时,如何拖动与其组合的所有窗口,关键是如何得到所有与其组合的窗口列表。
     (6)  如何针对这种效果设计一个通用的组件类,只需调用几个方法便可搞定。
   
   针对以上问题,主要思路是视屏幕上任意多个窗口为顶点,以其窗口矩形中心点来看待这个窗口,如果任意两个窗口间关系为组合,则视这两个顶点间是相通的,即两个顶点存在边。如果为分离,则视两顶点间是不通的,即两顶点不存边。因此可以用无向图来存储窗口和关系,为简单起见,我用的是邻接矩阵,问题(4)得以解决。既然用邻接矩阵来存储,那么如何得到所有与老板窗口相关的组合窗口呢?由于实际多个窗口在移动过程中,会改变其组合分离关系,这就会得到多个无向图的连通分量,而我们需要的是包含老板窗口的那一个连通分量,因此可以用DFS深度搜索遍历这个无向图连通分量,起始顶点是老板窗口,遍历完后就会得所有与其组合的窗口列表,问题(5)得以解决。现在讨论问题(1),这里有个细节问题就是组合分离的条件判断有两种情况,一是当移动窗口时的条件,称为条件1,因为实际向一个窗口A移入另一个窗口B时,要达到还没有接近窗口A时便一下子靠近A就像被A吸引的效果,当移出B时还没完全移到A窗口外面时便一下子远离就像被A排斥的效果。二是当大小改变时的条件,称为条件2,这个不同于条件1,因为它不需要那种吸引排斥的效果,也没必要,这个条件2就是简单的判断A和B矩形是否相交,API函数IntersectRect即可完成这一判断。条件1的判断如下图所示:
                                                           
   在B向A移入过程中,当B的中心点在矩形left,top,right,bottom范围内,可认为是发生组合,实现吸引效果;当在center矩形内,认为是已经组合了;同理,B向A移出过程中,当B的中心点在矩形left,top,right,bottom范围内,可认为是发生分离,实现排斥效果。当都不在left,top,right,bottom,center矩形范围时,认为是已经分离了。至此,问题(1)得到解决。当窗口大小改变时,需要更新邻接矩阵反映窗口间关系的变化,而后更新组合窗口列表,组合窗口列表的计算依赖于邻接矩阵,运用DFS算法来更新,这在WM_SIZE消息事件处理内完成,问题(2)得到解决。当新建窗口时,需要向无向图中增加(窗口)顶点,扩充邻接矩阵以备存储与其它窗口的关系;当销毁窗口时,需要从无向图中删除对应的顶点,而后从邻接矩阵中删除对应的关系,问题(3)得到解决。
   上述问题(1)--(5)都已分析并得到解决,总的来说,就是以数据结构中无向图的观点和算法来建模解决这些问题的,特别是运用到了DFS搜索算法来重建已组合的所有窗口列表,只有这样,在移动老板窗口过程中,才能保证其它窗口跟随着一起移动。接下来就是最后一个问题,也就是怎么封装设计组件类,以达到方便应用的目的,综上所述,设计接口方法与以下窗口4种消息相关:
   1) 创建窗口发生的消息,如WM_CREATE,WM_INITDIALOG等。
   2) 关闭或销毁窗口发生的消息,如WM_CLOSE,WM_DESTROY等。
   3) 窗口大小改变后消息,WM_SIZE。
   4) 窗口移动中消息,WM_MOVING。
   
   另外提供一个设置获取老板窗口的方法,在应用程序中,只需在窗口4种消息处理内调用以上对应4个方法即可实现多窗口组合分离的效果,注意该类没有考虑多线程,因此是非安全的,适用于多窗口属于同一线程内的情况。类声明如下 
 1class CWndMagnet
 2{
 3public:
 4    CWndMagnet();
 5  virtual ~CWndMagnet();
 6
 7public:
 8    void SetLeadWindow(HWND hWnd) { m_hLead = hWnd; }
 9    HWND GetLeadWindow() const return m_hLead; }
10    
11    void AddMagnetWnd(HWND hWnd);
12    void RemoveMagnetWnd(HWND hWnd);
13    void OnLButtonDown(HWND hWnd);
14    void OnNcLButtonDown(HWND hWnd);
15    void OnMoving(HWND hWnd, LPRECT lpRect);
16    void OnSize(HWND hWnd, UINT uType);
17
18protected:
19    void MoveLeadWndSet(HWND hWnd, LPCRECT lpRect);
20    void UpdateLeadWndSet(HWND hWnd, LPCRECT lpRect = 0);
21    void DeleteMagWnd(HWND hWnd);
22    void Add2DMatrix();
23    void Delete2DMatrix(HWND hWnd);
24    void Update2DMatrix(HWND hWnd, LPRECT lpRect = 0);
25
26private:
27    int GetFirstNeighbor(int v);
28    int GetNextNeighbor(int v, int w);
29    void DFS(int v, std::vector<bool>& vecVisited, std::vector<int>& vecNeighbor);
30
31private:
32    static const int      s_c_iThreshold = 10///< 偏移阀值
33    HWND                  m_hLead;        ///< 老板窗口
34    std::map<HWND,POINT>      m_map_leadWnd;  ///< 粘合窗口列表
35    std::map<HWND,int>        m_map_magWnd;   ///< 需要组合分离的窗口列表
36    std::vector<std::vector<bool> > m_vec_2DMatrix; ///< 表示任意两个窗口间相交或相切的邻接矩阵
37    

38}
;
posted @ 2011-07-04 11:14 春秋十二月 阅读(2442) | 评论 (0)编辑 收藏
   这个问题,解法比较多,假设序列X大小为N,一种普通的做法是先设定最大值和最小值都为序列中第一个元素值,在一个循环内,每次循环都和当前最大值和最小值来比较更新,这样就需要2N-2次比较了;再进一步,如果先查找最大值,则需N-1次比较,再查找最小值,则需N-2次比较,总共是2N-3次比较,比上一方法少了1次。这些做法都是每次取1个数来比较,比较次数为O(2N)。接下来,我们把情况扩展到每次取多于1个数,先试试看每次取2个数,即N-2个数的解,对N个数求解。当N=1时,最大值和最小值就是第1个元素值;当N=2时,最大值和最小值就是第1个元素和第2个元素的最大值和最小值;考察X[N-2]和X[N-1],同时令前N-2个数的解是MAX和MIN,易见,做3次比较便能得出新的最大值和最小值,首先比较X[N-2]和X[N-1],然后将其中大数同MAX比较,小数同MIN比较,这样一来,大约需O(3N/2)次比较即可,而不是先前的O(2N)次。那么,是不是每次取3个或4个数能更进一步减少总共的比较次数呢?有趣地是,可以证明,每次取多于2个数来比较时,总共所需次数和取2个元素来比较是一样的。本文示例的是每次取2个数比较的实现,C++代码描述如下
 1//动态数组版本1,T须支持operator < 运算
 2template<typename T>
 3void get_max_min(const T* p, size_t n, T& max, T& min)
 4{
 5    assert(n);
 6
 7    T t_max, t_min, p_min, p_max;
 8    p_min = p_max = p[0];
 9
10    size_t i;
11    for(i = 1;i < n-1; i+=2)
12    {
13        if (p[i+1< p[i]) 
14            t_max = p[i], t_min = p[i+1];
15        else
16            t_max = p[i+1],t_min = p[i];
17
18        if (p_max < t_max) 
19            p_max = t_max;
20
21        if (t_min < p_min)
22            p_min = t_min;
23    }

24    if (i == n-1)
25    {
26        if (p_max < p[n-1]) 
27            p_max = p[n-1];
28        else if (p[n-1< p_min) 
29            p_min = p[n-1];
30    }

31    min = p_min;max = p_max;
32}

33
34//静态数组版本2, T须支持operator < 运算
35template<typename T,size_t N>
36void get_max_min(const T (&p)[N],T& max, T& min)
37{
38    get_max_min(p,N,max,min);
39}
   对于以上代码的实现,由前面分析可知,当N为奇数时,总共比较次数为3/2*(N-1);当N为偶数时,总共比较次数为3N/2-1,时间复杂度为0(3N/2)。
posted @ 2011-07-03 18:05 春秋十二月 阅读(1953) | 评论 (0)编辑 收藏
   原题为某著名软件公司的试题,大意如下:给定一个容器,要求删除容器中重复的元素,并保持剩余元素的顺序不变。在这里,本文为了全面通用考虑,作了扩展,删除vector中的重复元素,从容器中元素顺序上可分为2种情形:1)保持剩余元素顺序不变,特称为稳定删除,对应下面的stable_unique版本函数模板 2)不考虑顺序变化,特称为快速删除。对应下面的quick_unique版本函数模板。从重复的概念定义也可分为2种情况:1)基于简单的相等判断 2)基于谓词的等价判断。因此,由排列组合得知应该有4种版本的实现,下面给出代码描述
 1//函数对象模板类
 2template<typename T>
 3struct Predicate
 4{
 5    Predicate()
 6    {
 7    }
 8
 9    Predicate(const T& t)
10        :_t(t)
11    {
12    }
13    bool operator()(const T& t) const
14    {
15        //可以自定义比较实现
16        return _t == t;
17    }
18    //支持std::unique谓词版本的删除
19    bool operator()(const T& l,const T& r) const
20    {
21        //可以自定义比较实现
22        return l == r;
23    }

24    T _t;
25}
;
26
27//quick_unique版本1: 相等判断
28template<typename T>
29void quick_unique(std::vector<T>& con)
30{
31    std::sort(con.begin(),con.end());
32    con.erase(std::unique(con.begin(),con.end()),con.end());
33}

34
35//quick_unique版本2: 谓词判断
36template<typename T,template <typename U> class Predicate>
37void quick_unique(std::vector<T>& con)
38{
39    std::sort(con.begin(),con.end());
40    con.erase(std::unique(con.begin(),con.end(),Predicate<T>()),con.end());
41}
42
43//stable_unique版本1: 相等判断
44template<typename T>
45void stable_unique(std::vector<T>& con)
46{
47    std::vector<T>::iterator it,ret,beg = con.begin();
48    for (it = ++con.begin();it!=con.end();)
49    {
50        ret = find(beg,it,*it);
51        if (ret != it)
52            it = con.erase(it);
53        else
54            ++it;
55    }
56}
57
58//stable_unique版本2: 谓词判断
59template<typename T,template <typename U> class Predicate>
60void stable_unique(std::vector<T>& con)
61{
62    std::vector<T>::iterator it,ret,beg = con.begin();
63    for (it = ++con.begin();it!=con.end();)
64    {
65        ret = find_if(beg,it,Predicate<T>(*it));
66        if (ret != it)
67            it = con.erase(it);
68        else
69            ++it;
70    }
71}
   以上代码在vc2005环境下编译测试通过,再进一步扩展,问题完全可以归类为删除某容器内重复元素,只要再加一个模板的模板参数即可template <typename T> class Conn;函数的形参类型变为std::Conn<T>就行了,但要注意的是不同平台下对应容器的erase实现所返回的迭代器可能有所差别,比如map要这样写才能在linux上正确工作:conn.erase(it++)。对于特殊的情况,可对以上4个函数作对应的重载(注意,函数模板没有特化的概念)来解决。
posted @ 2011-06-25 14:49 春秋十二月 阅读(5543) | 评论 (3)编辑 收藏
   原为某著名软件公司试题,大意如下:请实现以下两个函数:char toupper(char c); char tolower(char c); 分别用于将传入的字母转为大写和小写。两个函数传入的参数取值范围都是[a-zA-Z],并且为ASCII编码,实现时不用检查参数合法性。两个函数的实现不能使用任何形式的分支、跳转等类型的语句或指令(特别说明:C/C++的条件操作符?:也是分支指令的一种形式,故而不能使用)。请尽可能多的写出你知道的办法。   

  分析解决:此题比较特别,限制严格,根据题目要求,排除if else、for、while、do while、switch case、?:外,能使用的语句就只有 =、+=、-=、&、|、^、++、--这些了,想要实现大小写转换,只能从这些语句中进行选择思考,由于字符集为ASCII编码,且范围明确为[a-zA-Z],我们知道,a-z对应ASCII值为97-122,A-Z对应ASCII为65-90,观察这些数字,可以发现97-122都大于96 ,65-90都大于64且小于96,进一步从二进制上考虑,则发现所有小写字母对应的二进制形式为011XXXXX,大写字母对应的二进制形式为010XXXXX,一到这里,哈哈,答案就出来了,通过位运算&和|就可实现了。代码描述如下
 1 char toupper(char c)
 2 {
 3     return c & 0x5F;
 4 }

 5 
 6 char tolower(char c)
 7 {
 8     //c | 0x60也行,但不太好,因为0x60会改变结果的第7位值,根据题目意思,改变第6位值为1,而其它位保持不变就够了。
 9     return c | 0x20;
10}
   至于其它方法,我就没多想了,还希望各位大侠多多分享一下哈。
posted @ 2011-06-25 12:13 春秋十二月 阅读(2872) | 评论 (7)编辑 收藏
   原题为某游戏公司试题,大意如下:  对于一个单向链表,试写出找到它的倒序第m个元素(m >= 1)的函数,注意变量命名、注释、时间复杂度、空间复杂度。注:要求写出可编译并可以运行通过的程序代码。

  这道题的常规做法或者说首先想到直觉的方法M1是先求得链表的长度,即元素总个数n,然后问题转化为求顺序第n-m+1个元素。下面给出第2种方法M2:先求得顺序第m个元素,用一指针P指向这个元素,用另一指针PR指向链表的头部,现在好了,P和PR同时向右移动,直到P为空,则PR就是要求的倒序第m个元素,如果因m超越界限,则PR为空,表示没找到,这样一来,只需一次循环就够了。C++代码描述如下
 1 template<typename T>
 2 struct Node
 3 {  
 4     T  data;    /**////< 数据
 5     Node* next;  ///< 指向下一结点的指针
 6 } ;

 7 
 8 template<typename T>
 9 Node<T>* ReverseFind(Node<T>* head, size_t m)
10{
11    size_t  n = 0;
12    Node<T> *p, *pR = NULL;
13    for (p = head;p;p = p->next)
14    {
15        if (++== m)
16        {
17            pR = head;
18            continue;
19        }

20        if (pR)
21        {
22            pR = pR->next;
23        }

24    }

25    return pR;
26}
  现在分析这2种方法的时间复杂度,假设链表元素个数为N,所求倒序为第M元素,N>=M,则M1方法为0(N)+0(N-M)=0(2N-M),M2方法为O(M)+O(N-M)=0(N),因此M2快于M1。
posted @ 2011-06-24 11:40 春秋十二月 阅读(2228) | 评论 (11)编辑 收藏
   原题为某游戏公司的试题,大意如下:写一个千位分隔符算法,函数原型是 char * format_thousands_separator(unsigned long val); 要求实现效果是 1.使用者不需要释放返回的字符串指针 2.支持最多调用16次而不返回相同指针地址。可以用以下方法测试       
    printf("num1(%s), num2(%s), num3(%s)\n", format_thousands_separator(0),format_thousands_separator(123456),format_thousands_separator(23456789)); 
   注:要求写出可编译并可以运行通过的程序代码。

   经过修改后,我目前最简洁的C代码描述如下
 1 char* format_thousands_separator(unsigned long  val)
 2 {
 3     static char buf[16][16];
 4     static int  c = 0;
 5 
 6     long m, n = 0;
 7     char* p = &buf[c++ % 16][15];
 8     *= '\0';
 9 
10    do 
11    {
12        m = val % 10;
13        val = val / 10;
14        *--= '0' + m;
15
16        if (val && !(++% 3))
17            *--= ',';
18
19    }
 while(val);
20
21    return p;
22}
   这里再稍作一下扩展,使之能支持负数,代码描述如下
 1char* format_thousands_separator(long  val)
 2 {
 3     static char buf[16][16];
 4     static int  c = 0;
 5 
 6     long m, n = 0;
 7     char* p = &buf[c++ % 16][15];
 8     *= '\0';
 9 
10    do 
11    {
12        m = val % 10;
13        val = val / 10;
14        *--= '0' + (m < 0 ? -m : m);
15
16        if (!val && m < 0
17            *--= '-';
18
19        if (val && !(++% 3))
20            *--= ',';
21    
22    }
 while(val);
23
24    return p;
25}
   如果哪位大侠有更简洁高效的代码,还望留言或Email我,谢谢哈
posted @ 2011-06-24 10:55 春秋十二月 阅读(2583) | 评论 (4)编辑 收藏
     摘要:    一般地,泛型容器的设计实现大多只是存储了类型的单个对象,而没有存储类型的多个对象,如果有这样特定的需求,容器内的元素要求都是某个类型的多个对象,那么这时就可以考虑用模板类的数组特化来实现了,作为例程,下面C++代码描述了主模板实现 Code highlighting produced by Actipro CodeHighlighter (freewa...  阅读全文
posted @ 2011-06-23 12:01 春秋十二月 阅读(2094) | 评论 (2)编辑 收藏
仅列出标题
共10页: First 2 3 4 5 6 7 8 9 10