Felix021

C/C++标准里头都没有正则表达式，C++还好，可以用上boost::regex，C的话，最简单的还是用系统自带的正则库了。

这个正则库真是相当简单，如果不关心内部琐碎的细节，实际上它只有2个类型、4个函数和7个常量，详细的后面会列出来（或者直接man regex），这里还是直接看例子比较实在：

代码1：email格式检测

比赛的起因是这样的，@Tranch同学在SegmentFault.com提了个问题，求一个代码，可以列出字符串"qwerty"被 "." 分割的所有情况，比如 q.werty qwe.rty q.w.e.r.t.y 等等。

这个问题其实很简单，qwerty中间最多可以塞5个". "，每个地方用1表示塞，0表示不塞，也就是正好循环 2^5 次就行了（对于全0的情况不做特别要求，可有可无），实现起来也非常容易，这里是写这篇文章时补充的一个C语言实现：

不过当时没想写这样的代码，而是特意脑抽用python写了个递归的版本:
因为前一段时间看到 这里用21行python代码实现了一个拼写检查器，于是一时兴起，简化成了这个等价但是更难读的版本：
虽然已经很短了，但是我还是想知道，是否有更简单些的实现（一定程度上可以忽略效率和可读性），于是在MSTC的群里发了这个问题，简单起见，把字符串改成了"abcde"，问问有没有更短的代码来给出各种组合。

然后 @杭神 扔了个代码出来，被喷“能不能用人话”。这段代码看起来是有些费解，主要思路是，生成 ['****', '***.', '**..', '*...', '....'] 的各种排列，然后用zip('abcd', p)交错组合起来（再删掉'*'）：
然后 @霄妹纸 说，实际上那个是笛卡尔积。于是用上itertools.product，再改善下语法，可以写成这样，看起来就清晰多了：
@霄妹纸 还给出了另外两个奇葩的代码，一个是 C 的，充分利用和宏、main函数的参数和递归：
另一个是ruby的:如果是ruby 1.9+的话，还可以再少几个字符：
由于不懂ruby语法，所以这个代码我也只能勉强看看，不过思路上跟上面的python代码是一样的，使用笛卡尔积生成组合序列，然后再与'abcde'交错组合。

结果是，ruby赢了（58个字节），python紧随其后（80字节，不包括import），C语言则意外地以106个字节的代码实现了这个目标。

这个问题从实践的角度上来说没有太大意义，不过可以对比下，不同的语言（C/Ruby/Python）、不同的编程范型（过程式/函数式）的表达方式，一窥函数式编程的魅力～

这是2012年百度实习招聘非技术类的某道笔试题。

给一个5×5的矩阵，每个元素只能是0或者1。

请问，有多少种不同的矩阵，能够满足每一行、每一列都有偶数个1？

==== 分割线 ====

乍看这个题目，觉得是数学题。画了个5*5的矩阵，试图填几个数字进去看看是否可以推出一些结论。果断失败。

然后想了下，这题如果枚举的话，也就是2的25次方，大约3200万这个规模，不是很夸张。于是决定暴力搞一下。

最简单的做法就是这个check_even(i)里头把 i 当成一个25bit的二进制数字，并转换为对应的5*5矩阵，判断其每一行和每一列是否满足要求。（p.s. whusnoopy的做法是直接使用位运算，更简单，不过思路就断了。。）

一个不难想到的优化是，在for之前先把每一行给枚举了，这样就不需要在check_even里面每次进行转换，只需要从 i 中取出对应的bits，就可以直接找到每一行。

更进一步，由于题目要求每一行都是偶数个1，所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了，枚举出5行，然后判断每个列。很容易计算，每行5个bit，偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。

再进一步剪枝——题目要求所以列是偶数，那么在已经确定前4行的情况下，第5行是可以直接推出来的，需要枚举的矩阵数量降至16^4。但还需要做的事情是，判断第5行是否有偶数个1。

