如何对一组对进行排序？

Question

我该如何使用qsort函数对一组对进行排序？这是我的设定：

set< pair< int, int> > my_set                        

我想这应该是我的比较功能：

int compare (const void * a, const void * b)
{
    return ( *(int*)a - *(int*)b );
}

我的qsort应该是这样的吗？

qsort (my_set, no_of_pairs, sizeof(int), compare);

当我对它们进行排序时，我想按二维数组**M;的值进行排序，其中

 M[my_set.first][my_set.second] = the_value 

Answer 1

首先，首选使用c ++ std容器将std :: sort转换为qsort。其次，你不能对std :: set a posteriori进行排序。 std::set已分拣。但是，您可以使用第二个模板参数为instanciation的std :: set指定自定义排序。请参阅规格。

如果你需要在事后对数据进行排序，你可以做的是使用std :: vector。有一种算法可以剔除重复值。

该提出的解决方案假设M是一些全局变量。

#include <algorithm>

bool less_than(const std::pair<int, int> &some, const std::pair<int, int> &other) {
    return M[some.first][some.second] < M[other.first][other.second]; 
}

std::sort(yourvector.begin(), yourvector.end(), less_than);

如果M不是全局变量，你可以这样做：

struc Compair { // see what I did there ? #sofunny
    bool operator() (const std::pair<int, int> &some, const std::pair<int, int> &other) {
        return M[some.first][some.second] < M[other.first][other.second]; 
    }
    int **M;
}

然后在主要：

Compair mycomparefunctor;
mycomparefunctor.M = arr; // arr is the original int **
std::sort(yourvector.begin(), yourvector.end(), mycomparefunctor);

编辑：

如果你必须使用std::set，那么你应该在声明它时定义自定义顺序，如下所示：

Compair mypredicate;
mypredicate.M = arr; // arr is the original int **

std::set<std::pair<int, int>, mypredicate> myset;
// add stuff to the set. They will be sorted following your predicate.

但要小心：在一个集合中，你不能添加两个相等的项目。因此，如果您的int ** 2D数组具有多个相等的值，则您将无法在该集合中具有与值相等的索引对应的多个对。

Answer 2

你说这个错了。

假设我们知道该对中每个成员的最大值。如果您不知道这一点，那么您需要弄明白。我将假设它是100。

然后我们需要做的就是遍历集合，并将它们插入到新数组中。没有更快的方法来解决这个问题。

int M[100][100] = {};
for (auto const & pair : my_set)
    M[pair.first][pair.second] = the_value;