如何在列表上执行GroupBy Sum查询？

Question

背景

我尽可能地使用C＃.Net + LINQ，并在C ++开发中尝试我参与的项目。当然，我完全意识到C＃和C ++是两个不同的世界。

题

我有一个std::list<T>，其中T是一个结构如下：

struct SomeStruct{
    int id;
    int rate;
    int value;
};

我需要得到rate组和value总和的结果。如何在此列表中执行GroupBy Sum聚合函数？

例：

SomeStruct s1;
SomeStruct s2;
SomeStruct s3;

s1.id=1;
s1.rate=5;
s1.value=100;

s2.id=2;
s2.rate=10;
s2.value=50;

s3.id=3;
s3.rate=10;
s3.value=200;

std::list<SomeStruct> myList;
myList.push_front(s1);
myList.push_front(s2);
myList.push_front(s3);

有了这些输入，我想获得以下输出：

rate|value
----|-----
   5|  100
  10|  250

我发现了一些有希望的库，如CINQ和cppitertools。但由于缺乏足够的知识，我无法完全理解。如果有人引导我走向正确的方向会很棒，我更愿意学习新事物。

Answer 1

计算Group-By总和相对简单：

using sum_type = int; // but maybe you want a larger type
auto num_groups = max_rate + 1;
std::vector<sum_type> rate_sums(num_groups); // this is initialized to 0
for(const auto& s : myList) {
    rate_sums[s.rate] += s.value;
}

这是当rate值在0和max_rate之内时，max_rate相对于myList.size()不是太大;否则内存使用可能过多（并且你将初始化向量有一些开销）。

如果rate值分散在相对于myList.size()的大范围内，请考虑使用std::unoredered_map而不是std::vector）。

上面的代码也可以并行化。并行化的方式取决于您的硬件，并且有各种各样的库可以帮助您实现这一目标。在C ++ 20中可能有language facilities for parallelization。

但请记住，链接列表使用起来相当慢，因为您必须取消引用任意地址才能从一个元素到另一个元素。如果你能用std::vector或普通数组输入，那就会更快;如果你不能，那么打扰并行化可能毫无价值。