Felix021

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风格，正好适合我^^

题目：给出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给出)：

    *  教您怎样使用位运算实现循环移位
    * 来源：http://www.idcnews.net/html/edu/C/20070606/235880.html

    循环移位区分于一般移位的是移位时没有数位的丢失。循环左移时，用从左边移出的位填充字的右端，而循环右移时，用从右边移出的位填充字的左侧。这种情况在系统程式中时有使用，在一些控制程式中用得也不少。
    设有数据说明：
    a=01111011，循环左移2位 正确结果: 11101101
    过程：

花了挺多的时间整理出了C++ STL的各种标准容器以及标准的C++非STL容器，包括stack, queue, priority_queue, string, vector, deque, list, map, multimap, set, multiset, 在整理的同时测试过去，感觉对这些容器的使用都比较熟悉了，而且对泛型编程也有了比较深的理解。现在也整理出了STL的算法这一部分，花了一整个晚上。。。真累阿。发现STL的算法部分其实也是非常值得看看的。比如next_permutation这个算法，可以产生某序列的下一个排列，效率竟然是自己写的DFS的2倍还高些！省了代码，保证了正确性，还提高了效率，何乐而不为呢！

花了这么多时间整理出来，不仅仅是希望自己能用上，也希望所有有需要的人可以看到，参考。或许有些错误，如果谁发现了，还望告知～～

在整理的时候查看了很多资料，最重要的一些是是The C++ Standard Library,  http://cppreference.com ,  C++ Programmer's Guide,  Effective STL , 都是非常好的书/网站，如果有不明白的，或者需要更详细的，建议去翻翻这些资料。

Felix021 @ 2008.08.22 4:24

摘自boost库的文档：
Currently   the   library   contains   only   naive   implementation   of   find   algorithms   with   complexity   O(n   *   m)   where   n   is   the   size   of   the   input   sequence   and   m   is   the   size   of   the   search   sequence.   There   are   algorithms   with   complexity   O(n),   but   for   smaller   sequence   a   constant   overhead   is   rather   big.   For   small   m   < <   n   (m   by   magnitude   smaller   than   n)   the   current   implementation   provides   acceptable   efficiency.   Even   the   C++   standard   defines   the   required   complexity   for   search   algorithm   as   O(n   *   m).   It   is   possible   that   a   future   version   of   library   will   also   contain   algorithms   with   linear   complexity   as   an   option。

也就是说string::find()提供的是O(m*n)的效率，不是KMP的O(n)，很汗。。。

    在C++里，STL中string和vector的空间是可以自动增长的，但是有一个问题是，当你将它们中的元素删除(甚至是使用clear函数)时，多余的空间不会被释放，这时候可以用一个交换技巧(详见Effective STL)来清空多余的元素：

这些天花了不少时间看STL，当然也少不了看《Effective STL》这本书。
这本书讲了很多内容，我只记下了对于初学者比较容易理解和需要记住的一些重要条款：

条款4：用empty()来代替检查size()是否为0
因为size()可能需要O(n)的时间，但是empty()只需要O(1)

条款5：尽量使用区间成员函数代替它们的单元素兄弟
对于插入已知数量或已知区间的元素，使用区间版的成员函数效率高。
比如vt.insert(a, a+100000)效率将显然高于for(i=0;i<100000;i++)vt.insert(a[i]);
因为后者需要反复调用insert()并可能多次重新分配空间

今天做比赛的时候Cplus用STL的list写一个3000个vertex的图的邻接表MLE了，所以产生了测试STL容器内存占用的念头。
没下什么软件，也没用系统什么命令，就是写个程序插入500,000个元素到这些容器中，然后分别提交到WOJ 1035进行测试。
因为1035的内存限制是64M，时间限制是1000ms，所以没有用更大的数据进行测试，但是测试结果确实能说明一些问题了：

实测环境:WOJ 1035 BG
数据量: 500,000个int(map使用的是<int,int>)
结果:
容器    内存占用    时间
array  3060K      4ms
deque  3200K      15ms
queue  3204K      19ms
stack  3204K      19ms
vector 5168K      14ms
priority_queue 5172K  650ms
list   16768K     132ms
set    24584K     922ms
map<int,int> 24584K   913ms

不知道为什么list会占用那么大的空间，看来以后对list的使用要谨慎再谨慎了。