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

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

代码1:email格式检测
#include <stdio.h>
#include <regex.h>
#include <assert.h>

int main() {
    //分配一个regex_t
    regex_t reg;
    //编译(使用POSIX扩展模式、并忽略大小写),确认编译成功(返回0)
    assert(regcomp(&reg, "^[a-z0-9_]+@([a-z0-9-]+\\.)+[a-z0-9]+$", REG_EXTENDED | REG_ICASE) == 0);
    int ret = regexec(&reg, "steve@rim.jobs", 0, NULL, 0); //执行搜索
    //看看返回值:0表示匹配成功,1表示REG_NOMATCH
    printf("ret = %d, nomatch = %d\n", ret, REG_NOMATCH);
    regfree(&reg); //记得释放空间
}

Oct 30

短代码比赛 不指定

felix021 @ 2012-10-30 17:11 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(4596) | Via 本站原创
比赛的起因是这样的,@Tranch同学在SegmentFault.com提了个问题,求一个代码,可以列出字符串"qwerty"被 "." 分割的所有情况,比如 q.werty qwe.rty q.w.e.r.t.y 等等。

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

int main()
{
    char str[] = "qwerty";
    int i, j;
    for (i = 0; i < (1<<5); i++)
    {
        for (j = 0; j < 5; j++)
        {
            putchar(str[j]);
            if (((i >> j) & 1) == 1)
                putchar('.');
        }
        printf("y\n");
    }
    return 0;
}


不过当时没想写这样的代码,而是特意脑抽用python写了个递归的版本:
def add_dots_l(str):
    ret = []
    for i in range(1, len(str)):
        left  = str[:i]
        right = str[i:]
        ret.append(left + '.' + right)
        ret += [j + '.' + right for j in add_dots_l(left)]
        ret += [left + '.' + j  for j in add_dots_l(right)]
    return set(ret)

因为前一段时间看到 这里用21行python代码实现了一个拼写检查器,于是一时兴起,简化成了这个等价但是更难读的版本:
def add_dots(s):
    r = [s[:i] + '.' + s[i:] for i in range(1, len(s))]
    r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])]
    r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])]
    return set(r)

虽然已经很短了,但是我还是想知道,是否有更简单些的实现(一定程度上可以忽略效率和可读性),于是在MSTC的群里发了这个问题,简单起见,把字符串改成了"abcde",问问有没有更短的代码来给出各种组合。

然后 @杭神 扔了个代码出来,被喷“能不能用人话”。这段代码看起来是有些费解,主要思路是,生成 ['****', '***.', '**..', '*...', '....'] 的各种排列,然后用zip('abcd', p)交错组合起来(再删掉'*'):
from itertools import permutations as p  #itertools.permutations是python2.6引入的
map(lambda p: ''.join(j for i in zip('abcd', p) for j in i).replace('*', '') + 'e', [''.join(y) for x in map(lambda i: set(p('*' * (4-i) + '.' * i)), range(5)) for y in x])

然后 @霄妹纸 说,实际上那个是笛卡尔积。于是用上itertools.product,再改善下语法,可以写成这样,看起来就清晰多了:
from itertools import product  #itertools.product也是2.6引入的
map(lambda p: ''.join(i + j for i, j in zip('abcd', p)) + 'e', product(['.', ''], repeat = 4))

@霄妹纸 还给出了另外两个奇葩的代码,一个是 C 的,充分利用和宏、main函数的参数和递归:
#define z(a,b) printf(#a"%s",(x>>b)&1?".":""),
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}

另一个是ruby的:
p ("b".."e").inject(["a"]){|a,q|a.product [q,"."+q]}.map &:join
如果是ruby 1.9+的话,还可以再少几个字符:
p (?b..?e).inject([?a]){|a,q|a.product [q,?.+q]}.map&:join

由于不懂ruby语法,所以这个代码我也只能勉强看看,不过思路上跟上面的python代码是一样的,使用笛卡尔积生成组合序列,然后再与'abcde'交错组合。

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

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

二进制偶矩阵 不指定

felix021 @ 2012-6-30 22:34 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(7777) | Via 本站原创
这是2012年百度实习招聘非技术类的某道笔试题。

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

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

==== 分割线 ====

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

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

