STL在算法中的常用技巧

本文主要介绍算法题中常用到的一些功能的STL实现

排序

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

Sorts the elements in the range [first, last) in non-descending order. The order of equal elements is not guaranteed to be preserved.

//对 [first, last) 区域内的元素做默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

其中，first 和 last 都为随机访问迭代器，它们的组合 [first, last) 用来指定要排序的目标区域；另外在第 2 种格式中，comp 可以是 C++ STL 标准库提供的排序规则（比如 std::greater<T>），也可以是自定义的排序规则。

降序实现

---

1. 直接反转
   reverse(a.begin(), a,end());
   sort(a.rbegin(), a.rend());

2. 使用标准库函数
   sort(a.begin(), a.end(), greater<>());

3. 定义比较函数

   //情况一：数组排列
   int A[100];
   bool cmp1(int a,int b)//int为数组数据类型
   {
       return a>b;//降序排列
       //return a<b;//默认的升序排列
   }
   sort(A,A+100,cmp1);
   
   //情况二：结构体排序
   Student Stu[100];
   bool cmp2(Student a,Student b)
   {
       return a.id>b.id;//按照学号降序排列
       //return a.id<b.id;//按照学号升序排列
   }
   sort(Stu,Stu+100,cmp2);

4. 重载比较操作运算符

   //情况一：在结构体内部重载
   typedef struct Student{
       int id;
       string name;
       double grade;
   
       bool operator<(const Student& s)
       {
           return id>s.id;//降序排列
           //return id<s.id;//升序排列
       }
   };
   vector<Student> V;
   sort(V.begin(),V.end());
   
   //情况二：在外部重载
   vector<Student> V;
   bool operator<(const Student& s1, const Student& s2)
   {
       return s1.id>s2.id;//降序排列
       //return s1.id<s2.id;//升序排列
   }
   sort(V.begin(),V.end());

5. 函数对象
   另外一种方式，即构造一个函数对象，抑或叫 functor，其实就是实现了重载 operator() 的一个类

   struct Less
   {
       bool operator()(const Student& s1, const Student& s2)
       {
           return s1.id<s2.id; //升序排列
       }
   };
   sort(sutVector.begin(),stuVector.end(),Less());

6. lambda
   使用 C++11，您甚至可以将 lambda 函数传递给 std::sort 功能

   std::sort(vec.begin(), vec.end(), [](const int &l, const int &r) {
               return l > r;
           });

对象是容器的话，推荐用方法1，2. 非容器的话推荐lambda表达式.

Reference

[1]. cppreference
[2]. sort函数详解
[3]. 在 C++ 中按降序对Vector进行排序
[4]. C++ sort排序之降序、升序使用总结

关键字排序K个数

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
    return abs(a - x) < abs(b - x) || abs(a - x) == abs(b - x) && a < b;
});
sort(arr.begin(), arr.begin() + k);

也可以直接用lambda表达式