Conzxy's blog

《C++ Templates》第二版阅读笔记CppTemplates

钢条切割问题Problem: Given a rod of length n inches and a table of prices $p_i$ for i=1,2,…,n,determine the maximum revenue $r_n$ obtainable by cutting up rod and selling the prices.Note that if the price $p_i$ for a rod of length n is large enough,an optimal solution may requires no cutting at all 长度与价格的关系表如下： Length i 1 2 3 4 5 6 7 8 9 10 Price $p_i$ 1 5 8 9 10 17 17 20 24 30 按照动态规划的两个特征，先找到该问题是否具有最优子结构（optimal substructure）性质： 先切成两段，分成两个相异的子问题，这样就会产生许多两段切割方案，然后在这些方案中取最大收益即可 r_n=\mat ...

循环不变式循环不变式是一个用来证明循环过程是否正确的不变量，分为三个阶段： Initialization:在第一次迭代开始前确保不变量为真 Maintenace:在一次迭代前为真，到下一次迭代前保持为真 Termination:循环终止时，根据不变式是否为真可以得知循环是否正确 依据循环不变式我们可以验证任何算法的循环过程是否正确 循环不变式前两个步骤类似于数学归纳法，最后一个步骤不同，因为数学归纳法是无穷的，而循环是有穷的

插入排序我们将欲排序的元素称为Key。插入排序的思想就是将A[j]（key）插入到前面A[1..j-1]有序序列的第一个使得该序列仍然保持有序的位置。 比如有这样一组数[1,2,3,3,5,6,4] 取key=4，前面序列为有序序列，该序列按<谓词排序，那么有两种思路： 从后往前：从Key前一位开始依次比较，在第一个不满足该谓词的元素后面插入 从前往后：从第一位开始依次比较，在第一个满足该谓词的元素前面插入 我们采取第一个思想，如果满足谓词，则将$i$指向元素往后移，为$i$的插入腾出空间，直到不满足时在$i$的后面插入key 12345678INSERTION-SORT(A,P)for j ← 2 to A.length Key ← A[j] i ← j-1 while i > 0 and P(Key,A[i]) A[i+1] ← A[i] i ← i-1 A[i+1] ← Key 翻译成C++如下： 12345678910111213template<typename T,typename Pred>void insert ...

了解C++默默编写并调用了哪些函数 自动生成的函数类型当你自己没有声明任何函数时，C++会自动给你声明： default constructor copy constructor copy assignment operator destructor 这些函数唯有在被调用时才会被编译器创建出来 注意，编译器生成的函数都不是virtual（这方面请看Item 7） 无法自动生成的情形 在“内含引用成员或const成员”的类中请提供自己的拷贝赋值和拷贝构造 基类如果拷贝赋值是delete或是private的则拒绝为派生类生成拷贝赋值 三/五法则 如果这个类需要一个析构函数，我们几乎可以肯定它也需要它需要一个拷贝构造函数和拷贝赋值运算符重载 如果需要一个拷贝构造函数，几乎肯定也需要一个拷贝赋值运算符重载，反之亦然 但是无论需要拷贝构造函数还是拷贝赋值运算符重载都不意味必须要析构函数

确定对象被使用前已被初始化基本保证永远在使用对象之前先将它初始化： 对于无任何成员的内置类型，你必须手工完成此事 对于内置类型以外的自定义类型，则确保每一个构造函数都能将所有成员初始化 初值列表构造函数优先选择初值列表（member initialization list） 有这样几个优点： 省去了拷贝赋值的开销以及没有多余的默认构造 如果成员类型为const或引用，不得不初始化 承诺： 总是在初值列表中初始化所有成员 按照成员声明次序进行初始化 non-local static对象的处理方式这里指的non-local是相对于函数而言的，函数以内的static对象是local （但实际local只要是个block scope都是，不限于函数） 注：这里static是指static storage duration不是声明为static，也不一定得是internal linkage 我们的问题是： 如果某翻译单元内的某个non-local static对象的初始化用到了另一个翻译单元的某个non-local static对象，可能是还没有初始化的 123456 ...

