如何对vector<vector<Edge>>类型图按Edge的weight降序排序？

这问题我之前做图结构的时候碰到过，分两种常见场景给你讲清楚，你可以根据自己的需求选：

场景1：对每个子向量里的Edge单独按weight降序排序 #

如果你的需求是graph里每个内层的vector<Edge>都各自按weight从大到小排列，直接用std::sort配合lambda表达式就能搞定，代码很直观：

首先得包含<algorithm>头文件，因为要用到std::sort：

#include <algorithm>
#include <vector>

// 先放一下Edge类的假设定义（你可以替换成自己的）
class Edge {
public:
    int height;
    int weight;
    int length;
    // 构造函数、其他方法...
};

// 排序函数
void sortEachEdgeListByWeightDesc(std::vector<std::vector<Edge>>& graph) {
    // 遍历外层vector的每个子向量
    for (auto& edgeList : graph) {
        // 用std::sort自定义排序规则：weight大的排前面
        std::sort(edgeList.begin(), edgeList.end(), [](const Edge& a, const Edge& b) {
            return a.weight > b.weight;
        });
    }
}

补充说明： #

• 如果你的Edge类中weight是私有成员，别慌，给它加个const的getter方法就行：

  class Edge {
  private:
      int weight;
  public:
      int getWeight() const { return weight; }
      // 其他成员...
  };
  

  然后把lambda里的a.weight换成a.getWeight()就ok了。

场景2：对整个外层嵌套向量按子向量的weight特征排序 #

如果你的需求是把外层的vector<vector<Edge>>本身排序（比如按每个子向量第一个Edge的weight，或者子向量里最大的weight降序），同样用std::sort，只是比较器要针对子向量来写：

示例1：按子向量第一个Edge的weight降序 #

std::sort(graph.begin(), graph.end(), [](const std::vector<Edge>& a, const std::vector<Edge>& b) {
    // 先处理空向量的情况，这里把空向量放后面
    if (a.empty() || b.empty()) {
        return !a.empty() && b.empty();
    }
    // 按第一个元素的weight降序
    return a[0].weight > b[0].weight;
});

示例2：按子向量中最大的weight降序 #

先写个辅助函数找子向量的最大weight，再排序：

#include <climits> // 用到INT_MIN

int getMaxEdgeWeight(const std::vector<Edge>& edgeList) {
    if (edgeList.empty()) {
        return INT_MIN; // 空向量用最小int值标记
    }
    int maxWeight = edgeList[0].weight;
    for (const auto& edge : edgeList) {
        if (edge.weight > maxWeight) {
            maxWeight = edge.weight;
        }
    }
    return maxWeight;
}

// 排序外层vector
std::sort(graph.begin(), graph.end(), [](const std::vector<Edge>& a, const std::vector<Edge>& b) {
    return getMaxEdgeWeight(a) > getMaxEdgeWeight(b);
});

不管哪种场景，核心都是利用std::sort的自定义比较器，灵活控制排序规则～

内容的提问来源于stack exchange，提问作者j doe