如何为vector of vector编写upper_bound比较函数，匹配全对应元素更大的元素？

首先明确：upper_bound 要求目标容器必须基于指定的比较函数严格弱序排序，否则无法保证结果的正确性。要实现你需要的“找到第一个所有对应元素均大于目标元素的元素”，我们需要分三步：定义符合要求的比较函数、对容器排序、最后使用upper_bound。

1. 定义自定义比较函数 #

我们需要的核心逻辑是：判断vector<int>对象a是否所有元素都严格小于b的对应元素。为满足严格弱序的要求（保证sort和upper_bound能正常工作），对于无法满足“全小于”的元素对，我们回退到字典序比较。

#include <vector>
#include <algorithm>

bool compareVectors(const std::vector<int>& a, const std::vector<int>& b) {
    // 检查a的所有元素是否严格小于b的对应元素
    bool allLess = true;
    const size_t minLen = std::min(a.size(), b.size());
    for (size_t i = 0; i < minLen; ++i) {
        if (a[i] >= b[i]) {
            allLess = false;
            break;
        }
    }
    // 若前minLen个元素全小于，再判断长度（短vector视为更小）
    if (allLess) {
        return a.size() <= b.size();
    }
    // 否则按字典序比较，保证严格弱序
    return a < b;
}

2. 对容器排序 #

在使用upper_bound前，必须用上述比较函数对vector<vector<int>>排序：

std::vector<std::vector<int>> arr = {{0,1,1},{0,1,2},{0,2,1},{1,2,3},{4,1,2},{4,3,2}};
std::sort(arr.begin(), arr.end(), compareVectors);

排序后，所有满足“全小于”关系的元素会按顺序排列，其余元素按字典序排列。

3. 使用upper_bound查找目标 #

传入同一个比较函数调用upper_bound，即可找到第一个所有元素均大于目标的元素：

std::vector<int> target = {0,1,1};
auto it = std::upper_bound(arr.begin(), arr.end(), target, compareVectors);

if (it != arr.end()) {
    // 示例中排序后第一个满足条件的元素为{1,2,3}
    for (int num : *it) {
        std::cout << num << " ";
    }
}

关键注意事项 #

• 严格弱序是核心：自定义比较函数必须满足严格弱序规则（反自反性、非对称性、传递性），回退到字典序的操作就是为了保证这一点，否则sort和upper_bound会出现未定义行为。
• 长度不一致的vector：如果你的场景中存在长度不同的vector，可根据需求调整长度比较逻辑（比如认为长vector的剩余元素更小），上述代码默认短vector的剩余元素视为更小。
• 原数组顺序保留：如果需要保留原数组的原始顺序，可以先复制一份数组再执行排序和查找操作。

内容的提问来源于stack exchange，提问作者Random User