枚举变量扩展-2
在前一篇文章里，可能有人注意到了：扩展结果中会出现同一变量的不同实例，如果我们要增加一个限制，扩展结果中每个变量都必须引用相同的实例，该怎么做？
本网站仅单台服务器: 2核2G 99￥包年，集成兼容 MySQL 的 MyTopling 高压缩高性能数据库 |
|
本网站仅单台服务器: MyTopling 2核2G 99￥包年当搜索词中有错别字时，搜索引擎会尝试纠错通过相似拼音纠错搜索引擎把这些字还原成拼音，用一个拼音相同的已知的搜索词代替。 这是一种众所周知的纠错策略，但是，当输错的字是多音字，特别是有多个这样的错误输入时，所有的搜索引擎都尽量绕开这个问题，或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合，在极端情况下会导致指数爆炸！ 例如某互联网大厂的实现(枚举多音字全排列)。 基于自动机的算法可以完美解决这个指数爆炸问题
这个算法也可以用来解决用户输入预测(智能提示)功能用户只输入Query开头部分，就自动提示出整个Query，例如用户输入举头望，就提示出举头望明月。就像现在各种搜索引擎做的那样。 基于编辑距离的纠错在已知的搜索词中寻找编辑距离与用户 Query 最小的词，使用我的算法也可以高效解决（还没做演示页面） 创建 DFA Key 与 搜索 DFA Key 的 耗时 包含了 收集网页展示需要的信息，耗时占比90%以上！ |
|
枚举变量扩展
在很多配置文件中，都会牵涉到变量扩展，一个变量会有多少种可能的扩展结果，这在静态分析中非常重要。这里给出一个算法，使用 perl 来表达(expand.pl)，变量引用使用统一的形式：${varname}。 继续阅读
C++0x 几个很败的修改
Until November 2009, std::future was named std::unique_future
Until November 2010, std::launch::deferred was named std::launch::sync.
非对称类型的 Comparator
结构体数组，按字段查找
我有一个按字段 name 排好序的结构体数组，怎样使用 stl 来查找？
|
1 2 3 4 5 6 7 8 9 |
struct User { std::string name; std::string address; //more fields... }; //.... std::vector<User> v; // expected searching code auto i = std::lower_bound(v.begin(), v.end(), "whinah", CompareName()); |
怎样定义 CompareName ？
|
1 2 3 4 5 6 7 8 |
struct CompareName { bool operator()(const User& x, const std::string& y) const { return x.name < y; } bool operator()(const std::string& x, const User& y) const { return x < y.name; } }; |
一般的 Compare 这样定义：
|
1 2 3 4 5 |
struct CompareName { bool operator()(const User& x, const User& y) const { return x.name < y.name; } }; |
这样的 Compare 只能用于排序，如果要用于查找，我们必须先构造一个 User 对象，再把想查找的name assign 这个 User::name, ….
terminal 的显示编码为 utf8 时用 vim 打开 gb2312/gbk/gb18030 编码的文件
vim "+e ++enc=gbk filename"
vim "+e ++enc=cp936 filename"
怎样区分 const char* 和字符串文字量
在一个面试中，猛然间一闪念，问到了 candidate 这个问题。无解……
stl 中使用到了很多 traits 技术，只要懂得 traits ，这个问题就太简单了！以下是代码示例：
软件工程中很多地方，如果采用直接的办法不能解决问题，增加一个间接层，问题即迎刃而解，type_traits 就是这样一种技术，这个代码示例是自包含的，除了 printf ，没有任何其它外部依赖。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <stdio.h> struct true_{}; struct false_{}; template<class T> struct isarray; template<class T, int N> struct isarray<T[N]> { typedef true_ type; }; template<class T> struct isarray<T* > { typedef false_ type; }; void f(const char* s, false_) { printf("const char*/n"); } template<int N> void f(char const (&s)[N], true_) { printf("const char[N=%d]/n", N); } template<class T> void f(const T& x) { f(x, typename isarray<T>::type()); } int main() { const char* pc = "abc"; const char s[] = "1234"; f("123"); f(s); f(pc); return 0; } |
为什么下面这样的代码不能work？
|
1 2 3 4 5 6 7 |
void f(const char* s) { printf("const char*/n"); } template<int N> void f(char const (&s)[N]) { printf("const char[N=%d]/n", N); } |
答案：C++的重载匹配规则：如果在非模板的候选中能找到一个”精确”匹配，就不会去找模板。”精确”的精确定义包含3大类，5种具体情况，按顺序如下：
Identity Conversion —- 不需要任何转化，最精确，级别 1
Lvalue to Rvalue Conversion — 左值到右值转化， 级别 2
Array to Pointer Conversion — 数组到指针转化， 级别 3
Function to Pointer — 函数名到函数指针， 级别 4，这就是为什么很多时候我们不需要使用 &func_name 而直接使用 func_name
Quolification Conversion — cv qualify 少的可以转化到 cv qualify 多的，级别 5
这也就是为什么下面的代码可以 work：
|
1 2 3 4 5 6 7 |
template<class T> void f(T x) { printf("f(T)/n"); } void f(int x) { printf("f(int)/n"); } ..... f(1); // call f(int) f(1L); // call f(T) f('c'); // call f(T) |
char -> int 不是 exact match, 是 integeral promotion.
long -> int 不是 exact match, 是 integeral conversion.
将递归转化成迭代的通用技术
从理论上讲，只要允许使用栈，所有的递归程序都可以转化成迭代。
但是并非所有递归都必须用栈，不用堆栈也可以转化成迭代的，大致有两类
- 尾递归：可以通过简单的变换，让递归作为最后一条语句，并且仅此一个递归调用。
|
1 2 3 4 5 6 7 8 9 10 11 |
// recursive int fac1(int n) { if (n <= 0) return 1; return n * fac1(n-1); } // iterative int fac2(int n) { int i = 1, y = 1; for (; i <= n; ++i) y *= i; return y; } |
- 自顶向下->自底向上：对程序的结构有深刻理解后，自底向上计算，比如 fibnacci 数列的递归->迭代转化。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// recursive, top-down int fib1(int n) { if (n <= 1) return 1; return fib1(n-1) + fib1(n-2); } // iterative, down-top int fib2(int n) { int f0 = 1, f1 = 1, i; for (i = 2; i <= n; ++i) { int f2 = f1 + f0; f0 = f1; f1 = f2; } return f1; } |
对于非尾递归，就必须使用堆栈。可以简单生硬地使用堆栈进行转化：把函数调用和返回的地方翻译成汇编代码，然后把对硬件 stack 的 push, pop 操作转化成对私有 stack 的 push, pop ，这其中需要特别注意的是对返回地址的 push/pop，对应的硬件指令一般是 call/ret。使用私有 stack 有两个好处：
- 可以省去公用局部变量，也就是在任何一次递归调用中都完全相同的函数参数，再加上从这些参数计算出来的局部变量。
- 如果需要得到当前的递归深度，可以从私有 stack 直接拿到，而用递归一般需要一个单独的 depth 变量，然后每次递归调用加 1。
我们把私有 stack 元素称为 Frame，那么 Frame 中必须包含以下信息：
- 返回地址（对应于每个递归调用的下一条语句的地址）
- 对每次递归调用都不同的参数
通过实际操作，我发现，有一类递归的 Frame 可以省去返回地址！所以，这里又分为两种情况：
- Frame 中可以省去返回地址的递归：仅有两个递归调用，并且其中有一个是尾递归。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// here used a function 'partition', but don't implement it tempalte<class RandIter> void QuickSort1(RandIter beg, RandIter end) { if (end - beg <= 1) return; RandIter pos = partition(beg, end); QuickSort1(beg, pos); QuickSort1(pos + 1, end); } tempalte<class RandIter> void QuickSort2(RandIter beg, RandIter end) { std::stack<std::pair<RandIter> > stk; stk.push({beg, end}); while (!stk.empty()) { std::pair<RandIter, RandIter> ii = stk.top(); stk.pop(); if (ii.second - ii.first) > 1) { RandIter pos = partition(beg, end); stk.push({ii.first, pos}); stk.push({pos + 1, ii.second}); } } } |
- Frame 中必须包含返回地址的递归，这个比较复杂，所以我写了个完整的示例：
- 以MergeSort为例，因为 MergeSort 是个后序过程，两个递归调用中没有任何一个是尾递归
- MergeSort3 使用了 GCC 的 Label As Value 特性，只能在 GCC 兼容的编译器中使用
- 单纯对于这个实例来说，返回地址其实只有两种，返回地址为 0 的情况可以通过判断私有栈(varname=stk)是否为空，stk为空时等效于 retaddr == 0。如果要精益求精，一般情况下指针的最低位总是0，可以把这个标志保存在指针的最低位，当然，如此的话就无法对 sizeof(T)==1 的对象如 char 进行排序了。
-
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202#include <stdio.h>#include <string.h># if 1#include <stack>#include <vector>template<class T>class MyStack : public std::stack<T, std::vector<T> >{};#elsetemplate<class T>class MyStack {union {char* a;T* p;};int n, t;public:explicit MyStack(int n=128) {this->n = n;this->t = 0;a = new char[n*sizeof(T)];}~MyStack() {while (t > 0)pop();delete[] a;}void swap(MyStack<T>& y) {char* q = y.a; y.a = a; a = q;int z;z = y.n; y.n = n; n = z;z = y.t; y.t = t; t = z;}T& top() const {return p[t-1];}void pop() {--t;p[t].~T();}void push(const T& x) {x.print(); // debugp[t] = x;++t;}int size() const { return t; }bool empty() const { return 0 == t; }bool full() const { return n == t; }};#endiftemplate<class T>struct Frame {static T* base;T *beg, *tmp;int len;int retaddr;Frame(T* beg, T* tmp, int len, int retaddr): beg(beg), tmp(tmp), len(len), retaddr(retaddr){}void print() const { // for debugprintf("%4d %4d %d/n", int(beg-base), len, retaddr);}};template<class T> T* Frame<T>::base;#define TOP(field) stk.top().fieldtemplate<class T>bool issorted(const T* a, int n){for (int i = 1; i < n; ++i) {if (a[i-1] > a[i]) return false;}return true;}template<class T>void mymerge(const T* a, int la, const T* b, int lb, T* c) {int i = 0, j = 0, k = 0;for (; i < la && j < lb; ++k) {if (b[j] < a[i])c[k] = b[j], ++j;elsec[k] = a[i], ++i;}for (; i < la; ++i, ++k) c[k] = a[i];for (; j < lb; ++j, ++k) c[k] = b[j];}template<class T>void MergeSort1(T* beg, T* tmp, int len) {if (len > 1) {int mid = len / 2;MergeSort1(beg , tmp , mid);MergeSort1(beg+mid, tmp+mid, len-mid);mymerge(tmp, mid, tmp+mid, len-mid, beg);memcpy(tmp, beg, sizeof(T)*len);}else*tmp = *beg;}template<class T>void MergeSort2(T* beg0, T* tmp0, int len0) {int mid;int cnt = 0;Frame<T>::base = beg0;MyStack<Frame<T> > stk;stk.push(Frame<T>(beg0, tmp0, len0, 0));while (true) {++cnt;if (TOP(len) > 1) {mid = TOP(len) / 2;stk.push(Frame<T>(TOP(beg), TOP(tmp), mid, 1));continue;L1:mid = TOP(len) / 2;stk.push(Frame<T>(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid, 2));continue;L2:mid = TOP(len) / 2;mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));} else*TOP(tmp) = *TOP(beg);int retaddr0 = TOP(retaddr);stk.pop();switch (retaddr0) {case 0: return;case 1: goto L1;case 2: goto L2;}}}// This Implementation Use GCC's goto saved label value// Very similiar with recursive versiontemplate<class T>void MergeSort3(T* beg0, T* tmp0, int len0) {MyEntry:int mid;int retaddr;Frame<T>::base = beg0;MyStack<Frame<T> > stk;stk.push(Frame<T>(beg0, tmp0, len0, 0));#define Cat1(a,b) a##b#define Cat(a,b) Cat1(a,b)#define HereLabel() Cat(HereLable_, __LINE__)#define RecursiveCall(beg, tmp, len) /stk.push(Frame<T>(beg, tmp, len, (char*)&&HereLabel() - (char*)&&MyEntry)); /continue; /HereLabel():;//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~// retaddr == 0 是最外层的递归调用，// 只要到达这一层时 retaddr 才为 0,// 此时就可以返回了#define MyReturn /retaddr = TOP(retaddr); /stk.pop(); /if (0 == retaddr) { /return; /} /goto *((char*)&&MyEntry + retaddr);//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~while (true) {if (TOP(len) > 1) {mid = TOP(len) / 2;RecursiveCall(TOP(beg), TOP(tmp), mid);mid = TOP(len) / 2;RecursiveCall(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid);mid = TOP(len) / 2;mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));} else*TOP(tmp) = *TOP(beg);MyReturn;}}template<class T>void MergeSortDriver(T* beg, int len, void (*mf)(T* beg_, T* tmp_, int len_)){T* tmp = new T[len];(*mf)(beg, tmp, len);delete[] tmp;}#define test(a,n,mf) /memcpy(a, b, sizeof(a[0])*n); /MergeSortDriver(a, n, &mf); /printf("sort by %s:", #mf); /for (i = 0; i < n; ++i) printf("% ld", a[i]); /printf("/n");int main(int argc, char* argv[]){int n = argc - 1;int i;long* a = new long[n];long* b = new long[n];for (i = 0; i < n; ++i)b[i] = strtol(argv[i+1], NULL, 10);test(a, n, MergeSort1);test(a, n, MergeSort2);test(a, n, MergeSort3);printf("All Successed/n");delete[] a;delete[] b;return 0;}
怎么减少错误的发生
错误，我们暂且仅对软件开发而言。
错误的类别，暂且仅考虑接口错误和实现错误。
- 接口错误
- 一般可以分为误解和失配
- 误解
比如在一段公路入口有巨大的标识牌，上面写着：前方道路，靠左行，红灯行，绿灯停。这个大家可能觉得很荒谬，然而类似的事情在软件开发里面却层出不穷，生产方认为自己已经在文档中清楚地说明了用法和用途，然而他却没有意识到这与使用方的常识和惯例背道而驰。举个简单的例子，C 标准库里面的两个函数：
|
1 2 3 4 |
#include <stdio.h> size_t fwrite(const void * ptr, size_t size, size_t count, FILE * stream); #include <stdlib.h> void qsort(void * base, size_t num, size_t size, int (* comparator)(const void *, const void *) ); |
我不知道有多少人用过这两个函数，但是，大体上，应该是用 fwrite 的人多，而用 qsort 的人少。而用 fwrite 的人，大多数情况下，传递的 size 都等于 1，并且，一般情况下，size 和 count 搞反了也不会有啥大问题，除非判断了返回值。然而，一旦用多了 fwrite，并且吧 ObjectSize, ObjectCount 这个顺序当成了一个常识，再使用 qsort 的时候，就悲剧了！
还有一个例子：stl 的 range，一般表示为前闭后开的 [begin, end) 区间，如果你要搞一个前开后闭的 (begin, end] 区间，大家都会疯掉不可。我确实曾经被这样的 (begin, end] 疯掉过。
-
- 失配
一般情况下，发生在版本兼容问题上。我仅举一个简单例子：在Bash3.x中，[[]] 中的正则表达式会按Bash的quoting removal 规则进行处理，也就是说对于一般的正则表达式，加单引号，双引号，和不加引号，都没有区别，然而到了Bash4.x，如果加了引号，就悲剧了！Bash4.x会把引号当成正则表达式的一部分！
-
- 另一种接口错误
最近我在挤地铁时发现了另一类错误，看上去似乎不属于这两种：人很挤的时候，在地铁楼梯上，经常发现，人们走的是左边，而不是右边，稍微用心一下，就会发现这是什么原因——人们总是按贪心算法走最短路径，刚下地铁的人，会走挨地铁（车厢）的楼梯一侧，而这一侧正好是左边，上面往下走的人，却是走右边。在人流量不大的时候，这不是什么问题，然而，当人流汹涌时，造成的拥堵让大家都很郁闷。
怎么解决这个问题呢？——那就是在设计地铁站时，让贪心算法的最短路径是右边，而不是左边。再General一点，就是：设计要遵守人们的思维习惯。
在程序设计上，如果我们设计的接口符合人的思维习惯，可以大大减少错误的发生。在 C 里面，至少有两处设计违反人的直觉，不过还好，这两处早被 deprecate 了：
-
-
- 函数的默认返回值为 int，而非 void
- f() 表示可接受任意个参数，返回值为 int 的函数。
-
- 实现错误
一般情况下，就是指我们程序的逻辑错误
C++ 如何动态库实现接口兼容
看了一篇文章：避免使用虚函数作为库的接口
其中提到C++虚表的僵硬，导致版本更新时二进制兼容性的问题。
其实这个问题不是C++的问题，而是C++实现的问题。如果接口的二进制兼容性是一个强制需求，在不影响运行效率的情况下，C++是完全可以实现的，不过需要多一点的空间开销和初始化开销。
具体的方法可以参考 PE 文件中的 Import Table 和 Export Table。
简单地讲，就是 App 和 DLL 各自维护一个 name->func_address 的映射数组，当然，这个 name 应该是名字碾碎后的 name 。 加载 DLL 时，将 DLL 中 Export Table 中相应项填到 App 中相应的 Import Table 中，App 中的虚函数调用仍然到那个地方去取函数指针，但是对不同版本的 DLL，甚至是不同实现的 DLL，那个值是不同的，这没有任何问题。
具体的算法，在 PE 文件中，Import Table 中的项一般比相应 DLL 的 Export Table 项少得多，所以，它使用二分查找（当然，它还有很多优化，如 hint, by ordinal，bound import 等等）。对于虚函数的情形，因为 Import 和 Export 的项数差不多，使用 Merge 算法会更快一点。
以前在做嵌入式系统的时候，会把绝大部分函数都放到查找表中，也是类似的道理，因为 ROM 最便宜，然而 ROM 是 Read Only Memory，release 之后，客户买到产品，要修改怎么办？还好，系统中不是光有ROM，还要少量 EEPROM，于是，事情就好办了，查找表和 Fix 的新代码，都可以放到 EEPROM 中，只需要在更新系统时将 Fix 的新函数地址填入查找表中相应的位置。
如果C++哪天要统一abi，这样的东西应该是必不可少的。