对二维向量进行排序但得到意外输出

Question

我正在尝试对 2 D 向量进行排序，并且我得到了输入 'n' 小于 15 但大于 15 的所需输出，它没有按我想要的顺序排列。如果第一列的所有值均为 0，则第二列的值必须递增。

#include <bits/stdc++.h>
using namespace std;
bool sortcol(const vector<long long int>& v1, const vector<long long int>& v2)
{
    return v1[0] < v2[0];
}
int main()
{
    int n;
    cin >> n;
    
    vector<vector<long long int>> arr(n,vector<long long int> (2));
    
    for (int i = 0; i < n; i++)
    {
         arr[i][0] = 0;
         arr[i][1] = i;
    }
    
    
    sort(arr.begin(), arr.end(),sortcol);
    for(int i = 0;i<n;i++){
        cout << i << " - " << arr[i][0] << " , " << arr[i][1] << endl;
    }
}

我想要的输出：-

15 0
0 - 0 , 0
1 - 0 , 1
2 - 0 , 2
3 - 0 , 3
4 - 0 , 4
5 - 0 , 5
6 - 0 , 6
7 - 0 , 7
8 - 0 , 8
9 - 0 , 9
10 - 0 , 10
11 - 0 , 11
12 - 0 , 12
13 - 0 , 13
14 - 0 , 14

但我得到的是：-

50 0
0 - 0 , 38
1 - 0 , 26
2 - 0 , 27
3 - 0 , 28
4 - 0 , 29
5 - 0 , 30
6 - 0 , 31
7 - 0 , 32
8 - 0 , 33
9 - 0 , 34
10 - 0 , 35
11 - 0 , 36
12 - 0 , 37
13 - 0 , 25
14 - 0 , 39
15 - 0 , 40
16 - 0 , 41
17 - 0 , 42
18 - 0 , 43
19 - 0 , 44
20 - 0 , 45
21 - 0 , 46
22 - 0 , 47
23 - 0 , 48
24 - 0 , 49
25 - 0 , 13
26 - 0 , 1
27 - 0 , 2
28 - 0 , 3
29 - 0 , 4
30 - 0 , 5
31 - 0 , 6
32 - 0 , 7
33 - 0 , 8
34 - 0 , 9
35 - 0 , 10
36 - 0 , 11
37 - 0 , 12
38 - 0 , 0
39 - 0 , 14
40 - 0 , 15
41 - 0 , 16
42 - 0 , 17
43 - 0 , 18
44 - 0 , 19
45 - 0 , 20
46 - 0 , 21
47 - 0 , 22
48 - 0 , 23
49 - 0 , 24

我是运行 VS code 上的这段代码

Answer 1

正如其他人在评论中指出的那样，您的 sortcol() 始终 returns false 因为 v1[0] 和 v2[0] 始终为 0。由于谓词sortcol() 告诉排序算法哪些元素被认为比其他元素“更小”/“更少”，没有元素被认为比另一个元素小。这意味着所有元素都被认为是相等的：如果 a<b 为假且 b<a 为假，这意味着 a==b 为真。换句话说，STL 排序算法采用严格的弱排序，比较例如this post and this one.

所以你的所有元素都被排序算法认为是相等的。被视为相等的元素的顺序是为 std::sort() 定义的实现。 Quote for std::sort:

The order of equal elements is not guaranteed to be preserved.

因此，在您的情况下，实现可以根据需要自由更改所有元素的顺序，因为所有元素都被认为是相等的。实际上，一旦输入达到一定大小，就会使用不同的算法，在这种情况下，会选择不同的算法。对于 libstdc++（gcc 的 STL），n>16 会发生这种情况（请参阅源代码中的 constant _S_threshold）。这就是为什么您看到 n>16 和 std::sort() 的行为跳跃的原因。 STL 的其他实现可能使用其他阈值（例如，Microsoft STL 似乎使用 a value of 32）。

另一方面，std::stable_sort()保证相等元素的顺序保持不变。 Quote for std::stable_sort:

The order of equivalent elements is guaranteed to be preserved.

当然，保留顺序不是免费的，因此 std::stable_sort 可能会更慢。

因此，如果您的 sortcol() 确实是您想要的谓词（尽管在示例中它并没有多大意义），那么使用 std::stable_sort() 就是您要寻找的解决方案。

对二维向量进行排序但得到意外输出

Sorting a 2-d vector but getting an unexpected output

c++

sorting

multidimensional-array

vector