C++的STL比较方法

C++

在写算法题、使用C++开发的过程中，经常需要使用到STL来存取大量的有序数据，并且排序算法并不一定是简单的比大小，需要用户来自定义复杂的比较逻辑。由于本人在写leetcode时常常忘记比较算法，因此特别记录一下。

创建比较类

第一种标准办法是自定义Comparator类，并且定义一个operator()的比较方法。

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
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    class Comparator {
        public:
        bool operator()(const ListNode* node1, const ListNode* node2) {
            return node1->val > node2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode new_head = ListNode();
        ListNode* ptr = &new_head;
        priority_queue<ListNode*, vector<ListNode*>, Comparator> pq;
        int k = lists.size();
        for(int i = 0; i < k; ++i) {
            if(lists[i] != nullptr) {
                pq.push(lists[i]);
            }
        }
        while(!pq.empty()) {
            ListNode* node = pq.top();
            ptr->next = node;
            ptr = ptr->next;
            pq.pop();
            if(node->next) {
                pq.push(node->next);
            }
        }
        return new_head.next;
    }
};

创建lambda表达式

第二种办法是创建一个lambda表达式。与创建一个类最不同的是，需要使用decltype，并且如果是priority_queue

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
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode new_head = ListNode();
        ListNode* ptr = &new_head;
        auto comp = [](const ListNode* node1, const ListNode* node2) {
            return node1->val > node2->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
        int k = lists.size();
        for(int i = 0; i < k; ++i) {
            if(lists[i] != nullptr) {
                pq.push(lists[i]);
            }
        }
        while(!pq.empty()) {
            ListNode* node = pq.top();
            ptr->next = node;
            ptr = ptr->next;
            pq.pop();
            if(node->next) {
                pq.push(node->next);
            }
        }
        return new_head.next;
    }
};

lambda表达式的底层分析

我们可以看到，lambda表达式比起定义一个类，再写一个operator()这样的函数会简单一些。但实际上，lambda表达式的本质就是一个匿名类。

1
2
3
4
5
6
class __lambda_xxx { 
public: 
bool operator()(const ListNode* node1, const ListNode* node2) const { 
	return node1->val > node2->val; 
} 
};

decl(comp)实际上只是一个类型。所以我们还需要在priority_queue中使用pq(comp)来传递一个实例。
当然，这只是最简单的lambda表达式表现方式。lambda表达式另一个更有特点的地方在于它的捕获，可以让lambda表达式内部能修改外面的变量。

lambda的捕获

  • 按值捕获
1
2
3
4
5
int x = 5;
string name = "test";
auto comp = [=](int a) {
    return a > x && name.length() > 0;
};

就是把所有的值都拷贝存储，生成的类就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class __lambda_xxx {
private:
    int x;           // 拷贝存储
    string name;     // 拷贝存储
    
public:
    __lambda_xxx(int x_val, const string& name_val) 
        : x(x_val), name(name_val) {}  // 拷贝构造
    
    bool operator()(int a) const {
        return a > x && name.length() > 0;
    }
};

  • 按引用捕获
1
2
3
4
5
6
int x = 5;
string name = "test";
auto comp = [&](int a) {
    x++;  // 可以修改原变量
    return a > x && name.length() > 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class __lambda_xxx {
private:
    int& x;           // 引用存储
    string& name;     // 引用存储
    
public:
    __lambda_xxx(int& x_ref, string& name_ref) 
        : x(x_ref), name(name_ref) {}
    
    bool operator()(int a) const {  // 注意：即使是const，也能通过引用修改外部变量
        x++;  // 修改外部变量
        return a > x && name.length() > 0;
    }
};

  • 当然，也可以按值+按引用选择性地捕获
1
2
3
4
5
6
7
8
int x = 5;
int y = 10;
string name = "test";
auto comp = [&x, y](int a) {  // x按引用，y按值，name不捕获
    x++;
    return a > x + y;
};

因此，我们可以明显观察到，捕获的元素越多，这个匿名类肯定就越大。

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

int main() {
    int x = 1;
    double y = 2.0;
    std::string s = "hello";
    
    auto lambda1 = [](int a) { return a > 0; };           // 无捕获
    auto lambda2 = [x](int a) { return a > x; };          // 捕获int
    auto lambda3 = [x, y](int a) { return a > x + y; };   // 捕获int+double
    auto lambda4 = [x, y, s](int a) { return a > x; };    // 捕获int+double+string
    
    std::cout << "无捕获: " << sizeof(lambda1) << " bytes\n";      // 通常是1
    std::cout << "捕获int: " << sizeof(lambda2) << " bytes\n";     // 4
    std::cout << "捕获int+double: " << sizeof(lambda3) << " bytes\n"; // 16 (对齐)
    std::cout << "捕获int+double+string: " << sizeof(lambda4) << " bytes\n"; // 48+
    
    return 0;
}

P.S.: 之前面微信的时候面试官真的问了lambda表达式底层是什么。当时还没有来得及准备C++八股，只能遗憾离场了😎😭。