跳转至

2 STL 常用函数

STL 中大量的函数在熟练掌握后可以提高写代码的效率。

  使用 STL 中的函数需要包含头文件<algorithm>。

sort 函数

  std::sort用于排序，会根据实际情况调整底层实现算法，时间复杂度 $O(n\log n)$，再也不用手写快排/归并。
  该函数可以用于数组或vector。使用数组时，传入需要排序区间的头指针和尾指针（左闭右开）；使用vector时传入迭代器。 

1
2
3
4
5
6
7
8
int arr[6] = {1,1,4,5,1,4};
std::sort(arr,arr + 6); // arr: [1,1,1,4,4,5]
std::vector<int> vec;
vec.push_back(1);
vec.push_back(9);
vec.push_back(8);
std::sort(vec.begin(),vec.end()); // vec: [1,8,9]
std::sort(vec.rbegin(),vec.rend()); // vec: [9,8,1]
  std::sort可以传入第三个参数。这个参数返回bool值，是自定义的排序模式。该函数返回true时，第一个参数所代表的元素应排在前面。 
1
2
3
// 大的排在前面，即降序排序
bool cmp(const int &a,const int &b){return a > b;};
std::sort(vec.begin(),vec.end(),cmp);
  或者更简单地，直接使用匿名函数。 
1
2
// 依然是降序排序
std::sort(vec.begin(),vec.end(),[](const int &a,const int &b){return a > b;});

自定义排序函数的严格弱序要求

  自定义比较函数不能随意设置，它必须是严格弱序的，否则会引发未定义行为。同时满足以下三个条件的函数cmp是严格弱序的：

  • 反自反性：cmp(a,a)返回false。
  • 反对称性：如果cmp(a,b)返回true，则cmp(b,a)必须返回false。
  • 传递性：如果cmp(a,b)和cmp(b,c)都返回true，那么cmp(a,c)也要返回true。

经典的>=和<=都不是严格弱序的，因为不满足反自反性和反对称性。实际操作中建议使用>或者<。至于为什么要有严格弱序的要求，参见这篇博客。

unique 函数

  std::unique用于去重，说的更明白些是将多个连续的相同元素变成一个。其时间复杂度应该是 $O(n)$。
  该函数的调用方法和std::sort类似，没有第三个参数。在实际执行时，会将指定范围内的数据进行去重，并返回去重后的尾地址（去重数组返回指针，去重vector返回迭代器）。尾地址后的元素处于未指定状态。 

1
2
3
vector<int> a = {1,1,4,5,1,4};
int b = std::unique(a.begin(),a.end()) - a.begin();
// a = [1,4,5,1,4,*], b = a.begin() + 5, * 代表处于未指定状态
  如果要去掉所有重复的元素，做到真正的去重，可以先排序再使用该函数。

lower_bound 和 upper_bound 函数

  两个函数都是在有序的数组或者vector中寻找第一个满足某条件的元素。底层逻辑为二分查找，时间复杂度 $O(\log n)$。

  • std::lower_bound:寻找第一个不小于某值的元素，并以指针或迭代器形式返回。
  • std::upper_bound：寻找第一个大于某值的元素，并以指针或迭代器的形式返回。

  具体来说可以举一个例子。 

1
2
3
std::vector<int> a = {1,4,5,7,8,9};
std::cout << std::lower_bound(a.begin(),a.end(),4) - a.begin() << std::endl; // 1，即这个元素为 a[1] = 4
std::cout << std::upper_bound(a.begin(),a.end(),5) - a.begin() << std::endl; // 3，即这个元素为 a[3] = 7
  实际上这两个函数还可以传入第四个参数。实际上这个也不难掌握，上面的代码块也可以写作下面的四参数形式，输出结果是一样的。 
1
2
3
4
std::vector<int> a ={1,4,5,7,8,9};
auto cmp = [](const int &a,const int &b){return a < b;};
std::cout << std::lower_bound(a.begin(),a.end(),4,cmp) - a.begin() << std::endl;
std::cout << std::upper_bound(a.begin(),a.end(),5,cmp) - a.begin() << std::endl;
  也就是说三参数的std::lower_bound和std::upper_bound实际上都等价于第四个参数是函数less<type>()。实际运用时按照这个逻辑进行推演就好。

推演的例子

  已知条件是，若传入auto cmp = [](const int &a,const int &b){return a < b;};，那么std::lower_bound寻找的是第一个不小于某值的函数。若我传入auto cmp = [](const int &a,const int &b){return a > b;};，那么寻找的就是第一个不大于某值的函数（前提是序列要递减）。

  当然，有时候我们数组的元素和待比较的元素不是同一类型(1)。此时我们必须搞清楚这个自定义比较函数的内涵。这样不难理解，就比如lower_bound，我们可以认为它有一个“默认的比较函数”，也就是上面的cmp。结合lower_bound的目标是找到第一个不小于某值的元素，可以得到：

  1. 比如有一个结构体数组： 
    struct lk{
    string name;
    int likes;
} liker[M];
    结构体数组liker的元素是按照的likes字段值升序排序的，想要这个liker数组中，第一个likes成员大于val的结构体。显然我们可以构造一个likes字段为val的结构体进行比较，但这样感觉不是很优雅，所以需要深入了解自定义比较函数的内涵。

cmp的第一个参数是数组元素，第二个参数是目标值；lower_bound找到第一个使得cmp返回False的元素。

  同样地，结合upper_bound的功能，以及它的“缺省比较函数”cmp，可以得到：

cmp的第一个参数是目标值，第二个参数是数组元素；upper_bound找到第一个使得cmp返回True的元素。