最简单的做法就是
for (i = count = 0; i < 2<<25 - 1; i++) check_even(i) && count++;
这个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有一定的限制。
May 20
从哪儿说起呢?我想了想,从 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 到底做了什么事情呢?它基本上等同于这样几行代码:
char* strncpy(char *dest, const char *src, size_t n){
    size_t i;
    for (i = 0 ; i < n && src[i] != '\0' ; i++)
        dest[i] = src[i];
    for ( ; i < n ; i++)
        dest[i] = '\0';
    return dest;
}

比较诡异的两件事情是:

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

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

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

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

众所皆知,c是为unix而生,所以这就是strncpy的原始目的:定长字符串 的拷贝。对应的代码,很自然地,可以这样写:
strncpy(inode->d_name, filename, 14);

那么如果确实需要一个strcpy的n兄弟版本该怎么办呢?最简单的办法是用snprintf:
snprintf(dest, n, "%s", src);//注意,不能直接用src来替换"%s"

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
Apr 8
翻译自:How To Read C Declarations 英文原文
p.s. 以前还真没注意到这篇文章最后提到的vtable是啥意思……

就算是非常有经验的C程序员,也对那些比简单数组/指针更复杂一些的声明感到头疼。比如说,下面这个是一个指针的数组,还是一个数组的指针?
int *a[10];

下面这货到底是什么?
int (*(*vtable)[])();

当然了,这货是一个指针,指向一个数组,这个数组的每个元素是一个指针,指向一个函数,函数的返回值类型是int  :)

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

== 黄金法则 ==