到了这一步，豁然开朗——因为很容易证明，第5行必然是偶数个1：
  1) 每一列都是偶数个1（ABCDE都是偶数），所以矩阵中必然有偶数个1（F=A+B+C+D+E为偶数）
  2) 前4行都是偶数个1（HIJK都是偶数），所以第5行必然是偶数个1（L=F-H-I-J-K为偶数）
  (p.s. 这个证明是WHUMSTC群里某同学给出的，非常清晰，所以我就不给我自己那个很挫的证明过程了）

于是开头的直觉获胜，问题的答案就是：16^4，也就是(2^4)^4。

==== 分割线 ====

扩展：

1. 如果矩阵的大小是 N×N ，甚至是 M×N 呢？

    根据上述结论，很容易推知，对于M*N的矩阵，结果是2^((M-1) * (N-1))。

2. 如果要求满足每一行、每一列都有奇数个1呢？(whusnoopy提出)

    这个结论就不那么直接了，对M*N有一定的限制。

从哪儿说起呢？我想了想，从 gets 说起可能最好。

初学C语言的时候，如果要输入一行字符串，该怎么办？看书，或者找老师，或者找学长，通常得到的答案是gets。用法很简单，似乎也很好用，但是很不幸，这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符，而面对的输入是1万个字符，那么几乎毫无疑问，这个程序是要崩溃的，除非运气特别好，或者……

或者给出的输入是经过精心设计的，例如一段shell code，及其对应的跳转地址。对于常见的计算机体系来说，函数调用时，返回地址是在栈上的，通过精心设计输入，使得溢出数据中的跳转地址好正好覆盖了该返回地址，于是函数在返回时不是如预期般回到调用者处，而是跳转到攻击者给出的shell code处，使得攻击者获得了额外的权限。

这就是典型的溢出攻击。

为了防止这种情况的出现，在C库函数中，许多对字符串操作的函数都有其"n兄弟"版本，例如strncmp，strncat，snprintf……兄弟版本的基本行为不变，但是通常在参数中需要多给出一个整数n，用于限制操作的最大字符数量（本句不够严谨，详情参见各函数的说明）。

这是技术上的解决方案。只是，代码都是人写出来的，总会有对溢出缺乏概念的人，写出令人蛋疼的代码。于是一些公司，例如（听说）腾讯，建立了一套规则，对提交的代码进行扫描，若发现使用了非“n兄弟”版本，就会给对应的码农一定的惩罚措施，从而在管理上降低此类问题出现的可能性。

加强管理当然是好事，但是也给某些有强迫症的码农带来了不便：因为strlen没有n兄弟版本，坑爹啊！事实上，更坑爹的是strcpy，在c语言标准里，它不但没有n兄弟版本，甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。

strncpy 到底做了什么事情呢？它基本上等同于这样几行代码：
比较诡异的两件事情是：

1. 如果src的前n个字符里面没有'\0'，那么它不会在末尾补上这个结束符

2. 如果拷贝的数据不满n个字符，那么它会用 '\0' 在末尾填充

以 strcpy 的行为来理解它，只会感到很蛋疼：第一点很可能会造成此后代码的数组越界访问，而第二点则是对cpu资源的浪费。

事实上，完全是因为历史的原因，造成了这样的误会。在第七版的UNIX文件系统中，每个inode结构体中包含的每个entry（对应文件或下级目录）只有16个字节，其中前两个用于标识inode，剩下的14个用于保存文件名。由于文件名最长只能有14个字符，所以在设计上，末尾不足的字符用'\0'来填充；如果达到14个字符，则不需要结束标志。

众所皆知，c是为unix而生，所以这就是strncpy的原始目的：定长字符串 的拷贝。对应的代码，很自然地，可以这样写：
那么如果确实需要一个strcpy的n兄弟版本该怎么办呢？最简单的办法是用snprintf：
p.s. 其实还有个 strlcpy ，只可惜它是OpenBSD 2.4引入的，并非C标准中的函数，适用范围较窄。

参考资料：
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html

翻译自：How To Read C Declarations 英文原文
p.s. 以前还真没注意到这篇文章最后提到的vtable是啥意思……

就算是非常有经验的C程序员，也对那些比简单数组/指针更复杂一些的声明感到头疼。比如说，下面这个是一个指针的数组，还是一个数组的指针？
下面这货到底是什么？
当然了，这货是一个指针，指向一个数组，这个数组的每个元素是一个指针，指向一个函数，函数的返回值类型是int  :)

这篇短文希望能够教会你一个非常简单地读懂复杂声明的方法。我99%肯定我在80年代读过这篇，但是不记得具体是在什么地方读到的了。我怀疑是我自己发现这个的（尽管我总会被计算机语言结构和神秘的事物搞得很兴奋）。然而我的确记得，能够写出一个程序，将任何声明转换成英语。

== 黄金法则 ==

这个法则是这样说的：

最简单的情况是这样的：
从 i 开始，你向右看，啥都没看到；然后就向左看，看到了int，说出来：i是一个int。

然后看个复杂一点的：
从 a 开始：向右看，说“是一个包含3个元素的数组”；向左看，说“数组的每个元素是指针”；向右看，啥都没；向左看，说“指针指向int”。综合起来就是: a 是一个包含3个元素的数组，每个元素是一个指针，指向int。

