标准函数

C++中提供了相当多的标准算法，几乎都包含在标准库 algorithm 中；

排序与最值

排序

cmp 函数的作用在于规定相邻两个元素之间的关系，从而影响整体的排布；

bool cmp(int a, int b){
	return a > b; //序列中任意两个元素之间的关系都要满足 a>b
}
vector<int> vec = {1, 2, 3, 4, 5};
sort(vec.begin(), vec.end(), cmp);
//在这个cmp函数的情况下，最终结果 vec: 5 4 3 2 1

最值

有一些简单的方法可以直接得到一个数组容器中最大/最小值：

vector<int> vec = {1,2,3,4,5,9,8,7,6};
auto min_it = min_element(vec.begin(), vec.end()); //注意返回的是一个迭代索引
auto max_it = max_element(vec.begin(), vec.end());
 
int min = *min_element(vec.begin(), vec.end()); //注意*操作符
int max = *max_element(vec.begin(), vec.end());

二分查找

二分查找可以执行在 vector 容器上，其主要有三个用途：1️⃣检测是否存在的 binary_search；2️⃣检测下界的 lower_bound；3️⃣检测上界的 upper_bound

• binary_search 在first和last中的前闭后开区间进行二分查找，并以布尔值返回是否查找成功

vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
bool found = binary_search(vec.begin(), vec.end(), 5);

• lower_bound 在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val，则返回last的位置

vector<int> vec = {1, 2, 3, 4, 5, 5, 6, 7, 8, 9};
auto lower = lower_bound(vec.begin(), vec.end(), 5);
int lower_index = lower - vec.begin(); //下界的索引，输出为4

• upper_bound 在前闭后开区间查找关键字的上界，返回严格大于val的第一个元素位置

vector<int> vec = {1, 2, 3, 4, 5, 5, 6, 7, 8, 9};
auto upper = upper_bound(vec.begin(), vec.end(), 5);
int upper_index = upper - vec.begin(); // 上界的索引，输出为6

注意

其实 lower_bound 和 upper_bound 这个名字是针对含有重复的 $target$ 而言的；直观上，lower_bound 和 upper_bound 将整个数组划分为了三个部分，第一部分 $<target$ ，第二部分 $==target$，第三部分 $>target$

堆操作

C++中其他的有关堆的操作都是通过算法提供的，因此需要包括 algorithm 库函数才能够使用

• 快速建堆，在已知完整数组的情况下可以达到 $O(logn)$ 级别；插入建堆只有 $nlogn$ 的效率：

vector<int> vec{6, 1, 2, 5, 3, 4};
make_heap(vec.begin(), vec.end()); // 默认从大到小(大根堆)
printContainer(vec, "vec: "); // vec: 6 5 4 1 3 2
 
//使用cmp函数控制堆的类型
//建堆操作中cmp函数代表了子节点与父节点之间的关系；这个例子是小根堆
bool cmp(int a,int b){
	return a > b; 
}
make_heap(vec.begin(), vec.end(), cmp);

• 插入操作：

vec.push_back(200);
push_heap(vec.begin(), vec.end());

注意

这里只能够先加入然后再进行堆重建；并且需要保证原来的 vector 已经是一个堆，因为算法只对最后一个值进行操作

• 弹出操作：

pop_heap(vec.begin(), vec.end()); // 堆顶元素会被放置到vector最后
vec.back(); // 进行访问
vec.pop_back(); // 真正的弹出

最大公因数

非常生僻的函数 __gcd(a,b)

int Gcd = __gcd(a,b);
int Lcm = a*b/Gcd; // 最小公倍数

其他

字符转数字

标准函数 stoi 实现了字符串到数字的转换，英文含义为 string to integer

string target = "1256";
try{
	int num = stoi(target);
}catch(const invalid_argument& e){
	cout<<"非法输入"<<endl;
}catch(const out_of_range& e){
	cout<<"超出范围"<<endl;
}

标准输入流

string line;
getline(cin, line); //读取一整行输入，丢弃换行符，并存入字符串line中
stringstream ss(line); //用line来初始化字符流
 
int num;
vector<int> nums;
while(ss>>num){
	nums.push_back(num);
}

整数转二进制字符

string binary(int x) {
        string s;
        while (x) {
            s.push_back('0' + (x & 1));
            x >>= 1;
        }
        reverse(s.begin(), s.end());
        return s;
    }