跳转至

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;});

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 = [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,3,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,3,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;};，那么寻找的就是第一个不大于某值的函数（前提是序列要递减）。