加上一对括号让它看起来更怪异点儿：
像在普通表达式中一样，括号改变了阅读/计算的顺序。从 a 开始：向右看，遇到括号了，往回；向左看，说“是一个指针”，遇到(括号，跳出来；向右看，[3]，说“指向一个包含3个元素的数组”；向左看，int，说“数组的每个元素是int”。综合起来：a是一个指针，指向一个包含3个元素的数组，数组的每个元素是一个int。

好，再来看看这个：
赞，你说：foo是一个函数，返回一个指针，指向int。

接下来跳一步：就像我们可以定义一个指向int的指针，我们也可以定义一个指向函数的指针。在这种情况下，不需要extern了（因为不是函数的前向引用声明），而是一个变量的定义。这是一个基本的函数指针：
从foo开始：向右看，遇到括号，往回；向左看，*，说“是一个指针”，遇到左括号，跳出来；向右看，()，说“指向一个函数”；向左看，int，说“函数返回int”。综合起来：foo是一个指针，指向一个函数，函数返回int。

下面是一个数组，每个元素是一个指针，指向函数，函数返回int：

你还需要最后一个，诡异的难以置信的声明：
这是一个指针，指向一个数组，数组的每个元素是个指针，指向一个函数，函数的返回值是int。发现了吗？这货就是上面那个object_vtable的指针，也就是你定义的每一个对象需要的虚函数表(vtable)的指针。

这个指向vtable的指针是一个vtable的地址，例如，&Truck_vtable （就是某个Truck类的实例虚函数表的指针）。

== 总结 ==

接下来的例子总结了所有C++为了实现多态性所建造的虚函数表需要的所有情形（就像最初的C Front - C++转C翻译器）。

　　对于没有GC的语言来说，这实在是最让人头疼的事情了，毕竟内存泄漏是最难处理的问题（之一?），对于一个后台server，即使只是一个小小的泄漏，日积月累，也会导致灾难性的后果。有个传闻说的是，某公司的某下载软件的某后台server，由于有个无法定位的内存泄漏问题，导致服务的内存占用不断增加，以至于只能每隔一段时间重启之。

　　有人说，C/C++程序员有一半的工作量是花在处理内存泄漏上面，但是很遗憾，内存泄漏仍然屡见不鲜。一旦出现泄漏，能做的事情不多，上述处理方式是消极做法之一，有效，但治标不治本。积极一点的，也不外乎这两个：一是看代码，反复看代码，请别人看代码，请别人反复看代码；或是借助valgrind之类的工具来跟踪内存的分配/释放（而且并不适用于所有程序，例如某些程序寄希望于在其终止时让OS来释放那些只需申请一次且无需释放的内存）。一些额外的测试工作也许能帮助缩小查看代码的范围，但也只能这样了。

　　既是如此，在程序运行之前，就应该先把好关。

　　对于C语言，这确实是个比较痛苦的事情。毕竟C语言只是汇编的高级语言封装，语言本身提供的能力很有限。

　　假定有一个函数申请了多次内存，那么每次遇到错误需要退出的时候，为了避免内存泄漏，必须将其之前申请的所有内存都释放。所以你也许会看到或者写出过这样蛋疼的程序：　　有效，但是不靠谱。当这个函数长达数百行、有多处申请内存的时候，其可维护性是相当低的。当然，使用 alloca 这个非标准的内存分配函数可以在某些情况下解决问题，但是如果申请的内存较大（栈空间不够）、或者分配到的内存被用于较复杂的结构（比如还包含其他资源的指针）、资源不是内存（比如文件指针、锁等同样需要在生命周期结束被释放的资源），alloca就无能为力了。

　　于是万恶的goto出场了。为了解决上面的问题，引入goto可以使得每个资源只需要写一份对应的释放代码，例如：　　看起来很棒对不对？但是实际上并不能通过编译，gcc会提示类似这样的错误：　　什么意思呢？假定在第一步，给 a 分配内存的时候失败了，那么还没来得及去定义 b 并给其初始化赋值，就跳转到了wtf这儿，而在wtf下面的第二行，却引用了 b 这个变量，对于编译器而言，这便无法处理了。正确的代码应该是：　　这样一来便要求所有在 goto 之后被用到的变量都必须在第一个goto之前定义，并赋初值。这就类似c89/pascal的做法了，强制要求所有变量在函数的开头定义，失去了变量就近定义的便捷性和一些其他的好处(sandy的说法是“局部性”，但是窃以为变量的就近定义跟局部性关系不大，更多的是在C++中，对象的就近定义可以在一些情况下避免不必要的初始化，并且可能需要之前的一些处理结果）。这儿有个更复杂的例子，作者指出，在驱动/linux内核中大量使用了这种方式来释放资源。注意，稍有不同的是，这个例子有多种资源，函数末尾有多个label，按照资源申请顺序的倒序释放资源（为什么呢，看代码吧～）

　　对变量就近定义的好坏见仁见智了，但是goto毕竟不是个好东西，所以看过内核代码的同学可能会发现另外一种替代性的结构：do-while(0) 。乍一看这个结构似乎没有意义，有点奇怪，但是却很好用，很适合用来消除goto语句，例如上面的代码可以这么做：　　既消除了“不法分子”，也达到了避免冗余的目的。对于这个结构，其实还有更多的好处，详见这里。

　　但是do-while(0)和goto一样，不是万金油，对于很多较复杂的情况也不能很好的解决，甚至会使得程序更加晦涩难懂。对于do-while(0)，如果在这个结构内还有一个循环，循环里面出错想要跳出do-while(0)，break就不奏效了（至于为什么，你懂的），这时代码怎么写都恶心，只能羡慕Java里面的break label语法了；而对于比较复杂的资源，比如上文中申请到的内存是 a->b->c 这样嵌套的，那么如何安排内存释放代码，又要让人头疼了。合理的使用goto/do-while(0)，将过长的代码拆分成多个函数等都可以起到一定的帮助。

　　只是很可惜，C语言的能力大概就只能走到这里了。想走得更远，就得借助C++来完成了。虽然C++没有gc，但是由于其OO的特性，使得RAII的实现变得可能。

　　所谓RAII，即 Resource Acquizition Is  Initialization。很晦涩吧？其实具体实现很简单：把资源封装成一个类，在其构造函数中分配，在析构函数中释放。当需要使用的时候，在栈上初始化一个对象，当这个对象生命周期结束的时候，其析构函数会被调用，自动完成资源的释放。对于前面提到的例子，可以把A/B/C封装成一个class，对应的a/b/c就是实例化得到的三个对象，当func函数结束的时候，abc对应的内存就会被释放。同样的方法也适用于锁、互斥量、文件指针等其他类型的资源。下面这段代码以pthread_mutex为例，演示了RAII的使用:
　　不过程序中因为各种原因常需要使用 new 来分配资源（内存、对象等），这样对应的指针还是得在其生命周期结束的时候被释放，总不能为每一个指针再封装一个struct吧。幸而C++的泛型在这里又为RAII提供了绝佳的方法。实际上在第一版STL里面就包含了一个 auto_ptr 容器，实例化一个auto_ptr的时候可以赋予一个任意类型指针ptr（但是必须是使用new获得的，特别注意：new[]分配的不行），auto_ptr对象将ptr包装起来，并重载了 * 和 -> 两个操作符，使得该对象能像指针一样被使用，并且在该对象被生命周期的时候，其析构函数会delete ptr。 下面是auto_ptr的一个简单实现和使用：　　代码的最后无需显式调用 delete 需释放分配的那个int，却照样避免了内存的泄漏。

　　既然说到auto_ptr，为什么不用它来写例子呢？因为auto_ptr的某些特性导致其有大坑，在很多地方不受待见，以至于在 c++11 标准里，auto_ptr被废弃了，因此不建议在项目中使用它了。有兴趣的同学可以去翻看《C++标准程序库》对auto_ptr的介绍。

　　本来计划写到这里要告一段落了，但是上面的 x_ptr 有坑，无奈只好继续……为什么说有坑呢？举两个例子：　　在 func1 中，由于进行了拷贝（其实拷贝构造也一样），导致 p 对应的那块空间会被泄漏，而 q 对应的那块空间会被释放2次；在 func2 中，x_ptr试图用delete去释放由new[]分配的内存空间，其结果是未定义的（比如不是基本元素而是某个class，程序可能会直接崩溃）。

　　针对func1的问题，可以通过私有化其拷贝函数、拷贝构造函数来禁止x_ptr的拷贝，代码如下
　　而针对func2的问题，解决方法呢，要么是写一个x_ptr_arr，使用delete[]来处理；要么是在x_ptr的构造函数里加一个flag，用来指定是否是new[]分配的，当然，为了方便，可以设置一个默认值false.....

　　补充一句，这里的x_ptr其实是boost::scoped_ptr的缩水版了，有兴趣的同学可以自行Google了解更多，关于内存泄漏的话题，这篇大概就说这么多了吧。

　　最后，感谢Sandy同学的 C++中利用RAII在stack上管理资源I ，本篇有多处参考该文。希望他能抽出时间把 II 给写完吧 :P

这程序写了好几次了，干脆贴出来吧～附上exe。

@2019-03-19 STL里的lowerbound算法简单有效。

该元素在数组中不一定存在，只是要找一个i，使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。