Category Archives: 计算机与 Internet

读书的时候，读Effective C++，当时还打趣的说，世界上的C++程序员分为两种，看过Effective C++的，和没有看过的。最近才注意到，gcc的 -Weffc++编译选项能警告我们，如果代码没有遵循Effective C++的编码规范。 最近我们就发现一个：     struct uncopyable {         uncopyable() {}     private:         uncopyable(uncopyable const&);     };     struct A: uncopyable {}; // -Weffc++ warning: base class ‘struct uncopyable’ has a non-virtual destructor 麻烦的是我们使用的大多数STL，BOOST 库都没有完全遵守Effective C++的规则。而-Weffc++还没有聪明到能识别哪些警告是不需要的，从而造成我们编译代码时打印出了大量不必要的警告信息。anyway, -Weffc++是个好东西，宁可错报，不要漏报。

前面分别介绍了 Resolving Recurrence(1) – Substitution Method 和 Resolving Recurrence(2) – Recursion Tree 来评估T(n) = aT(n/b) + f(n) 的时间复杂度。 这一节介绍Master Method，既然叫Master，可见其重要程度。掌握了Master Method,我们可以很快写出Merge Sort, Heap Sort以及Quick Sort的时间复杂度。 Master Method:  (在 a>=1 并且 b>1 的情况下) 如果f(n) is polynomially smaller than nlogba, polynomially smaller就是grow … 繼續閱讀 →

T(n) = T(n/3) + T(2n/3) + n Recursion Tree其实就是Iteration，只不过图型化以后我们看起来更容易理解了。 T(n) = T(n/3) + T(2n/3) + n       = [T(n/9) + T(2n/9) + n/3] + [T(2n/9) + T(4n/9) + 2n/3]       = ……画成图就是：   总的cost就是把每一层的cost加起来。层数就是树的高度。上面的这个问题有点tricky的。从图上看分两种情况，一种以1/3的方式减少n,还有一种是以2/3的方式。前一种方式经过log3n次就到达叶子节点，后一种方式经过log3/2n次，因为log3/2n > log3n，树的高度为log3/2n。每一层加起来的代价是cn, 其实越到下面，每一层的cost会小于cn的，因为那时候按照1/3的方式减少的那一枝已经不存在了。 T(n) <= cn x log3/2n … 繼續閱讀 →

整个recurrence就是研究一个数学表达式：T(n) = aT(n/b)+f(n)  意思是先有一个问题T(n), 解决思路为把T(n)切分成a个小问题， 每个小问题的代价是T(n/b), 然后把a个T(n/b)的结果合并起来的代价是f(n)；依次类推，直到T(k)的粒度小到其复杂度是一个常数。很像是递归吧～～递归只是一种实现方式，这里介绍的是一种思路和评估这种思路复杂度的方法。 经典的评估Recurrence的方法有3种，Substitutuon, Recursion Tree和Master Method.  看下面的命题： T(n) = 4T(n/2) + n ,需要证明T(n)=O(n2) Substitution： 假设T(k) <= ck2  k<n; 所以 T(n) <= 4(n/2)2 +n = n2+n 要证明n2+n<=cn2 好像不容易。 我们换个假设，假设T(k)<=c1k2-c2k ，这样的话T(n) <= c1n2-(2c2-1)n = c1n2-c2n-(c2-1)n. 所以只要 c2 … 繼續閱讀 →

