面试题：C++ find算法在复杂数据结构及谓词函数优化中的应用

Question

有一个std::list<std::pair<int, std::vector<int>>> 类型的链表，其中每个pair的第一个元素代表编号，第二个元素是一个整数向量。编写代码，使用C++ STL的find算法，结合自定义谓词函数，找到编号为特定值（如10）且其向量中所有元素之和大于100的pair对象。若找到，输出该pair的详细信息；若未找到，给出提示。同时，请分析如何优化这个谓词函数以提高查找效率，并在代码实现中体现优化思路。请给出完整的代码实现。

Answer 1

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <numeric>

// 自定义谓词函数，优化思路：先检查编号，减少不必要的向量求和计算
bool customPredicate(const std::pair<int, std::vector<int>>& pair, int targetId, int targetSum) {
    if (pair.first != targetId) {
        return false;
    }
    return std::accumulate(pair.second.begin(), pair.second.end(), 0) > targetSum;
}

int main() {
    std::list<std::pair<int, std::vector<int>>> myList = {
        {5, {10, 20, 30}},
        {10, {50, 60}},
        {15, {10, 20}},
        {10, {40, 70}}
    };

    int targetId = 10;
    int targetSum = 100;

    auto it = std::find_if(myList.begin(), myList.end(), [&targetId, &targetSum](const std::pair<int, std::vector<int>>& pair) {
        return customPredicate(pair, targetId, targetSum);
    });

    if (it != myList.end()) {
        std::cout << "找到符合条件的pair: 编号 " << it->first << ", 向量元素: ";
        for (int num : it->second) {
            std::cout << num << " ";
        }
        std::cout << ", 向量元素之和: " << std::accumulate(it->second.begin(), it->second.end(), 0) << std::endl;
    } else {
        std::cout << "未找到符合条件的pair" << std::endl;
    }

    return 0;
}

上述代码首先定义了一个优化后的自定义谓词函数 customPredicate，该函数先检查编号是否匹配，避免了不必要的向量求和计算。然后在 main 函数中，使用 std::find_if 算法结合自定义谓词函数查找符合条件的 pair 对象，并根据查找结果输出相应信息。