算法学习专栏——C++需要知道的一些基础知识PLUS

Codefor

一、其他常见排序

之前的文章已经介绍过了一部分，下面来介绍一点新玩意。

sort()和stable_sort()函数

1、sort (first, last) ： 对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。

2、stable_sort (first, last)： 和 sort() 函数功能相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置。

3、stable_sort() 函数是基于归并排序实现的

4、sort() 函数是基于快速排序实现的

二、二分查找的一些函数使用

lower_bound()函数和upper_bound()函数的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int num[10] = {1, 2, 2, 2, 3, 3, 3, 3, 3, 3};
    
    
    int index1 = lower_bound(num, num + 10, 3) - num;
    cout << index1 << '\n';     
    // 输出num数组第1个>=3的数的位置下标4
    
    int index2 = upper_bound(num, num + 10, 3) - num;
    cout << index2 << '\n';
    // 输出num数组第1个>3的数的下标位置10
    // 注意：如果不存在这样的数它就会指向最后一个位置的数
    
    int index3 = lower_bound(num, num + 10, 2,greater<int>()) - num;
    cout << index3 << '\n';
    // 输出num数组第1个<=3的数的位置下标9
    
    int index4 = upper_bound(num, num + 10, 2, greater<int>()) - num;
    // 输出num数组第1个<3的数的位置下标3
    // 注意：如果不存在这样的数它就会指向最后一个位置的数
    cout << index4 << '\n';


    return 0;
}

binary_search(arr, arr + arr.size(), num)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int num[10] = {1, 2, 2, 2, 3, 3, 3, 3, 3, 3};
    // 这种方式的话就是必须先对数组进行排序才可以进行二分查找
    sort(num, num + 10);
    cout << binary_search(num, num + 10, 3); // 1表示找得到
    cout << binary_search(num, num + 10, 7); // 0表示找不到


    return 0;
}

find()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int num[10] = {3,4,6,2,1,25,0,8,3,1};
    
    
    cout << find(num, num + 10, 1) - num;
    // 可以輸出数组中第1个查找到的目标数1的下标，不排序就可以搜到
    return 0;
}

find_if()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int num[10] = {3,4,6,2,1,25,0,8,3,1};
    
    
    cout << find_if(num, num + 10, [](int x){return x > 3;}) - num;
    // 找到数组中第一个比3大的数的下标
    return 0;
}

count()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int num[10] = {3,4,6,2,1,25,0,8,3,1};
    
    
    cout << count(num, num + 10, 3);
    // 找到数组中3的个数
    return 0;
}

三、multiset

​ 在前面的文章我们已经介绍过了set，和它不同的就一点，它允许存在重复的元素，当然它和set一样拥有insert,erase，clear，count，find等函数。

​ 定义一个迭代器指向q集合的开始位置:multiset<int> :iterator it = q.front()

持续更新中

四、complex 复数类

六、count， count_if 区间内统计元素

七、search 区间内查找子区间

八、min_element，max_element，nth_element找区间的最小值， 最大值，一般用于获取序列（有序无序都可以）第n小的数

1
2
3
4
5
6
7
8
9
10
int arr[10] = {8, 7, 4, 2, 1, 3, 9, 10, 5, 6};
nth_element(arr, arr + 6, arr + 10); // 让 arr + 6这个位置的数就绪，即将第7大的数放到arr[6]
// 即执行完后，arr + 6位置前的数都比他小，后面的数都不低于他
for (int x : arr) {
    cout << x << ' ';
}
cout << endl;
// 输出 6 5 4 2 1 3 7 8 10 9 
cout << arr[6] << endl; // 获取排第7即位置6的数 输出 7

九、merge 合并两个有序区间

十、swap_range 交换两个区间

十一、adjacent_find 区间内查找相邻的相同的元素

十二、mismatch 找两个区间第一个不同的地方

十三、冷门函数

__builtin_popcount：二进制中 1 的个数

__builtin_ffs(10) = 2：

举例： ，因为二进制10表示为 ‘1010’ 从右往左数，第一个1的下标为1（下标从0开始计数）,函数返回 1+index，所以结果为2；而如果 x== 0, 则 return 0；

十四、valarray 数值数组