周日的下午，窗外下着雨，我一边在听陈奕迅的‘爱情转移’，一边在写如何实现一个C++风格的Timer。 要求：在HTTP服务器上实现一个不需要精确定时的Timer，该Timer本质上是一堆时间事件的管理类，每个时间事件都绑定一个事件回调函数，可以scedule在某个时间点开始运行，运行一次或者以固定时间间隔反复执行。Timer的使用者可以以代码方式加载或者撤销指定的时间事件。 设计这个Timer的原因，因为一个HTTP服务器上加载了诸多服务，我们需要定时收集，统计系统MEMORY,CPU, LOCK,QPS, LATENCY等信息，同时我们希望统计这些资源是如何在各模块中分配的，有了这些信息，才能方便进行trouble shooting和performance tuning。 设计：从逻辑上来说，每一个事件包括以下信息：开始执行时间，执行间隔，是否需要repeat execution, 绑定的事件回调函数…在C++的实现中，我们往往把回调函数设计成一个类(我们可以在类实例中存储状态，这样比单纯的回调函数更加灵活)，看下面的接口： class TimeoutCallback{public:       virtual ~TimeoutCallBack(){};       virtual void CallbackFunc() = 0; //纯虚接口，所有定制的callback都继承TimeoutCallback并实现自己的CallbackFunc。}; 一个TimeoutCallback实例可以被绑定在多个事件上，下面是事件实现类(为了演示方便，这里都声明成public) class TimeEvent{public:       time_t  m_schedule;   //预计下一次的执行时间       time_t  m_interval;     //如果是repeatable的事件，事件的执行间隔       bool     m_repeatable; //是不是需要重复执行       int       m_count;        //该事件被触发的次数       TimeoutCallback* m_callback; //绑定的事件回调类实例 }; 而Timer类需要提供事件的注册，撤销以及执行功能。 … 繼續閱讀 →

这是很经典的问题，很多C语言的初级面试都会碰到。今天在这里重提是因为我以前一直没有真正理解，我是死记得： const char* p: p指向的内容是常量，但是p是常量指针char* const p: p指向的内容是变量，但是p是指针常量 因为我没有真正理解，所以稍微一变化我就傻了：template <class T>void getStrT(const T& val)   {…}   // void getStr(const char*& val){…}  // const char* p="This is Arrowpig!"; getStr(strdup(p));     //1. getStrT(strdup(p));   //2. 结果getStrT是成功编译的，但是 getStr碰到编译错：error: invalid initialization of non-const reference of type ‘const … 繼續閱讀 →

今天调一个程序，里面用到了vector，在GDB里面看vector里面的东西一点也不直接，如果碰到vector<vector<int> >，要想看看里面的内容就更不爽了。也可能是我不知道有什么好办法，如果谁知道，麻烦告诉我一下。 没有办法，只要弄个Dump函数来看： template <class T>void DumpArrayArray(vector<vector<T> >& arr){    cout<< "Dumping Data:" << endl;    vector< vector<T> >::iterator outIter = arr.begin();     for (; outIter!= arr.end(); outIter++)      {          vector<T>::iterator inIter = (*outIter).begin();         for (;inIter!=(*outIter).end();inIter++){             cout << *inIter << "t";         }         … 繼續閱讀 →

2005年5月份，我转正后1个月，组里组织我们到青岛旅游，那个时候我正在看Exceptional C++这本书，有一个章节一直看不懂，就打印了带到青岛去了，嘿嘿，旅游还是有助于激发灵感的，在旅馆里我终于看懂了，回来以后总结了一个PPT。这个PPT很有特点，因为我做了一个Q版。时光飞逝阿，转眼2年多过了，房价又涨了好多，本来可以买两室两厅的钱只够一室一厅了。特重写C++异常处理献给我们可爱的房地产开发商.   Exception-Safety Issues and Techniques预练武功，先修心法看看金庸武侠小说中的那些少年俊才，在开始都是不一定有很高的技巧，但总是在年少的时候就或得到高人指点，或得到武林内功秘籍，并且都是心地善良。作为一名C++的入门弟子，同样，在碰到异常这个主题时，有两条要铭记在心：1. 异常安全不是口号，从一开始就要贯彻执行。在设计程序时就要考虑的异常的处理，不要给自己借口，说以后碰到了再说吧。千万不能懒惰！等把代码都写的七七八八了，再来添加异常处理。2. 要有怀疑一切的谨慎态度，要知道，所有的语句都是靠不住的。如果你拿不出100%的信心说这段代码一定exceptional-safe,那这段代码就是异常不安全的。总之，首先要培养 异常安全的意识。 两个概念：Exception-Safe这里的safe就是说从表现给外部的功能上来说，我总是正常工作了。至于我为了正常工作，饿了肚子，取消了和女朋友的约会之类的事情，外部的调用代码你们不需要关心。Exception-Neutral:我只是个传话筒，我虽然是个基层领导，但是我不作为，一线的员工有什么意见，我一字不改的转达给我的上司。下层函数抛上来的异常，我原封不动的throw给上层函数。但是并不是所有的基层领导都是不作为的，他们要把底层员工的意思包装一下，整理一下…然后再汇报给上层，这就叫做non-fully exception-neutral. new和delete: 你们到底做了什么？！new和delete的两步曲，我想大家都了解的:分配内存和调用构造函数/调用析构函数和释放内存。本着怀疑一切的态度，如果分配内存失败了呢，如果构造函数失败了呢，如果析构函数失败了呢。就new和delete的层次上，编译器已经帮我们做了很多工作，如果我们希望new和delete是Exception-Safe的，最好打开编译器的/GX开关。 我们来看一段小程序template <class T>Stack<T>::Stack():v_(0),     //这个Stack底层用数组实现，数组指针初始化为0vsize_(10), //希望为数组分配可以容纳10个元素的内存vused_(0)   //现在这个Stack为空{ v_ = new T[vsize_]; //initial allocation}分析一下这段代码1.这段代码是exception-neutral的。如果new抛异常，Stack的构造函数只是原封不动的将下层异常throw给上层。2.这段代码没有内存泄漏。如果内存分配了，但是某个T的构造函数失败，/GX会保证new分配的内存会被释放3.这段代码的状态是合理的。如果内存分配失败，std::bad_alloc被抛出，Stack的构造函数失败，这是合理的。如果内存分配成功，第N（N<10）个T对象的构造函数失败，/GX会保证前面N-1个已经被成功构造的对象的析构函数被调用，并且释放内存。所以整体状态也是合理的。 好了，正式进入修炼，本心法一共有3层第一层： 我指保证没有泄漏资源，其他的就难说了。可以参考两本书：《Coping with Exceptions》 和 《More Effective C++》怎么能保证我能够到达第一层呢？  第一层还是挺简单的，只要不泄漏资源（内存）就可以了，一个常用的技巧是把一定要在函数退出时需要释放的资源封装在一个临时对象中，这样可以保证在函数退出时临时对象析构时将资源释放。为了保证第一层还有一句话是这样讲的：恶魔！抛出异常的析构函数。为什么这样说呢，并不是说析构函数不能抛出异常，原因是这样的，如果析构函数是由于用户代码造成的，那不要紧。但是有时候析构函数是由/GX以后由编译器添加的代码调用的，看这样的情况：CMyObject* p = new CMyObject[10];如果内存被成功分配，在调用第7个CMyObject的构造函数的时候有失败，编译器为了保证行为合理，会依次调用前面成功的6个对象的析构函数然后释放内存，如果在这个时候前面6个析构函数中任何一个失败（有异常抛出），就会调用Terminate终止程序，这是我们不愿意看到的。为了保证这一点，我们常常看到这样的函数声明：void operator delete[](void*) … 繼續閱讀 →

纵览多数面向对象的库，在事件处理上都希望把事件源和事件处理分开。在说OSG的事件处理之前我想先看一个通用的事件处理模式，Reactor模式。Reactor的是用于事件驱动的应用程序中的，将一个或多个客户提交的请求分发给相应的事件处理器处理。这里有两个设计需求：Q1.客户提交的请求时不能阻塞客户代码，我们可以待会处理你的请求，但是不能看到你的请求时理都不理你。解决： 设计一个Synchronously Event Demultiplexer.使用不阻塞客户代码的API来检测到达的事件源请求，怎么把事件源和事件处理器关联起来呢，我们需要给Reactor提供事件注册能力，告诉Reactor哪些事件你是有兴趣的，什么样的事件源和什么样的事件处理器关联。 2.程序要求方便扩展，当我要添加一类事件处理能力时不能对现有代码造成大的冲击。解决：Reactor中为了实现事件派发一定有一张映射表 (Event Source –> Event Handler)，我们可以定义一个Event Handler的接口，所有具体的事件处理类都从该接口继承，这样，添加一类新的事件处理时，只需要定义一个新类，并注册给Reactor就可以了。 那OSG呢，OSG是桌面系统渲染库，我需要相应鼠标操作，键盘操作，以Windows为例是由windows的消息循环处理的，我怎么能用面向对象的发式去包装它使得客户使用的时候也只要简单的定义继承类，注册事件处理类从而只要在事件继承类中填写处理代码就可以了呢。看看OSG事件处理的客户代码是怎么写的：先定义具体的事件处理类，这里是picking,必须从OSG预先定义好的事件处理接口继承class PickHandler : public osgGA::GUIEventHandler{ public:       //实现这个接口，在这里填写处理代码 }；      bool handler(const osgGA::GUIEventAdapter& ea,osgGA::GUIActionAdapter& aa){ …}; };再看看主程序：int main(int argc, char** argv){     //创建场景的视图     osgViewer::Viewer viewer;     viewer.serSceneData( createScene().get());          //添加pick的事件处理类     viewer.addEventHandler(new PickHandler);          … 繼續閱讀 →

OSG和OpenGL的主要区别之一是OSG提供了组织空间场景的功能。OSG把空间场景和场景中的所有物体都组织在一棵树下。根节点代表整个场景，由根节点出发可以遍历场景中的所有物体。这个实现很简单了，如果我是这棵场景树的设计者，首先想到的就是，定义这个的节点类：class gNode{public:    virtual ~gNode();     void addChild(gNode* pChild);private:    std::vector<gNode*> m_children; //存储指向儿子的指针};当我做完所有的事情，准备结束程序的时候，我需要释放整个场景树,也很简单啊，看我的gNode::~gNode(){    std::vector<gNode*>::iterator iter;    for(iter = m_children.begin();iter!=m_children.end(); iter++)   {       if(NULL!=*iter)       {            delete *iter; //如果这个节点还有儿子，会自动递归下去释放的        }    }     m_children.clear();}嘿嘿，不错啊，能够完成所有的工作并且没有内存泄露！可是我们看这样一个问题，假设现在的场景是一个教室，教室中有40张课桌，是一模一样的课桌，整齐的排放成5排8列。那我们的根节点是教室，根节点下面有40个儿子，假设一张课桌由200个三角形组成。那每个课桌节点都保存了这一样的200个三角形，也太浪费了！这样好了，三角形数据不放在课桌节点里面了，我再加一个类专门用来存数据，叫gDeskDataNode.课桌节点里面保存了指向gDeskDataNode的指针：class gDeskNode: public gNode{public:    ~gDeskNode(){ if(m_Data) delete m_Data; }     void SetDataNode(gDeskDataNode* data){ m_Data = data; }private:     gDeskDataNode* … 繼續閱讀 →