语法与函数

函数

1.lower_bound()，upper_bound

二分查找函数：

iteration::rstart lower_bound(iteration::start，iteration::end，key)；

lower_bound()返回值是一个迭代器,返回指向大于等于key的第一个值的位置

upper_bound()返回值是一个迭代器,返回指向大于key的第一个值的位置

找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

基本用法

我们都知道C++ STL中有两个函数lower_bound和upper_bound，它们都是在有序序列中进行二分查找的，lower_bound返回的是第一个大于等于给定值的元素的位置，upper_bound返回的是第一个大于给定值的元素的位置。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    cout << *lower_bound(v.begin(), v.end(), 5) << endl;    // 5
    cout << *upper_bound(v.begin(), v.end(), 5) << endl;    // 6
    return 0;
}

上面是最简单的用法，其实lower_bound和upper_bound有4个参数，上面使用的是默认的cmp,但是有的时候我们可能需要针对特定问题来定义我们自己的比较方式,或者我们想要使用一个没有默认cmp的类型，那么就需要用到自定义cmp了。

自定义cmp

假如我们现在想对一个二维数组进行二分查找，那么我们就需要自定义一个cmp函数，这个函数的参数是两个vector<int>，返回值是bool

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    vector<vector<int>> v = {{1, 2}, {3, 4}, {5, 6}};
    cout << *lower_bound(v.begin(), v.end(), vector<int>{3, 4}, [](vector<int> a, vector<int> b) {
        return a[0] < b[0];
    })[0] << endl;    // 3
    cout << *upper_bound(v.begin(), v.end(), vector<int>{3, 4}, [](vector<int> a, vector<int> b) {
        return a[0] < b[0];
    })[0] << endl;    // 5
    return 0;
}

上面自定义了一个比较函数，这个函数的参数是两个vector<int>，返回值是bool，这个函数的作用是比较两个vector<int>的第一个元素的大小，那么该二分查找就是对vector的第一个元素进行二分查找。

进阶

自定义比较函数的例子里，我们二分搜索的目标是一个vector<int>，也就是说搜索目标和被搜索的序列的类型是一样的，但是如果这里的搜索目标是一个数而不是vector呢？（即搜索目标和待搜索的序列类型不一样）

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    vector<vector<int>> v = {{1, 2}, {3, 4}, {5, 6}};

    cout << *lower_bound(v.begin(), v.end(), 3, [](vector<int> a, int b) {
        return a[0] < b;
    })[0] << endl;    // 3

    cout << *upper_bound(v.begin(), v.end(), 3, [](int a, vector<int> b) {
        return a < b[0];
    })[0] << endl;    // 5
}

可以看到我们待二分搜索序列中的每个元素类型是vector<int>,而函数中的搜索目标却是一个int。

attention

这里需要注意的是，若要使用这种方法，上面的lower_bound和upper_bound的比较器是不一样的，以上面的例子来说，lower_bound的比较器是 { return a[0] < b; }，而upper_bound的比较器是 { return a < b[0]; }，两个比较器的参数顺序以及函数体内的参数顺序刚好都是反过来的。

2.list::splice

list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list。

函数有以下三种声明：

void list::splice( iterator pos, list rhs );
void list::splice( iterator pos, list rhs, iterator ix ); 
void list::splice( iterator pos, list rhs, iterator first, iterator last );

splice()把一个或一级元素从一个 list 移到另一个中去 它有三种形式

1、从positon开始，把一个 list rhs的全部元素搬移到另一个中去 pos开始

2、从positon开始，把一个 ix 元素搬移到 rhs 的 pos位置

3、从positon开始，把first 到 last 剪接到要操作的list对象中的pos位置

3.分割字符串-stringstream

//s为原字符串
stringstream ss(s);
string item;
while(getline(ss, item, ' '))
{
    cout << item <<endl;
}

4.map的lower_bound二分查找操作

map<int, int> cmap;
auto pos = cmap.lower_bound(num);
//pos返回大于等于num的迭代器，如果末尾则为cmap.end()

语法

1.priority_queue 排序写法

class cmp
{
    public:
    bool operator()(const pair<int,int> &a ,const pair<int,int> &b)
    {
        return a.second < b.second; //这种写法是大顶堆
    }
};

auto cmp = [&](const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return nums1[lhs.first] + nums2[lhs.second] > nums1[rhs.first] + nums2[rhs.second];
        };

//自定义类型 两种写法
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> que;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> heap(cmp);
//原有类型
priority_queue<int,vector<int>,greater<int>> que; // 小顶堆 -- 第k大
priority_queue<int,vector<int>,less<int>> que;// 大顶堆 -- 第k小
priority_queue<int,vector<int>> que;// 大顶堆（默认）

2.map/set 排序写法

class MyCompare 
{
public:
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};
set<int,greater<int>> sets1; // 指定set从大到小排序
set<int,MyCompare> sets2; // 指定set从大到小排序

//注意：map是键值对，需要按照键排序，所以参数填的int
map<int,greater<int>> map1; // 指定map从大到小排序
map<int,MyCompare> map2; // 指定map从大到小排序

刷题注意牢记

1.二分的左右最小值怎么算

2.回溯的去重问题以及从什么地方开始遍历

3.dp的背包问题的排列和组合问题

4.快慢指针快速找到链表的中点

5.记忆快排和归并

6.位运算

r & (-r) 是一个位运算的操作，表示将 r 的二进制表示取反然后加一，然后与 r 进行按位与操作。

例如，假设 r = 5，它的二进制表示为 0101，则 -r = -5 的补码表示为 1011。进行按位与操作，即 0101 & 1011 = 0001，结果为 1。

这种操作对于找出一个整数的最低非零位（即最右边的 1）非常有用。