这个法则是这样说的:
引用
从标识符开始(或者最内层的结构,如果不存在标识符的话,通常出现于函数指针),首先向右看,直到遇到 ) 括号或者结束,看到什么就说出来;然后向左看,直到遇到 ( 括号或者回到行首,看到什么就说出来。跳出一层括号,重复上述过程:右看看,说出来;左看看,说出来。直到你说出变量的类型或者返回值(针对函数指针),也就表示你把声明都读完了。


最简单的情况是这样的:
int i;

从 i 开始,你向右看,啥都没看到;然后就向左看,看到了int,说出来:i是一个int。

然后看个复杂一点的:
int *a[3];

从 a 开始:向右看,说“是一个包含3个元素的数组”;向左看,说“数组的每个元素是指针”;向右看,啥都没;向左看,说“指针指向int”。综合起来就是: a 是一个包含3个元素的数组,每个元素是一个指针,指向int。

加上一对括号让它看起来更怪异点儿:
int (*a)[3];

像在普通表达式中一样,括号改变了阅读/计算的顺序。从 a 开始:向右看,遇到括号了,往回;向左看,说“是一个指针”,遇到(括号,跳出来;向右看,[3],说“指向一个包含3个元素的数组”;向左看,int,说“数组的每个元素是int”。综合起来:a是一个指针,指向一个包含3个元素的数组,数组的每个元素是一个int。

好,再来看看这个:
extern int *foo();

赞,你说:foo是一个函数,返回一个指针,指向int。

接下来跳一步:就像我们可以定义一个指向int的指针,我们也可以定义一个指向函数的指针。在这种情况下,不需要extern了(因为不是函数的前向引用声明),而是一个变量的定义。这是一个基本的函数指针:
int (*foo)();

从foo开始:向右看,遇到括号,往回;向左看,*,说“是一个指针”,遇到左括号,跳出来;向右看,(),说“指向一个函数”;向左看,int,说“函数返回int”。综合起来:foo是一个指针,指向一个函数,函数返回int。

下面是一个数组,每个元素是一个指针,指向函数,函数返回int:
int (*Object_vtable[])();


你还需要最后一个,诡异的难以置信的声明:
int (*(*vtable)[])();

这是一个指针,指向一个数组,数组的每个元素是个指针,指向一个函数,函数的返回值是int。发现了吗?这货就是上面那个object_vtable的指针,也就是你定义的每一个对象需要的虚函数表(vtable)的指针。

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

== 总结 ==

接下来的例子总结了所有C++为了实现多态性所建造的虚函数表需要的所有情形(就像最初的C Front - C++转C翻译器)。
int *ptr_to_int;
int *func_returning_ptr_to_int();
int (*ptr_to_func_returning_int)();
int (*array_of_ptr_to_func_returning_int[])();
int (*(*ptr_to_an_array_of_ptr_to_func_returning_int)[])();
Jan 12

C/C++:内存泄漏 不指定

felix021 @ 2012-1-12 21:58 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(7703) | Via 本站原创
  对于没有GC的语言来说,这实在是最让人头疼的事情了,毕竟内存泄漏是最难处理的问题(之一?),对于一个后台server,即使只是一个小小的泄漏,日积月累,也会导致灾难性的后果。有个传闻说的是,某公司的某下载软件的某后台server,由于有个无法定位的内存泄漏问题,导致服务的内存占用不断增加,以至于只能每隔一段时间重启之。

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

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

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

  假定有一个函数申请了多次内存,那么每次遇到错误需要退出的时候,为了避免内存泄漏,必须将其之前申请的所有内存都释放。所以你也许会看到或者写出过这样蛋疼的程序:
void func(){
    void *a = malloc(sizeof(A));
    if (NULL == a) {
        return;
    }

    void *b = malloc(sizeof(B));
    if (NULL == b) {
        free(a);
        return;
    }

    void *c = malloc(sizeof(C));
    if (NULL == c) {
        free(a);
        free(b);
        return;
    }
    ......
}
  有效,但是不靠谱。当这个函数长达数百行、有多处申请内存的时候,其可维护性是相当低的。当然,使用 alloca 这个非标准的内存分配函数可以在某些情况下解决问题,但是如果申请的内存较大(栈空间不够)、或者分配到的内存被用于较复杂的结构(比如还包含其他资源的指针)、资源不是内存(比如文件指针、锁等同样需要在生命周期结束被释放的资源),alloca就无能为力了。

  于是万恶的goto出场了。为了解决上面的问题,引入goto可以使得每个资源只需要写一份对应的释放代码,例如:
void func(){
    void *a = malloc(sizeof(A));
    if (NULL == a) goto wtf;

    void *b = malloc(sizeof(B));
    if (NULL == b) goto wtf;

    void *c = malloc(sizeof(C));
    if (NULL == c) goto wtf;

    ......

wtf:
    if (a != NULL) free(a);
    if (b != NULL) free(b);
    if (c != NULL) free(c);
}
  看起来很棒对不对?但是实际上并不能通过编译,gcc会提示类似这样的错误:
引用
cross.c:14: error: jump to label ‘wtf’
cross.c:9: error:  from here
cross.c:11: error:  crosses initialization of ‘void* c’
  什么意思呢?假定在第一步,给 a 分配内存的时候失败了,那么还没来得及去定义 b 并给其初始化赋值,就跳转到了wtf这儿,而在wtf下面的第二行,却引用了 b 这个变量,对于编译器而言,这便无法处理了。正确的代码应该是:
void func(){
    void *a = NULL, *b = NULL, *c = NULL;

    a = malloc(sizeof(A));
    if (NULL == a) goto wtf;

    b = malloc(sizeof(B));
    if (NULL == b) goto wtf;

    c = malloc(sizeof(C));
    if (NULL == c) goto wtf;

    ......

wtf:
    if (a != NULL) free(a);
    if (b != NULL) free(b);
    if (c != NULL) free(c);
}
  这样一来便要求所有在 goto 之后被用到的变量都必须在第一个goto之前定义,并赋初值。这就类似c89/pascal的做法了,强制要求所有变量在函数的开头定义,失去了变量就近定义的便捷性和一些其他的好处(sandy的说法是“局部性”,但是窃以为变量的就近定义跟局部性关系不大,更多的是在C++中,对象的就近定义可以在一些情况下避免不必要的初始化,并且可能需要之前的一些处理结果)。这儿有个更复杂的例子,作者指出,在驱动/linux内核中大量使用了这种方式来释放资源。注意,稍有不同的是,这个例子有多种资源,函数末尾有多个label,按照资源申请顺序的倒序释放资源(为什么呢,看代码吧~)

  对变量就近定义的好坏见仁见智了,但是goto毕竟不是个好东西,所以看过内核代码的同学可能会发现另外一种替代性的结构:do-while(0) 。乍一看这个结构似乎没有意义,有点奇怪,但是却很好用,很适合用来消除goto语句,例如上面的代码可以这么做:
void func(){
    void *a = NULL, *b = NULL, *c = NULL;

    do {
        a = malloc(sizeof(A));
        if (NULL == a) break;

        b = malloc(sizeof(B));
        if (NULL == b) break;

        c = malloc(sizeof(C));
        if (NULL == c) break;

        ......

    } while (0);

wtf:
    if (a != NULL) free(a);
    if (b != NULL) free(b);
    if (c != NULL) free(c);
}
  既消除了“不法分子”,也达到了避免冗余的目的。对于这个结构,其实还有更多的好处,详见这里

  但是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的使用:
class Mutexer {
    private:
        pthread_mutex_t *mutex;
    public:
        Mutexer(pthread_mutex_t *m) { mutex = m; }
        ~Mutexer() { Unlock(); }
        Lock() { pthread_mutex_lock(mutex); }
        Unlock() { pthread_mutex_unlock(mutex); }
};

//Global mutex
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void func() {
    Mutexer mtx(&mutex);
    mtx::lock();
    if (sth. failed) {
        return;
    }
}

  不过程序中因为各种原因常需要使用 new 来分配资源(内存、对象等),这样对应的指针还是得在其生命周期结束的时候被释放,总不能为每一个指针再封装一个struct吧。幸而C++的泛型在这里又为RAII提供了绝佳的方法。实际上在第一版STL里面就包含了一个 auto_ptr 容器,实例化一个auto_ptr的时候可以赋予一个任意类型指针ptr(但是必须是使用new获得的,特别注意:new[]分配的不行),auto_ptr对象将ptr包装起来,并重载了 * 和 -> 两个操作符,使得该对象能像指针一样被使用,并且在该对象被生命周期的时候,其析构函数会delete ptr。 下面是auto_ptr的一个简单实现和使用:
template <typename T>
class x_ptr
{
    private:
        T* x;
    public:
        typedef T ele_type;
        explicit x_ptr(T* _x): x(_x) {}
        ~x_ptr() { delete x; }

        T & operator * () { return *x; }
        T * operator ->() const { return x; }
};

void func(){
    x_ptr<int> p(new int);
    *p = 3;
}
  代码的最后无需显式调用 delete 需释放分配的那个int,却照样避免了内存的泄漏。

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

  本来计划写到这里要告一段落了,但是上面的 x_ptr 有坑,无奈只好继续……为什么说有坑呢?举两个例子:
void func1() {
    x_ptr<int> p(new int), q(new int);
    *p = 1;
    *q = 2;
    p = q;
}

void func2() {
    x_ptr<int> p(new int[10]);
}
  在 func1 中,由于进行了拷贝(其实拷贝构造也一样),导致 p 对应的那块空间会被泄漏,而 q 对应的那块空间会被释放2次;在 func2 中,x_ptr试图用delete去释放由new[]分配的内存空间,其结果是未定义的(比如不是基本元素而是某个class,程序可能会直接崩溃)。

  针对func1的问题,可以通过私有化其拷贝函数、拷贝构造函数来禁止x_ptr的拷贝,代码如下
template <typename T>
class x_ptr
{
    private:
        T* x;
        x_ptr(const x_ptr&);
        x_ptr& operator= (const x_ptr& v);
    public:
        typedef T ele_type;
        explicit x_ptr(T* _x): x(_x) {}
        ~x_ptr() { delete x; };

        T & operator * () { return *x; }
        T * operator ->() const { return x; }
};

  而针对func2的问题,解决方法呢,要么是写一个x_ptr_arr,使用delete[]来处理;要么是在x_ptr的构造函数里加一个flag,用来指定是否是new[]分配的,当然,为了方便,可以设置一个默认值false.....

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

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

FILL YOUR DISK 不指定

felix021 @ 2011-12-23 14:38 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(6794) | Via 本站原创
这程序写了好几次了,干脆贴出来吧~附上exe。
#include <stdio.h>
#include <stdlib.h>

char str[65536];

int main() {
    int i;
    for (i = 0; i < 65536; i++) str[i] = '1';
    str[65535] = '\0';
    i = 0;
    while (1) {
        i++;
        if (i % 3000 == 0) {
            sleep(1);
        }
        puts(str);
    }
    return 0;
}
下载文件 (已下载 1632 次)
Nov 15
@2019-03-19 STL里的lowerbound算法简单有效。

该元素在数组中不一定存在,只是要找一个i,使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
//区间是 [s, e),左闭右开,类似STL。
int binsearch(int arr[], int t, int s, int e)
{
    int left = s, right = e, mid;
    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] == t)
            return mid;
        else if (arr[mid] < t)
        {
                //right most    OR ...right here
            if (mid + 1 >= right || t < arr[mid + 1])
                return mid;
            else
                left = mid + 1;
        }
        else /* arr[mid] > t */
        {      //left most    OR ...right here
            if (mid - 1 < left || arr[mid - 1] <= t)
                return mid - 1;
            else
                //11.18.DELETED: right = mid - 1;
                right = mid; //[11.18.update]发现这里是个BUG……
        }
    }
    return -2; //bad range
}
分页: 4/23 第一页 上页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]