有一些程序, 虽然写起来不难, 但是可能比较麻烦或容易出错, 这时就可以用C++函数库里自带的一些实用的函数. 这里只记录一些不太常见可能会用上的函数. 以后可能会继续更新~
1. __gcd(x, y).
求两个数的最大公约数, 在algorithm库中.
2. unique(a + 1, a + n + 1) .
去重函数. 跟sort的用法一样. 不过返回的值是最后一个数的地址, 所以要得到新的数组长度应该这么写: new_n = unique(a + 1, a + n + 1) – a – 1.
3. lower_bound(a + 1, a + n + 1, x); upper_bound(a + 1, a + n + 1, x).
lower_bound是查找数组中第一个大于等于x的数, 返回该地址, 同理也是pos = lower_bound(a + 1, a + n + 1, x) – a. upper\_bound是查找第一个大于x的数, 用法和lower_bound一样. 复杂度是二分的复杂度, O(logn), (其实就是代替了手写二分)
4. fill(a + 1, a + n + 1, x).
将数组a中的每一个元素都赋成x, 跟memset的区别是, memset是一个字节一个字节赋值, fill是一个元素一个元素赋值!(省掉一层for……)
5. next_permutation(a, a + n).
该函数包含在头文件algorithm里面, 它按照字典序产生排列, 并且是从数组中当前的字典序开始依次增大直至到最大字典序. 记得使用前需要对容器进行排序, 否则得到的排列集合元素一般会偏少.
6. 如何判断一个数是2的幂?
1个数乘以2就是将该数左移1位, 而2的0次幂为1, 所以2的n次幂就是将1左移n位, 这样我们知道如果一个数n是2的幂, 则其只有首位为1, 其后若干个0, 必然有n&(n – 1)=0. (在求1个数的二进制表示中1的个数的时候说过, n&(n-1)去掉n的最后一个1). 因此, 判断一个数n是否为2的幂, 只需要判断n&(n-1)是否为0即可. (谨记, 此处的判断应写为if((n&n-1)==0), 因为==的优先级是要比&的优先级要高的)
7. 如何判断是2的多少次方呢? (即探讨底数为2的对数函数的实现)
int log2(int value) //递归判断一个数是2的多少次方
{
if (value == 1)
return 0;
else
return 1+log2(value>>1);
}
8.求两个集合的交集
使用set_intersection:
vector<int> y;
set_intersection(begin(s1), end(s1),
begin(s2), end(s2), back_inserter(y));
这里使用了back_inserter不得不说是非常妙了. 另外, s1, s2一般都是一个set而非vector, 因为该函数要求s1, s2是有序的(跟unique一样的要求).