使用内置函数（或任何其他方法）在 C++ 中对二维数组进行排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20931669/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sort a 2D array in C++ using built in functions(or any other method)?
提问by prime
I have a 2D array like below. ( array[5][2])
我有一个像下面这样的二维数组。( array[5][2])
20 11
10 20
39 14
29 15
22 23
after sorting it should be like below.
排序后应该如下所示。
10 20
20 11
22 23
29 15
39 14
that means the array should be sorted comparing the first column values only.
这意味着数组应该只比较第一列的值进行排序。
In Java there is a built in function capability to do that. like below.
在 Java 中有一个内置的函数功能可以做到这一点。像下面。
Arrays.sort(a, new Comparator<Long[]>() {
@Override
public int compare(Long[] o1, Long[] o2) {
Long t1 = o1[1];
Long p1 = o1[0];
Long t2 = o2[1];
Long p2 = o2[0];
if (t1 == t2) {
return (p1 > p2 ? 1 : (p1 == p2 ? 0 : -1));
} else {
return (t1 < t2 ? -1 : 1);
}
}
});
So is there any C++ built in function capability to do these kind of stuff or how can i do this in C++ (the fastest implementation) ?
那么是否有任何 C++ 内置函数功能来执行这些操作，或者我如何在 C++（最快的实现）中执行此操作？
Thanks in advance :)
提前致谢 ：）
回答by WhozCraig
I'm offering this up only because it was one of the few things std::qsortdoes wellthat std::sortsimply does not, namely sort multi-column fixed arrays: The comparator is a string of ternary statements, but should be clear enough if you stare at it long enough:
我提供这个只是因为它是为数不多的std::qsort做的很好但std::sort根本做不到的事情之一，即对多列固定数组进行排序：比较器是一串三元语句，但如果你长时间盯着它应该足够清楚足够的：
#include <iostream>
#include <random>
#include <algorithm>
int main()
{
int ar[10][2];
// populate with random data
std::random_device rd;
std::default_random_engine rng(rd());
std::uniform_int_distribution<> dist(1,20);
std::for_each(std::begin(ar), std::end(ar),
[&](int (&ar)[2]){ ar[0] = dist(rng); ar[1] = dist(rng); });
std::cout << "Before Sort..." << '\n';
std::for_each(std::begin(ar), std::end(ar),
[](const int(&ar)[2]) { std::cout << ar[0] << ',' << ar[1] << '\n';});
std::qsort(ar, 10, sizeof(*ar),
[](const void *arg1, const void *arg2)->int
{
int const *lhs = static_cast<int const*>(arg1);
int const *rhs = static_cast<int const*>(arg2);
return (lhs[0] < rhs[0]) ? -1
: ((rhs[0] < lhs[0]) ? 1
: (lhs[1] < rhs[1] ? -1
: ((rhs[1] < lhs[1] ? 1 : 0))));
});
std::cout << "After Sort..." << '\n';
std::for_each(std::begin(ar), std::end(ar),
[](const int(&ar)[2]) { std::cout << ar[0] << ',' << ar[1] << '\n';});
return 0;
}
Sample Run(yours will vary, obviously)
样品运行（你的会有所不同，显然）
Before Sort...
2,11
18,4
20,20
14,6
8,10
17,8
14,14
3,10
20,14
19,19
After Sort...
2,11
3,10
8,10
14,6
14,14
17,8
18,4
19,19
20,14
20,20
Notes: this specifically uses strict-value comparison rather than subtraction short-cuts in the comparator so as to avoid potential underflow issues. If that is not a problem in your restricted data-space, you could easily make that comparator significantly simpler.
注意：这在比较器中专门使用了严格值比较而不是减法捷径，以避免潜在的下溢问题。如果这在您受限的数据空间中不是问题，您可以轻松地使该比较器变得更加简单。
回答by pentadecagon
The built-in arrays of C and C++ are very inflexible, among other things they cannot be assigned.
C 和 C++ 的内置数组非常不灵活，除其他外，它们不能被赋值。
Your best option would be the 'array' class from the C++ standard library, at least for the inner dimension:
您最好的选择是来自 C++ 标准库的“数组”类，至少对于内部维度：
array<int, 2> a[5] = { { 20, 11 },
{ 10, 20 },
{ 39, 14 },
{ 29, 15 },
{ 22, 23 } };
sort( a, a + 5 );
Edit: Some more explanations.
编辑：一些更多的解释。
Here we use the property of std::array that '<' by default compares them lexicographically, i.e. starts with the first element. In order to sort things differently we have to come up with an comparator object, so if you want to use the second column as sort key you have to do this:
这里我们使用 std::array 的属性，默认情况下 '<' 按字典顺序比较它们，即从第一个元素开始。为了以不同的方式对事物进行排序，我们必须提出一个比较器对象，因此如果您想使用第二列作为排序键，您必须这样做：
auto comp = []( const array<int, 2>& u, const array<int, 2>& v )
{ return u[1] < v[1]; };
sort( a, a + 5, comp );
And as mentioned in the first comment, sort(a, a+5 ...is just an ugly short form for the cleaner sort(std::begin(a), std::end(a) ...
正如第一条评论中提到的，sort(a, a+5 ...对于清洁工来说只是一个丑陋的简短形式sort(std::begin(a), std::end(a) ...
回答by NL628
To be honest, since you have only two intsin your second dimension, I would use instead an array of pairs, which have their own built in comparison function. With something like pair<int,int> arr[200], you would be able to call the built in sort function sort(arr, arr + 200), which would sort your array by first element, and then by the second element.
老实说，因为你ints的第二维只有两个，我会用一个对的数组来代替，它们有自己的内置比较函数。使用类似pair<int,int> arr[200]，您将能够调用内置的 sort 函数sort(arr, arr + 200)，该函数将按第一个元素对数组进行排序，然后按第二个元素排序。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
// pair of integers
pair<int, int> arr[1000];
// fill array with random numbers
random_device rd;
mt19937 rng(rd());
uniform_int_distribution<int> uni(0,1000);
for(int i = 0; i < 10; i++) {
// make_pair(x, y) creates a pair with two integers x and y
arr[i] = make_pair(uni(rng), uni(rng));
}
// prints out initial array
cout << "BEFORE ARRAY..." << endl;
for(int i = 0; i < 10; i++) {
// .first and .second call the first and second ints in the pair respectively
cout << arr[i].first << " " << arr[i].second << endl;
}
cout << endl;
// sort the array by calling built in sort function
sort(arr, arr + 10);
// prints out array
cout << "FINAL ARRAY..." << endl;
for(int i = 0; i < 10; i++) {
cout << arr[i].first << " " << arr[i].second << endl;
}
cout<<endl;
}
When you run this program, you see that the arrays are now sorted:
运行此程序时，您会看到数组现在已排序：
BEFORE ARRAY...
726 562
916 348
594 6
515 872
976 960
662 169
529 317
789 702
74 255
330 574
FINAL ARRAY...
74 255
330 574
515 872
529 317
594 6
662 169
726 562
789 702
916 348
976 960
Note how the second elements are also sorted, but secondary to the
注意第二个元素也是如何排序的，但次于
回答by MRB
If you can, use Vectorwith some struct to hold two int:
如果可以，请使用Vector一些结构来保存两个int：
typedef std::pair<int, int> pairType;
std::vector<pairType> vec;
// Initialize vector
std::sort(std::begin(vec), std::end(vec), [](pairType& first, pairType& second)->bool { return first.first < second.first });
回答by Jonathan Mee
First off, if you'd given vector<vector<int>> arraythis would be sortable just using: sort(begin(array), end(array))because vectordefines lexicographic comparison functions: http://en.cppreference.com/w/cpp/container/vector/operator_cmp
首先，如果你给出vector<vector<int>> array这将是可排序的：sort(begin(array), end(array))因为vector定义字典比较函数：http: //en.cppreference.com/w/cpp/container/vector/operator_cmp
That said, there are drawbacks to using a vector-of-vectors: What are the Issues with a vector-of-vectors?and it's clearly not what you intended. Given int array[5][2]trying to use sortwill yield:
尽管如此，也有缺点使用vector-OF- vectorS：什么问题与向量的向量？这显然不是你想要的。鉴于int array[5][2]尝试使用sort将产生：
error C3863: array type 'int [2]' is not assignable
错误 C3863：数组类型“int [2]”不可分配
Instead of using swapto exchange 2 int[2]s we need to simply need to swap bytes of sizeof(*array), that can be accomplished using qsortas suggested by WhozCraig's answer, but we can improve upon that making our comparator capable of handling any size sub-array. Given int array[5][2]or whatever dimensions are desired we can write:
而不是swap用于交换 2 int[2]s，我们只需要交换 的字节sizeof(*array)，这可以按照WhozCraig 的回答的qsort建议使用来完成，但我们可以改进这一点，使我们的比较器能够处理任何大小的子数组。给定或任何需要的维度，我们可以写：int array[5][2]
static const auto SIZE = size(*array);
qsort(array, size(array), sizeof(*array), [](const auto lhs, const auto rhs) {
const auto first = reinterpret_cast<const int*>(lhs);
const auto last = next(first, SIZE);
const auto its = mismatch(first, last, reinterpret_cast<const int*>(rhs));
if (its.first == last) {
return 0;
} else if (*its.first < *its.second) {
return -1;
} else {
return 1;
}});
A quick note arrayshould not be used as a variable name as it defines a standard type, with this change you can find an example here: http://ideone.com/87Atheitroad
快速注释array不应用作变量名称，因为它定义了标准类型，通过此更改，您可以在此处找到示例：http: //ideone.com/87Atheitroad
回答by WhiZTiM
The fastest way to sort a 2D array in time(using only columns) . . .will cost you reference locality... Else, every other way will involve lots of copying of rows.. . . Though (C++'s move operations may cushion this)
及时对二维数组进行排序的最快方法（仅使用列）。. .将花费你参考位置......否则，所有其他方式都将涉及大量的行复制...... . 虽然（C++ 的移动操作可能会缓冲这个）
You would create a new array of pointers to a 2D array... Then sort the pointers...
您将创建一个指向二维数组的新指针数组...然后对指针进行排序...
Else, every other answer before mine seems good. But I advise you to use std::array.
否则，我之前的所有其他答案似乎都不错。但我建议你使用 std::array。
回答by P0W
If end container doesn't matter, how about using a map ?
如果终端容器无关紧要，那么使用地图怎么样？
#include<map>
std::map<int, int> m;
for(std::size_t i = 0; i < 5; ++i )
m[array[i][0]] = array[i][1] ;
You can now copy mback to your array
您现在可以复制m回您的array
std::size_t i=0;
for(const auto& x:m)
{
array[i][0] = x.first ;
array[i++][1] = x.second ;
}
