C++二维vector的stl::sort()默认排序行为及平局处理、比较器问询

默认排序行为 #

stl::sort 默认使用 std::less<T> 作为比较器，对二维vector（比如 vector<vector<int>>）执行字典序排序：

• 优先比较两个子vector的第一个元素，元素值更小的子vector排在前面；
• 若第一个元素相等，则继续比较第二个元素，以此类推；
• 若其中一个子vector是另一个的前缀（比如 [1,2] 和 [1,2,3]），则长度更短的子vector排在前面。

举个实际例子：

vector<vector<int>> data = {{3}, {1,2}, {1,1}, {2}};
sort(data.begin(), data.end());
// 排序后结果：{{1,1}, {1,2}, {2}, {3}}

平局情况的处理 #

当两个子vector完全相等（长度相同且所有对应元素都相等）时，stl::sort 作为不稳定排序，不会保留它们原来的相对顺序。也就是说，排序后这两个子vector的位置可能互换，没有固定的顺序保证。

默认比较器的工作机制 #

默认比较器 std::less<vector<T>> 依赖于vector的operator<实现，具体逻辑如下：

1. 逐元素调用元素类型的operator<进行比较，直到找到第一对不相等的元素；
2. 根据这对元素的比较结果，直接确定两个vector的大小关系；
3. 如果所有已比较的元素都相等，则比较两个vector的长度：长度更短的vector被判定为更小；
4. 若两个vector长度相同且所有元素都相等，operator<返回false，此时std::less认为两者“不满足前者小于后者”，排序时它们的相对顺序由sort的底层实现决定（无固定保证）。

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