算法竞赛常用STL和其他c++知识点总结

摘要：
算法竞赛经常用到的STL和JDK轮子总结。

STL(如果对应Java的JDK存在类似功能，也一并给出)

1. 排序

C++
对数组vector<int> a排序：
#include <algorithm>

• 升序
  sort(a.begin(), a.end());
sort(a.begin(), a.end(), less<int>());

• 降序
  sort(a.begin(), a.end(), greater<int>());
sort(a.rbegin(), a.rend());

Java

1. Arrays.sort​(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
   用于排序数组。
   举例：

   //降序
   Arrays.sort(arr, new Comparator<Integer>() {
       @Override
       public int compare(Integer a, Integer b) {
           return b-a;
       }
   });

2. Cpllections.sort​(List<T> list, Comparator<? super T> c)
   用于排序容器。
   举例：

   List<Integer> list = new ArrayList<>();
   Collections.sort(list, new Comparator<Integer>() {
       @Override
       public int compare(Integer a, Integer b) {
           return b - a;
       }
   });

2. 字符串转数值类型

#include <string>
std::atoi
转换 const char* 为一个 int 类型整数，超出 int 类型范围时，返回边界值。

std::atol
转换 const char* 为一个 long 类型整数，超出 long 类型范围时，返回边界值。

std::atoll
转换 const char* 为一个 long long 类型整数，超出 long long 类型范围时，返回边界值。

std::stoi
转换 std::string 为一个 int 类型整数，超出 int 类型范围时报错。

std::stol
转换 std::string 为一个 long 类型整数，超出 long 类型范围时报错。

std::stoll
转换 std::string 为一个 long long 类型整数，超出 long long 类型范围时报错。

3. 有序集合

C++
set

Java
TreeSet

4. 截取子串

C++
string s = "abcd";
s.substr(int index)
截取从 index 开始到字符串结束的子串。
s.substr(int index, int len)
截取从 index 开始，长度为 len 的子串。

Java
String s = new String("abcd");
s.substring(int index)
截取从 index 开始到字符串结束的子串。
s.substring(int beginIndex, int endIndex)
截取从 beginIndex 开始到 endIndex 前一个字符结束的子串。左闭右开。

5. bitset

C++

• 定义一个长度为 MXN 的bitset:
  bitset<MXN> bs;
• 将下标为 idx 处的值设为 true / false
bs[idx] = true; bs[idx] = 1;
bs[idx] = false; bs[idx] = 0;
• 统计所有值为1的个数
  int x = bs.count();
• 反转下标为 idx 处的值
  bs[idx].flip(); 或 bs.flip(idx);

Java

• 定义一个长度为 MXN 的bitset:
  BitSet bs = new BitSet();
• 将下标为 idx 处的值设为 true / false
bs.set(idx, true);
bs.set(idx, false);
• 统计所有值为1的个数
  int x = cardinality();
• 反转下标为 idx 处的值
  bs.flip(idx);

6. 反转字符串

C++

string s = "1234567";
reverse(s.begin(), s.end());

Java

String s = new String("1234567");
StringBuilder sb = new StringBuilder(s).reverse();
string re = sb.toString();

或者：

StringBuffer sb = new StringBuffer(s).reverse();
string re = sb.toString();

7. 堆

C++

priority_queue<int> max_heap // 大根堆
priority_queue<int, vector<int>, greater<int>> min_heap // 小根堆

大根堆指的是root节点最大的堆，小根堆同理。

自定义比较器（等同于 less<int>）：

struct cmp {bool operator()(int a,int b) {return a < b;}}; 
priority_queue<int, vector<int>, cmp> pq;

当函数返回 true 时，说明 a < b，a 的优先级高，优先级高的放入叶子节点。从而实现大根堆。
说人话就是：只要 a < b，就把 a 放入叶子节点。

自定义比较器（等同于 greater<int>）：

struct cmp {bool operator()(int a,int b) {return a > b;}}; 
priority_queue<int, vector<int>, cmp> pq;

当函数返回 true 时，说明 a > b，a 的优先级高，优先级高的放入叶子节点。从而实现小根堆。
说人话就是：只要 a > b，就把 a 放入叶子节点。

C++优先队列默认是大根堆，且不支持Lambda表达式构造方法。

现在咱们和 sort 对 vector 排序时的比较器做一下对比，自定义排序函数时，如：

bool cmp(int a, int b) {
    return a < b;
}

如果函数返回 true，说明 a < b，a 的优先级高，两个数中，优先级高的放入前面，从而实现递增排序。反之亦然。
说人话就是：只要 a < b，就把 a 放在 b 前面。只要 a > b，就把 a 放在 b 的前面。

和堆比较，二者的区别即在于优先级高的放在哪里（堆是叶子节点，sort vector 是两个数的前面）。

Java
Java的优先队列默认是小根堆。

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 初始化小根堆

Queue<Integer> maxHeap =new PriorityQueue<>(new Comparator<Integer>() {

			@Override
			public int compare(Integer a, Integer b) {
				// TODO 自动生成的方法存根
				return b - a;
			}
});

说一下自定义大根堆：当函数返回真时，说明 a < b，那么就把较小的 a 放在叶子节点。实现大根堆。

其他C++知识点

0x0 输出指定位的小数点或有效数字

举例：
float a = 233.233;

• 输出保留2位小数:
  inlcude <iomanip>
cout << setiosflags(ios::fixed) << setprecision(2) << a;
  四舍五入输出233.23
  其中，setiosflags(ios::fixed) 为设置浮点数以固定的小数位数显示。
  setprecision(2) 为设置精度为2.

• 输出保留5位有效数字
  cout << setprecision(5) << a;
  四舍五入输出233.23

参考链接： C++ 如何保留两位小数和有效位数

参考链接： C++ 标准库之 iomanip 、操作符 ios::fixed 以及 setprecision 使用的惨痛教训经验总结