使用内置函数(或其他方法)对c++中的2D数组进行排序?

I have a 2D array like below. ( array[5][2] )

我有一个二维数组，如下所示。(阵列[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 :)

提前谢谢:)

7 个解决方案

#1

I'm offering this up only because it was one of the few things std::qsort does well that std::sort simply 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.

注意:在比较国中，这特别使用了严格值比较，而不是减缩短节，以避免潜在的欠流问题。如果在受限制的数据空间中这不是一个问题，那么可以轻松地使比较器更简单。

#2

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::数组的属性，默认情况下，'<'会在字典上对它们进行比较，也就是说，从第一个元素开始。为了对事物进行不同的排序，我们必须找到一个比较器对象，所以如果你想用第二列作为排序键，你必须这样做:

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……)是一种难看的简写形式，用于更简洁的分类(std::begin(a)， std::end(a)…

#3

If you can, use Vector with some struct to hold two int:

如果可以，使用带有结构体的向量来容纳两个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 });

#4

To be honest, since you have only two ints in 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 arr[200]这样的函数，就可以调用内建的sort函数排序(arr, arr + 200)，它会按第一个元素和第二个元素对数组进行排序。 ,int>

#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

请注意第二个元素也是如何排序的，但是是次要的

#5

First off, if you'd given vector<vector<int>> array this would be sortable just using: sort(begin(array), end(array)) because vector defines lexicographic comparison functions: http://en.cppreference.com/w/cpp/container/vector/operator_cmp

首先，如果给定向量 >数组，只需使用:sort(begin(array)， end(array))就可以排序，因为vector定义了字典比较函数:http://en.cppreference.com/w/cpper/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 sort will yield:

也就是说，使用矢量矢量有缺点:矢量矢量的问题是什么?这显然不是你想要的。给定int数组[5][2]尝试使用sort会得到:

error C3863: array type 'int [2]' is not assignable

错误C3863:数组类型'int[2]'不能赋值

Instead of using swap to exchange 2 int[2]s we need to simply need to swap bytes of sizeof(*array), that can be accomplished using qsort as 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:

我们不需要使用交换来交换2个int[2]，我们只需要交换sizeof(*array)的字节，这可以使用qsort完成，正如WhozCraig的回答所建议的，但是我们可以改进使我们的比较器能够处理任何大小的子数组。给定int数组[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 array should 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/87AoIr

快速注释数组不应该用作变量名，因为它定义了一个标准类型，您可以在这里找到一个示例:http://ideone.com/87AoIr

#6

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 m back to your array

现在可以将m复制回数组

std::size_t  i=0;
for(const auto& x:m)
{   
    array[i][0] = x.first ;
    array[i++][1] = x.second ;
}

#7

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)

对2D数组进行及时排序的最快方法(仅使用列)...将花费您引用局部性…另外，每一种方法都需要大量的拷贝。尽管(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。