[C++][std::sort] 它如何在 2D 容器上工作？

Question

我有这个矢量对象，其中包含 ints

的矢量

std::vector<std::vector<int>> vec;

我一直在努力弄清楚 std::sort(vec.begin(), vec.end()) 是如何处理它的。以下是我的观察：

二维向量按大小排序。
如果一些内部向量具有相同的大小，则第一个元素值较小的向量将具有较小的索引值。

我现在一直在生成一些二维向量，似乎这两个总是正确的。但是，我怀疑我的第二个假设。 std::sort 真的是这样吗，还是只是运气让我的假设正确？

Answer 1

对矢量元素进行排序与对任何其他类型进行排序的方式相同。 std::sort 使用给定的比较对象作为参数。如果 none 被显式传递，则 std::less 是默认值。

std::less 使用 operator<。根据矢量文档，它：

Compares the contents of lhs and rhs lexicographically. The comparison is performed by a function equivalent to std::lexicographical_compare.

Lexicographical comparison is a operation with the following properties:

Two ranges are compared element by element.

The first mismatching element defines which range is lexicographically less or greater than the other.

If one range is a prefix of another, the shorter range is lexicographically less than the other.

If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal.

An empty range is lexicographically less than any non-empty range.

Two empty ranges are lexicographically equal.

简而言之，词典排序与用于词典的排序相同（忽略某些语言的奇怪之处）。

2D vectors are sorted by size.

不完全是。 {1}, {3, 4}, {1, 2, 5} 将被排序为 {1}, {1, 2, 5}, {3, 4}。

Answer 2

std::sort默认使用operator <排序。由于 std::vector 有一个重载的 operator < 它使用它。 std::vector::operator < 进行字典序比较，这意味着它 returns 具有第一个较小元素的向量。这意味着 {1, 1, 2} 小于 {1, 1, 3}，因为 2 小于 3。如果向量的长度不同，但较小的向量与较大的向量具有相同的元素，则返回较小的向量。也就是说

int main()
{
    std::vector a{5, 1}, b{10};
    std::cout << (a < b);
}

打印 1 因为 5 小于 10.

int main()
{
    std::vector a{5, 10}, b{5};
    std::cout << (a < b);
}

打印 0，因为 a 比 b 大，但它们具有相同的公共元素。

[C++][std::sort] 它如何在 2D 容器上工作？

[C++][std::sort] How does it work on 2D containers?

c++

sorting

stdvector