Эффективный способ вычисления среднего значения по непересекающимся поддиапазонам карты STL

Я конвертирую алгоритм с 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 ограничены, поэтому мне действительно сложно выбрать решение, тем более что существует множество разных мнений. Было бы здорово, если бы кто-нибудь мог помочь мне с решением, сравнив решения, размещенные здесь. Чтобы дать вам немного дополнительной справочной информации:

Функция будет вызываться примерно 500 раз с 1000 значениями на карте. Самым важным аспектом является стабильность, производительность - на втором месте.