面试题：C++中用Lambda表达式作为STL容器自定义比较函数并分析性能

Question

在`std::set<int, YourComparator>`中，`YourComparator`需要使用Lambda表达式来定义一种比较规则：使得集合中的元素按照绝对值从大到小排序。请写出Lambda表达式的定义，并简要分析这种自定义比较函数在插入和查找操作时，相比于默认比较函数可能产生的性能影响。

Answer 1

Lambda表达式定义如下：

auto YourComparator = [](int a, int b) {
    return std::abs(a) > std::abs(b);
};

性能影响分析

1. 插入操作：
   • 默认比较函数通常是按照元素值从小到大排序，是一种简单的整数比较，开销较小。
   • 使用自定义的按绝对值从大到小的比较函数，每次插入时都需要计算元素的绝对值，然后再进行比较。计算绝对值操作增加了额外的计算开销，因此插入操作的时间复杂度虽然在最坏情况下依然是$O(\log n)$（$n$为集合元素个数），但实际运行时间可能会比默认比较函数慢，尤其是在元素数量较多时。
2. 查找操作：
   • 同样，默认比较函数进行简单整数比较开销小。
   • 自定义比较函数每次查找时都要计算绝对值，增加了计算量。在查找元素时，虽然红黑树的查找时间复杂度理论上还是$O(\log n)$，但由于计算绝对值的额外开销，实际查找性能会比默认比较函数差，特别是当集合规模较大时。