Dec
28
注：本文只是简单介绍这三个东西并对比一下其功能、差异，不讨论这些东西是否有存在的必要以及优劣。
· goto
· setjmp, longjmp
· try-catch
一、看看基本的使用
1. goto
这个比较简单，比较容易理解，只要设置一个行标就行了：
例子：
2. setjmp, longjmp
goto用起来是简单，但是存在一个先天缺陷：只能在同一个函数内使用。
有时候我们写一个代码，有两三层的函数嵌套，想要返回的时候就比较囧。
这时候用setjmp和longjmp就很happy。
例子：
输出是:
Hi, I'm foo!
Hi, I'm bar!
i = 1
3. try-catch （在这里算是歪用了，呵呵）
这个是c++提供的语言特性，可以用于捕获throw语句抛出的异常，不仅可以在函数内使用，也可以跨函数～～
例子：
输出是：
Hi, I'm foo!
Hi, I'm bar!
i = 1
二、简单对比一下：
· goto，使用简单方便，看起来比其他两个更容易一点（有行标），但是只能在函数内跳转；
· setjmp和longjmp，稍微麻烦点，需要带个参数(jmp_buf，全局变量，或者传参)，好处是可以跨函数跳转，且可以根据setjmp的返回值得知从何处跳转。还有一个小缺陷就是，因为需要先执行setjmp以后才可以跳转，所以可以跳转的地方有一定限制，也使得代码看起来有点不够清晰。
· try-catch，C++有C没有，看起来结构比较清晰，不需要带额外的参数，抛出不同的值（和类型）方便判断来源。
三、重点考察一个问题：
如果有一个class，比如
所以在使用这三个东西的时候，一定要特别注意，建议在C++里头不使用setjmp，以免查错无门...
· goto
· setjmp, longjmp
· try-catch
一、看看基本的使用
1. goto
这个比较简单，比较容易理解，只要设置一个行标就行了：
例子：
int main ()
{
int i = 0, sum;
for (i = 0; i < 100; ++i) {
sum += i;
if (sum > 1000) goto JMP1;
}
JMP1:
printf("%d\n", i);
return 0;
}
{
int i = 0, sum;
for (i = 0; i < 100; ++i) {
sum += i;
if (sum > 1000) goto JMP1;
}
JMP1:
printf("%d\n", i);
return 0;
}
2. setjmp, longjmp
goto用起来是简单，但是存在一个先天缺陷：只能在同一个函数内使用。
有时候我们写一个代码，有两三层的函数嵌套，想要返回的时候就比较囧。
这时候用setjmp和longjmp就很happy。
例子：
#include <setjmp.h>
jmp_buf jmpbuf1;
void bar() {
printf("Hi, I'm bar!\n");
longjmp(jmpbuf1, 1);
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
int i = 0;
i = setjmp(jmpbuf1);
if (i == 0) { //setjmp第一次某个jmp_buf的时候返回0
foo();
}
else { //否则返回longjmp给出的值
printf("i = %d\n", i);
}
return 0;
}
jmp_buf jmpbuf1;
void bar() {
printf("Hi, I'm bar!\n");
longjmp(jmpbuf1, 1);
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
int i = 0;
i = setjmp(jmpbuf1);
if (i == 0) { //setjmp第一次某个jmp_buf的时候返回0
foo();
}
else { //否则返回longjmp给出的值
printf("i = %d\n", i);
}
return 0;
}
输出是:
Hi, I'm foo!
Hi, I'm bar!
i = 1
3. try-catch （在这里算是歪用了，呵呵）
这个是c++提供的语言特性，可以用于捕获throw语句抛出的异常，不仅可以在函数内使用，也可以跨函数～～
例子：
void bar() {
printf("Hi, I'm bar!\n");
throw 1;
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
try{
foo();
}
catch(int i) {
printf("i = %d\n", i);
}
return 0;
}
printf("Hi, I'm bar!\n");
throw 1;
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
try{
foo();
}
catch(int i) {
printf("i = %d\n", i);
}
return 0;
}
输出是：
Hi, I'm foo!
Hi, I'm bar!
i = 1
二、简单对比一下：
· goto，使用简单方便，看起来比其他两个更容易一点（有行标），但是只能在函数内跳转；
· setjmp和longjmp，稍微麻烦点，需要带个参数(jmp_buf，全局变量，或者传参)，好处是可以跨函数跳转，且可以根据setjmp的返回值得知从何处跳转。还有一个小缺陷就是，因为需要先执行setjmp以后才可以跳转，所以可以跳转的地方有一定限制，也使得代码看起来有点不够清晰。
· try-catch，C++有C没有，看起来结构比较清晰，不需要带额外的参数，抛出不同的值（和类型）方便判断来源。
三、重点考察一个问题：
如果有一个class，比如
class T
{
public:
~T() { printf("I'm dead >_<\n"); }
};
那么使用goto、setjmp或try-catch的时候是否存在问题？{
public:
~T() { printf("I'm dead >_<\n"); }
};
if (1) {
T t1;
goto JMP1;
}
JMP1: ;
有输出I'm dead >_<T t1;
goto JMP1;
}
JMP1: ;
jmp_buf jmpbuf1;
if (setjmp(jmpbuf1) == 0) {
T t1;
longjmp(jmpbuf1, 1);
}
else {
;
}
无输出if (setjmp(jmpbuf1) == 0) {
T t1;
longjmp(jmpbuf1, 1);
}
else {
;
}
try {
T t1;
throw 1;
}
catch(int i) {
;
}
有输出I'm dead >_<T t1;
throw 1;
}
catch(int i) {
;
}
所以在使用这三个东西的时候，一定要特别注意，建议在C++里头不使用setjmp，以免查错无门...
Dec
26
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
int main ()
{
time_t t1 = time(NULL);
P(ld, t1);
struct timeval tv1;
gettimeofday(&tv1, NULL);
Ps(ld, &tv1, tv_sec);
Ps(ld, &tv1, tv_usec);
/*
* //t1 += 8 * 3600;
* struct tm *tm1 = gmtime(&t1); //标准时间
*/
struct tm *tm1 = localtime(&t1); //本地时间
Ps(d, tm1, tm_sec);
Ps(d, tm1, tm_min);
Ps(d, tm1, tm_hour);
Ps(d, tm1, tm_mday);
Ps(d, tm1, tm_mon+1); //0-based
Ps(d, tm1, tm_year+1900); //从1900年开始, 0-based
allocs(tm2, tm, 1);
tm2->tm_sec = 0;
tm2->tm_min = 0;
tm2->tm_hour= 0;
tm2->tm_mday= 1;
tm2->tm_mon = 0;
tm2->tm_year= 70;
tm2->tm_isdst = 0;
time_t t2 = mktime(tm2);
//t2 += 3600 * 8; //mktime是本地时间
P(ld, t2);
P(s, asctime(tm1)); //标准时间
P(s, ctime(&t1)); //本地时间
alloc(buf, char, 100);
strftime(buf, 100, "%Y-%m-%d %H:%M:%S", tm1); //标准时间
P(s, buf);
strftime(buf, 100, "%F %T", tm1); //标准时间, 格式和上面的一样
P(s, buf);
return 0;
}
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
int main ()
{
time_t t1 = time(NULL);
P(ld, t1);
struct timeval tv1;
gettimeofday(&tv1, NULL);
Ps(ld, &tv1, tv_sec);
Ps(ld, &tv1, tv_usec);
/*
* //t1 += 8 * 3600;
* struct tm *tm1 = gmtime(&t1); //标准时间
*/
struct tm *tm1 = localtime(&t1); //本地时间
Ps(d, tm1, tm_sec);
Ps(d, tm1, tm_min);
Ps(d, tm1, tm_hour);
Ps(d, tm1, tm_mday);
Ps(d, tm1, tm_mon+1); //0-based
Ps(d, tm1, tm_year+1900); //从1900年开始, 0-based
allocs(tm2, tm, 1);
tm2->tm_sec = 0;
tm2->tm_min = 0;
tm2->tm_hour= 0;
tm2->tm_mday= 1;
tm2->tm_mon = 0;
tm2->tm_year= 70;
tm2->tm_isdst = 0;
time_t t2 = mktime(tm2);
//t2 += 3600 * 8; //mktime是本地时间
P(ld, t2);
P(s, asctime(tm1)); //标准时间
P(s, ctime(&t1)); //本地时间
alloc(buf, char, 100);
strftime(buf, 100, "%Y-%m-%d %H:%M:%S", tm1); //标准时间
P(s, buf);
strftime(buf, 100, "%F %T", tm1); //标准时间, 格式和上面的一样
P(s, buf);
return 0;
}
Dec
26
写代码的时候总是觉得printf打起来很麻烦，malloc的强制转换和sizeof很罗嗦，写几个宏，方便多了
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
Dec
13
由于上次和slyar同学提起这个问题，所以才想着还是自己再写一下，而且其实还有自己没解决的问题，希望能抛砖引玉。
剧透
本篇未解决的问题是：在n个数字里面，如果只有3个数字是没有凑对的，能否用O(n)的方法找出来？超过3个又远小于n个的情况呢？
===
WOJ上有2道连在一起的题目，很赞。
找不同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203
找不同：给你n*2+1个数，其中有n对是一样的，让你找出没有相同数字的那一个（真寂寞）。
如果我们能把所有的数字按大小排序，那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况，就是找到寂寞数字了时候。
可是这样效率太低，就算用基数排序，那个常数也是够大的。
换个思路，由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说，按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0，且该操作是可交换的。
所以如果我们将所有数字串起来异或，其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0，最后异或的结果就是最寂寞的那个。。
找相同：有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明，如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab，如果a，b相同，放回去，如果a，b不同，都舍弃】直到剩下来的所有数字都相同（这一定是可以达到的）。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的，用栈。伪码如下
如果有同学看看1204的话，就会知道，这题是
继续找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述：有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别，多了一种情况就是，有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了，但是只要稍微想想，其实还是很容易的：
用上面的方法处理前1～n-1个数字，到了最后一个数字的时候，看看和栈里面那个数字是不是一样
如果一样，说明这个数字出现了超过一半次，输出
如果不一样，那么栈里肯定只剩下一个数字，能出现一半次的，肯定是这两个数字之一，重新扫一次数组就行了。
WOJ关于找相同和不同的貌似就只有三道题，但是“继续”其实还没完。
继续找不同：有2n个数字，其中2n-2个数字是两两凑对的，剩下两个数字很寂寞，请找出来。
这题和前面的找不同也很像，解决方法是可以“复用”的。
以前的一篇日志里面有：http://www.felix021.com/blog/read.php?1243
解法是momodi给出的，将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B，不符合要求)
然后扫描C的每一bit，如果bit[k] == 1，那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A，然后A ^ C = B
这种解法也是O(n)的，只需要扫描两遍，还是比较快的。
-------------------------------------
最后，重点：
如果是3个数，或者更多一些，有没有O(n)的解法？
当然，用O(n)的基数排序处理以后再遍历，的确是O(n)的效率，但是就是效率太低了，而且需要多次遍历。
假设数字的量超过1000亿，需要存放在硬盘中（也就是扫描次数越少越好），这该怎么办呢？
心里已经有些想法了，不过暂时不想写出来，再想想明白。
如果哪位大牛有好的想法，希望互相交流一下:)
剧透
本篇未解决的问题是：在n个数字里面，如果只有3个数字是没有凑对的，能否用O(n)的方法找出来？超过3个又远小于n个的情况呢？
===
WOJ上有2道连在一起的题目，很赞。
找不同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203
找不同：给你n*2+1个数，其中有n对是一样的，让你找出没有相同数字的那一个（真寂寞）。
如果我们能把所有的数字按大小排序，那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况，就是找到寂寞数字了时候。
可是这样效率太低，就算用基数排序，那个常数也是够大的。
换个思路，由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说，按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0，且该操作是可交换的。
所以如果我们将所有数字串起来异或，其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0，最后异或的结果就是最寂寞的那个。。
找相同：有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明，如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab，如果a，b相同，放回去，如果a，b不同，都舍弃】直到剩下来的所有数字都相同（这一定是可以达到的）。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的，用栈。伪码如下
init stack(s)
for x in a[1..n]
if empty(s) or s.top() == x
s.push(x)
else
s.pop()
return s.top()
for x in a[1..n]
if empty(s) or s.top() == x
s.push(x)
else
s.pop()
return s.top()
如果有同学看看1204的话，就会知道，这题是
继续找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述：有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别，多了一种情况就是，有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了，但是只要稍微想想，其实还是很容易的：
用上面的方法处理前1～n-1个数字，到了最后一个数字的时候，看看和栈里面那个数字是不是一样
如果一样，说明这个数字出现了超过一半次，输出
如果不一样，那么栈里肯定只剩下一个数字，能出现一半次的，肯定是这两个数字之一，重新扫一次数组就行了。
WOJ关于找相同和不同的貌似就只有三道题，但是“继续”其实还没完。
继续找不同：有2n个数字，其中2n-2个数字是两两凑对的，剩下两个数字很寂寞，请找出来。
这题和前面的找不同也很像，解决方法是可以“复用”的。
以前的一篇日志里面有：http://www.felix021.com/blog/read.php?1243
解法是momodi给出的，将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B，不符合要求)
然后扫描C的每一bit，如果bit[k] == 1，那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A，然后A ^ C = B
这种解法也是O(n)的，只需要扫描两遍，还是比较快的。
-------------------------------------
最后，重点：
如果是3个数，或者更多一些，有没有O(n)的解法？
当然，用O(n)的基数排序处理以后再遍历，的确是O(n)的效率，但是就是效率太低了，而且需要多次遍历。
假设数字的量超过1000亿，需要存放在硬盘中（也就是扫描次数越少越好），这该怎么办呢？
心里已经有些想法了，不过暂时不想写出来，再想想明白。
如果哪位大牛有好的想法，希望互相交流一下:)
Dec
10
在int32(64位机器则为int64)的范围内的证书作为数组索引来存储数据的话，
在php中，会自动将这种可以转换成int的字符串转换成int作为索引使用。
以下面这一段脚本的输出来说明这个问题：
在php中，会自动将这种可以转换成int的字符串转换成int作为索引使用。
以下面这一段脚本的输出来说明这个问题：
<?php
$arr = array(
123 => 'a',
'123' => 'b',
0123 => 'c',
'0123' => 'd',
);
var_dump($arr);
?>
输出：
array(3) {
[123]=>
string(1) "b" //第一个123的a消失了，却出来了一个b，说明"123"在索引中被当作int处理了，并覆盖了之前123索引对应的值
[83]=> //0123是八进制的83
string(1) "c"
["0123"]=> //字符串
string(1) "d"
}
$arr = array(
123 => 'a',
'123' => 'b',
0123 => 'c',
'0123' => 'd',
);
var_dump($arr);
?>
输出：
array(3) {
[123]=>
string(1) "b" //第一个123的a消失了，却出来了一个b，说明"123"在索引中被当作int处理了，并覆盖了之前123索引对应的值
[83]=> //0123是八进制的83
string(1) "c"
["0123"]=> //字符串
string(1) "d"
}
Nov
22
不解释，就让你看得蛋疼。
#include <iostream>
using namespace std;
class T {
typedef void (T::*Tptr)(void);
Tptr p;
public:
void a() { cout << "a" << endl; }
void b() { cout << "b" << endl; }
void call(Tptr _p) {
p = _p;
(this->*p)();
}
};
int main() {
T t1;
t1.call(&T::a);
t1.call(&T::b);
return 0;
}
using namespace std;
class T {
typedef void (T::*Tptr)(void);
Tptr p;
public:
void a() { cout << "a" << endl; }
void b() { cout << "b" << endl; }
void call(Tptr _p) {
p = _p;
(this->*p)();
}
};
int main() {
T t1;
t1.call(&T::a);
t1.call(&T::b);
return 0;
}
Nov
19
引用
UBB内容为（开头那个下划线不需要加）：
[_table]
l | r | l | c | r
左对齐|右对齐|左对齐|<a href="javascript:alert(12345)">居中啦啦啦</a>|右对齐
1|23|456|7890[newline]1234|0000
abcd|efg|hi|[-]|j
1|[-]|[-]|1|1
[/table]
[_table]
l | r | l | c | r
左对齐|右对齐|左对齐|<a href="javascript:alert(12345)">居中啦啦啦</a>|右对齐
1|23|456|7890[newline]1234|0000
abcd|efg|hi|[-]|j
1|[-]|[-]|1|1
[/table]
效果：
| 左对齐 | 右对齐 | 左对齐 | <a href="javascript:alert(12345)">居中啦啦啦</a> | 右对齐 |
| 1 | 23 | 456 | 7890 1234 |
0000 |
| abcd | efg | hi | j | |
| 1 | 1 | 1 | ||
PHP代码：
function maketbl($str) {
$str = str_replace("<br/>", "\n", $str);
$str = str_replace("|", "|", $str);
$str = trim($str);
$lines = explode("\n", $str);
$firstline = explode("|", trim($lines[0]));
$conf = array();
foreach($firstline as $v) {
switch($v) {
case 'l':
$conf[] = 'left';
break;
case 'r':
$conf[] = 'right';
break;
case 'c':
$conf[] = 'center';
break;
default:
$conf[] = '';
}
}
$ncols = count($conf);
$nline = count($lines);
$ret = '<table cellspacing="0" cellpadding="3" border="1">'. "\n";
for ($i = 1; $i < $nline; $i++) {
$line = trim($lines[$i]);
if (empty($line)) continue;
$line = explode("|", $line);
$ret .= "<tr>\n";
$next = 1;
for ($j = 0; $j < $ncols; $j++) {
if ($line[$j] == "[-]") {
$next++;
continue;
}
$td = $line[$j];
//$td = htmlspecialchars($td);
$td = str_replace("[newline]", "<br/>", $td);
$ret .= <<<eot
<td align="{$conf[$j]}" colspan="{$next}">{$td}</td>
eot;
if ($line[$j] != "[-]") {
$next = 1;
}
}
$ret .= "</tr>\n";
}
$ret .= "</table>";
return $ret;
}
$str = str_replace("<br/>", "\n", $str);
$str = str_replace("|", "|", $str);
$str = trim($str);
$lines = explode("\n", $str);
$firstline = explode("|", trim($lines[0]));
$conf = array();
foreach($firstline as $v) {
switch($v) {
case 'l':
$conf[] = 'left';
break;
case 'r':
$conf[] = 'right';
break;
case 'c':
$conf[] = 'center';
break;
default:
$conf[] = '';
}
}
$ncols = count($conf);
$nline = count($lines);
$ret = '<table cellspacing="0" cellpadding="3" border="1">'. "\n";
for ($i = 1; $i < $nline; $i++) {
$line = trim($lines[$i]);
if (empty($line)) continue;
$line = explode("|", $line);
$ret .= "<tr>\n";
$next = 1;
for ($j = 0; $j < $ncols; $j++) {
if ($line[$j] == "[-]") {
$next++;
continue;
}
$td = $line[$j];
//$td = htmlspecialchars($td);
$td = str_replace("[newline]", "<br/>", $td);
$ret .= <<<eot
<td align="{$conf[$j]}" colspan="{$next}">{$td}</td>
eot;
if ($line[$j] != "[-]") {
$next = 1;
}
}
$ret .= "</tr>\n";
}
$ret .= "</table>";
return $ret;
}
