c++ - 根据 C++ 中的列对具有 double 的 vector 的 vector 进行排序

Question

我有一个由 vector ​​组成的矩阵，其中代表行的每个元素都由代表矩阵列的 vector 组成。我想根据第一列对行进行排序。

这个矩阵中的每个元素都是一个double，尽管第一列包含一个用作标识符的数字(但不是唯一的)。

我的目标是在按第一列分组时使用类似于 SQL 中聚合函数的功能，例如 count() 和 sum()。

例如，如果我有:

ID       VALUE
1        10
2        20
1        30
2        40
3        60

我想得到:

ID       COUNT      MEAN
1        2          20
2        2          30
3        1          60

但是，我卡在了第一步:如何根据每行第一个元素的值对行进行排序？

我找到了一条线索 on this topic ，并将比较器修改为:

bool compareFunction (double i,double j)
{
    return (i<j);
}

但编译器对此不太满意(引用 STL_algo.h 文件):

error: cannot convert 'std::vector<double>' to 'double' in argument passing

因此我想知道是否有一种方法可以对包含 double 的 vector 进行排序。

Answer 1

答案(恕我直言):使用不同的数据结构。您要做的是设置 multimap 。哦，嘿，看:

http://www.cplusplus.com/reference/map/multimap/

stl::multimap - how do i get groups of data?

对于大量元素，它会更快。并且实际上是一个映射而不是 double vector 的 vector 。

或者，或者一起跳过排序，并使用 std::map、std::unordered_map 按键计数，或者(如果您知道键的数量和/或键被 1 偏移而没有中断) std::vector.

要扩展，对列表进行排序以获取均值会很慢。排序(使用 std::sort)是 O(nlogn)，每次计算这个平均值时都会是 O(nlogn)。这是一个不必要的步骤:你的东西是按关键分组的，而不考虑顺序。 std::map 和 std::multimap 将“边走边排序”，这将比每次排序快一点，但您不必对整个事物进行排序以获得列表。然后你可以迭代 multimap 以获得平均值，O(n)每个平均值计算。 (将所有元素添加到multimap仍然是O(nlg(n)))

但是如果您知道关键输出将是 1,2,3...n-1,n，那么排序完全是浪费时间。只需为每个键创建一个计数器(因为您知道键可以是什么)并在迭代数组时添加到键中。

但还有更多

如果 key 实际上是按照您的想法设置的，那么从一开始最好的方法就是忘记表结构，然后像这样构建它:

Index       VALUE
0           10,30
1           20,40
2           60

Count 现在是每行的常数时间。每行的平均值为 O(n)。获取列表是每一行的恒定时间。人人皆赢。