在STL图的不相交子范围上计算平均值的有效方法

Question

我正在将算法从C#转换为C++.该算法的一小部分是计算字典中某些区域的平均值.

字典中的数据按以下方式存储:

Index     Value
1         10
3         28
290       78
1110      90

我需要计算索引小于某个数字的所有值的平均值,并且所有索引值都大于某个数字.在C#中我按以下方式执行:

if (dictionary.Where(x => x.Key < areaWidth).Count() > 0)
{
    avgValue = (int) dictionary.Where(x => x.Key < areaWidth).Average(
        x => x.Value);
}

for (var i = 0; i < line.Length; i++)
{
    if (i == areaWidth)
    {
        avgValue = -1;
        i = line.Length - areaWidth;
        var rightBorder = i - areaWidth;

        if (dictionary.Where(x => x.Key > (rightBorder)).Count() > 0)
        {
            avgValue = (int) dictionary.Where(
                x => x.Key > (rightBorder)).Average(
                                x => x.Value);
        }
    }

    if (line[i] < avgValue * 0.8)
    {
        reallyImportantValue += (avgValue - line[i]);
    }
}

我知道这不是非常有效且非常糟糕的代码,但我知道我必须在C++中完全重写这部分算法,所以我决定快速而肮脏地实现它.

无论如何,我现在将其移植到C++,因为它将在移动平台上运行,性能非常重要.凭借我有限的C++/STL知识,我很可能完成工作,但结果可能比C#代码更糟糕.

因此,如果您知道在C++中完成此任务的有效方法,请告诉我.

---

编辑:谢谢你的所有答案.正如我在帖子中提到的,我的STL知识是有限的,所以我很难选择一个解决方案,特别是因为有很多不同的意见.如果有人能够通过比较这里发布的解决方案来帮助我做出决定,那将是很棒的.为您提供更多背景信息:

该函数将在地图中使用1000个值调用大约500次.最重要的方面是稳定性,性能是第二重要的.

Answer 1

std::map 中的键值对按键排序 - 即使使用 for 循环，也可以轻松地将小于或大于某个值的键指向的值相加（如果您不想使用或学习使用 STL 算法）。对于低于 some 的键value：

std::map<int, int> map;
map[...] = ...;

int count = 0, sum = 0;
for (std::map<int, int>::const_iterator it = map.begin();
     it != map.end() && it->first < value; ++it, ++count)
{
    sum += it->second;
}
// check for count == 0
int avg = sum / count; // do note integer division, change if appropriate

对于大于值的键的平均值，请使用map.rbegin()（类型std::map<...>::const_reverse_iterator）map.rend()和>。

编辑：STL 算法可能会使代码更短（即使用的地方）。例如，计算以下键的平均值value。

int ipsum(int p1, const std::pair<int, int>& p2) {
    return p1 + p2.second;
}

...

std::map<int, int> map;
int sum = std::accumulate(map.begin(), map.lower_bound(value), 0, ipsum);