Jan
8
昨天看的《C++标准函数库》，看到auto_ptr这一节，说到了关于内存泄露的问题
而且有些情况以前根本没有考虑到，想想觉得好危险。
典型的情况就是如下的代码：
如果在//do sth.的时候退出了函数，比如一个return语句，或者是抛出了一个异常
那么最后的delete p就不会被执行，于是就造成了内存的泄露。
更极端一点的情况是，可能申请了多个内存，有多处return，如果每一个都要处理，那程序就太恶心了。
但是不处理又是不行的——于是需要有一种方式来解决，于是标准库就引进了auto_ptr 智能指针。
这个东西保证它自己被销毁的时候能够释放其指向的对象(使用delete)。
一个简单的例子是:
在退出函数foo()的时候，p的析构函数会被调用，自动释放它指向的classA，于是再也不用费神去写delete了，真好～
不过auto_ptr不是基于引用计数的智能指针，所以有一些很特殊的属性。
如果想要用它，一定一定要都了解了才用哦！就推荐看这本书《The C++ Standard Library》C++标准函数库。
而且有些情况以前根本没有考虑到，想想觉得好危险。
典型的情况就是如下的代码：
void foo(){
int *p = new int[10];
//do sth.
delete[] p;
}
int *p = new int[10];
//do sth.
delete[] p;
}
如果在//do sth.的时候退出了函数，比如一个return语句，或者是抛出了一个异常
那么最后的delete p就不会被执行，于是就造成了内存的泄露。
更极端一点的情况是，可能申请了多个内存，有多处return，如果每一个都要处理，那程序就太恶心了。
但是不处理又是不行的——于是需要有一种方式来解决，于是标准库就引进了auto_ptr 智能指针。
这个东西保证它自己被销毁的时候能够释放其指向的对象(使用delete)。
一个简单的例子是:
#include<memory> //auto_ptr在头文件memory里面哦
using namespace std::auto_ptr; //它在namespace std里面哦
void foo(){
std::auto_ptr<classA> p(new classA);
//do sth.
//no need to free p;
}
using namespace std::auto_ptr; //它在namespace std里面哦
void foo(){
std::auto_ptr<classA> p(new classA);
//do sth.
//no need to free p;
}
在退出函数foo()的时候，p的析构函数会被调用，自动释放它指向的classA，于是再也不用费神去写delete了，真好～
不过auto_ptr不是基于引用计数的智能指针，所以有一些很特殊的属性。
如果想要用它，一定一定要都了解了才用哦！就推荐看这本书《The C++ Standard Library》C++标准函数库。
Dec
29
被牛逼哄哄的Snoopy雷到了。
事情是这样的，今天打开 http://acm.whu.edu.cn/woj 检查oak的运行情况
发现在status的第二页有好多个submit都处于Running状态
ssh到服务器上去看了一下，发现Judge在Compile OK以后就挂掉了。
有一堆Stack的信息，但是看不太懂~
DEBUG了一阵，定位到了错误：在判断Restricted_Function的那个函数里面。
加入了调试代码以后的大概结构是这样的：
然后发现非常神奇地，程序输出的是
然后跟上一堆程序出现错误的信息。
于是我就懵了，居然一个return语句也能出现错误？
然后请教snoopy大牛，经过一番七荤八素的DEBUG以后，终于找到了症结所在：
原来在Restricted_Function里面定义的那个char f[30]空间太小了
由于是分配在栈空间里面的，所以在运行的时候，出现了少量越界写入的情况
在程序返回的时候，由于返回地址等被未预料到的字符覆盖了，于是就出现了上述问题。
一个return语句也能"出错"，暴露出这样严重的内存使用问题
——可能存在于任何地方，写程序的时候务必要小心啊！
同时，通过这种方式"定位"到的错误点，未必就是错误真正发生的地方！
事情是这样的，今天打开 http://acm.whu.edu.cn/woj 检查oak的运行情况
发现在status的第二页有好多个submit都处于Running状态
ssh到服务器上去看了一下，发现Judge在Compile OK以后就挂掉了。
有一堆Stack的信息，但是看不太懂~
DEBUG了一阵，定位到了错误：在判断Restricted_Function的那个函数里面。
加入了调试代码以后的大概结构是这样的：
......
bool Restricted_Function(){
char f[30], ...;
......
cout << "DEBUG 1" << endl;
return false;
}
......
bool WOJ_JUDGE(){
......
cout << "DEBUG 0“ << endl;
if(Restricted_Function(){
cout << "DEBUG 2" << endl;
return RF;
}
cout << "DEBUG 2" << endl;
......
}
bool Restricted_Function(){
char f[30], ...;
......
cout << "DEBUG 1" << endl;
return false;
}
......
bool WOJ_JUDGE(){
......
cout << "DEBUG 0“ << endl;
if(Restricted_Function(){
cout << "DEBUG 2" << endl;
return RF;
}
cout << "DEBUG 2" << endl;
......
}
然后发现非常神奇地，程序输出的是
引用
DEBUG 0
DEBUG 1
DEBUG 1
于是我就懵了，居然一个return语句也能出现错误？
然后请教snoopy大牛，经过一番七荤八素的DEBUG以后，终于找到了症结所在：
原来在Restricted_Function里面定义的那个char f[30]空间太小了
由于是分配在栈空间里面的，所以在运行的时候，出现了少量越界写入的情况
在程序返回的时候，由于返回地址等被未预料到的字符覆盖了，于是就出现了上述问题。
一个return语句也能"出错"，暴露出这样严重的内存使用问题
——可能存在于任何地方，写程序的时候务必要小心啊！
同时，通过这种方式"定位"到的错误点，未必就是错误真正发生的地方！
Dec
29
#include<iostream>
using namespace std;
char l[] = "Felix021";
void print(char a){
for(int i = 7; i >= 0; --i){
cout << ((a >> i ) & 1);
}
}
int main(){
for(int i = 0; l[i]; ++i){
print(l[i]);
}
cout << endl;
return 0;
}
using namespace std;
char l[] = "Felix021";
void print(char a){
for(int i = 7; i >= 0; --i){
cout << ((a >> i ) & 1);
}
}
int main(){
for(int i = 0; l[i]; ++i){
print(l[i]);
}
cout << endl;
return 0;
}
Dec
7
momodi同学說得很对，嗯。
--
貌似新人们总会遇到几个问题，提一下吧。
1. 64Bit整型的问题
这个东西比较纠结阿。一般来说
在VC下面，定义的时候要用__int64
用g++/gcc的时候，则应该用long long定义
在Windows下面，输入输出的时候要用%I64d这个格式
在类Unix(包括Solaris/Linux等)下面，输入输出的时候要用%lld这个格式
对于各类OJ，不妨自己在A+B这道题上试试
参加比赛的时候，务必向工作人员或者judge问清楚编译环境
——包括操作系统和编译器。
2. 大数组RE的问题
emingCup的时候就有队伍遇到这个问题
自己运行的时候都RE还交过来。
这个涉及到编译器对不同类型变量的内存分配规则。
在C/C++中
--
貌似新人们总会遇到几个问题，提一下吧。
1. 64Bit整型的问题
这个东西比较纠结阿。一般来说
在VC下面，定义的时候要用__int64
用g++/gcc的时候，则应该用long long定义
在Windows下面，输入输出的时候要用%I64d这个格式
在类Unix(包括Solaris/Linux等)下面，输入输出的时候要用%lld这个格式
对于各类OJ，不妨自己在A+B这道题上试试
参加比赛的时候，务必向工作人员或者judge问清楚编译环境
——包括操作系统和编译器。
2. 大数组RE的问题
emingCup的时候就有队伍遇到这个问题
自己运行的时候都RE还交过来。
这个涉及到编译器对不同类型变量的内存分配规则。
在C/C++中
Nov
15
#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
int main(){
vector<int>a;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(a));
sort(a.begin(), a.end());
copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
return 0;
}
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
int main(){
vector<int>a;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(a));
sort(a.begin(), a.end());
copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
return 0;
}
Nov
4
这两天在看密码学的大作业，写一个DES加密程序，里面有很多涉及位运算的东西。
虽然直接用bitset写，但是非常非常地不顺手，于是自己写了一个类，里头有DES需要的运算，恩。
如果谁发现有错的话，麻烦告诉我一声。
好久没有写这样的代码了，一个简单的类居然花了这么久。囧。
虽然直接用bitset写，但是非常非常地不顺手，于是自己写了一个类，里头有DES需要的运算，恩。
如果谁发现有错的话，麻烦告诉我一声。
好久没有写这样的代码了，一个简单的类居然花了这么久。囧。
Nov
1
indent - changes the appearance of a C program by inserting or deleting whitespace.
indent是一个开源的C/C++代码规范化工具，提供非常多的选项，不过只用一个就很适合我了^^
具体的做法是
$ gedit ~/.indent.pro
输入内容为：
OK，以后只要用
$ indent ooxx.cpp
就可以把 ooxx.cpp 格式化成linux风格，正好适合我^^
indent是一个开源的C/C++代码规范化工具，提供非常多的选项，不过只用一个就很适合我了^^
具体的做法是
$ gedit ~/.indent.pro
输入内容为：
引用
-linux
OK，以后只要用
$ indent ooxx.cpp
就可以把 ooxx.cpp 格式化成linux风格，正好适合我^^
Oct
30
题目：给出2N个正数，找出其中两个不凑对的。
e.g.：
对于1, 2, 2, 3, 4, 5, 3, 4，不凑对的是1和5
算法思路1(momodi给出)：
设不凑对的两个数分别为m和n
1. 对所有数字进行XOR，得出k，则必有k != 0
2. 找到 k 二进制表示中的某一个 1，必有m和n该位分别为1和0
3. 根据该位置为1或0，把所有数分为两a, b半
4. 对a、b两半分别异或，即得出m、n
此算法可以保证正确性，以及O(N)的时间复杂度、O(1)的附加空间。
算法思路2(felix给出)：
e.g.：
对于1, 2, 2, 3, 4, 5, 3, 4，不凑对的是1和5
算法思路1(momodi给出)：
设不凑对的两个数分别为m和n
1. 对所有数字进行XOR，得出k，则必有k != 0
2. 找到 k 二进制表示中的某一个 1，必有m和n该位分别为1和0
3. 根据该位置为1或0，把所有数分为两a, b半
4. 对a、b两半分别异或，即得出m、n
此算法可以保证正确性，以及O(N)的时间复杂度、O(1)的附加空间。
算法思路2(felix给出)：
