C++ 中向量的向量排序

Question

我们可以对向量的向量进行排序吗：

{[7, 2], [1, 8], [3, 4]}

使用std::sort(vec.begin(), vec.end()), 根据每个向量中的第一个元素按升序排列，或者我们是否需要将自定义比较器函数传递给std::sort？

Answer 1

您可以对向量的向量进行排序，而无需任何自定义比较器。如果您不提供，则会std::vector::operator<使用。该运算符对内部元素执行字典顺序比较。

例如：

#include <vector>
#include <iostream>
#include <algorithm>

int main()
{
    std::vector<std::vector<int>> vecs{{7, 2}, {1, 8, 5}, {3}};
    
    // until C++20
    std::sort(vecs.begin(), vecs.end());

    // since C++20
    std::ranges::sort(vecs);

    for (const auto &v : vecs) {
        for (int x : v) {
            std::cout << x << ' ';
        }
        std::cout << '\n';
    }
}

输出

1 8 5 
3 
7 2 

注意：operator<首先会比较第一个元素，如果两个向量相同，则会比较其余元素。如果您只想比较第一个元素以节省性能，您仍然需要一个自定义比较器，您可以执行以下操作：

// since C++11, could also be written as a lambda expression
struct first_element_compare {
    
    /* static since C++23*/
    constexpr bool operator()(const std::vector<int>& a,
                              const std::vector<int>& b) const
    {
        // FIXME: this code crashes when a or b is empty
        //        we must decide how these vectors compare to each other
        return a.front() < b.front();
    }
};

// ...

// until C++20
std::sort(vecs.begin(), vecs.end(), first_element_compare{});

// since C++20
std::ranges::sort(vecs, first_element_compare{});