OOP概述OOP，全名：Object-Oriented Programming 其核心思想为： 数据抽象（封装）：使得类的接口和实现分离 继承：可以建立相似关系模型 动态绑定（多态）：可以在一定程度忽略相似类型的区别从而以统一的方式使用 基类和派生类在继承体系中，处于根部的就是基类（base class），而以此衍生的则是派生类（derived class）。 基类负责定义层次关系中所有类都共有的成员，每个派生类则定义自己特有的成员。 基类有两种成员函数：虚函数（virtual function） 和非虚函数（non-virtual function） 前者是是基类希望派生类进行覆盖的，后者则直接继承 但实际上，虚函数还可细分为：纯虚函数（pure virtual function） 和非纯虚函数（impure virtual function） 这个可以参考Meyes的《Effective C++》Item 34 前者是为了让派生类只继承函数接口，而后者是继承函数接口和默认实现 直接基类和间接基类123class base{}class D1:publ ...

二叉堆支持合并有左式堆和二项队列，我们实现二叉堆用最基本的数组就行了。 关键操作insertExample插入14 Code1234567891011121314151617181920template<typename T> void BinaryHeap<T>::insert(const T& x) { if(currentSize+1==array.size()) array.resize(2*array.size()); //扩容 /* * 上滤操作（percolate up）：与下滤操作类似，但是不是调整根结点，而是child。 * hole是新增位置的child，其parent是最后一个父结点，通过父结点不断往上爬直到 * 欲插入值不小于父结点停止。 * 最后用储存插入值的哨兵填上hole。 */ int hole=++currentSize; T copy=x ...

二项队列(Binomial Queues)名字由来首先我们来认识一下二项队列是个什么东西，二项队列不是一颗满足堆序性质的树，而是由这些树组成的森林(forest)。 如上图所示，这是由B0、B1、B2、B3组成的二项队列，其中每一颗树都称为二项树(binomial tree)。我们将其表示为Bk。k表示二项树高度，Bk实际上是由B（k-1）接在另一个B（k-1）的根上（merge的基础）。在每个高度都只有惟一一个二项树，因此二项队列可以表示为任意大小。二项队列为什么会如此命名，是因为二项树的性质。 性质一来源于定义，而性质二和性质三都可以通过数学归纳法得出，性质二比较显然，这里稍微证明一下性质三： 性质四也很好理解，我这里举一个例子吧，假设二项队列大小为27，27=1+2+8+16，因此可以是由B0，B1，B3，B4组成的，那么27的二进制表示就是11011，自己算算确实如此，因此我们可以根据总结点数来得出二项队列是由哪些二项树组成的。性质四实质就是十进制转二进制。 算法分析 补充一点在上面，从这点也可以看出寻找最小元素的算法分析度为O(logn)。我们还是来重点讲一下合并 ...

左式堆（Leftist heap）引入二叉堆不能有效地支持合并操作，而且只使用一个数组的话，我们需要将一个数组复制到另一个数组中，时间复杂度为O(n)。因此我们通过链式来设计一个新的方便合并的堆，这就是左式堆。 性质我们要介绍左式堆首先要介绍零路径长（null path length，简写为npl） 设结点X，则npl（X)=X到不具有两个儿子结点的最短路径。 所以只有一个儿子或是没有儿子的结点的零路径长为0。左式堆的性质是：每个结点的左儿子的零路径长大于等于右儿子。因此左式堆是不平衡堆，偏向于向左增加深度，也因此便于合并，故得名——Leftist。事实上，右路径是左式堆路径中最短的，否则，将会破坏左式堆性质。 定理这里我们来证明一个定理： 在右路径上有r个结点的左式堆至少有2^r-1个结点 证明： 也就是说含有N个结点的左式堆，有一条最多含有[log(N+1)]个结点的右路径。也正因此我们处理左式堆的一般思路就是将一切工作都放在右路径上进行，这样尽可能地保证了树的深度小（后面的操作有体现）。 合并操作我们主要侧重来看一下合并是如何进行的。先声明一下，插入是合并的一种特殊形式，看 ...