如何对已排序pair向量中同首元素项求均值并存入std::map

因为你的输入std::vector<std::pair<int, double>>已经按pair首元素升序排序，相同首元素的项连续存储，直接一次线性遍历即可完成分组平均值计算，时间复杂度为O(n)，实现代码如下：

#include <vector>
#include <map>
#include <utility>

int main() {
    // 你的已排序test向量
    std::vector<std::pair<int, double>> test;
    test.push_back(std::make_pair(1,100.0));
    test.push_back(std::make_pair(1,200.0));
    test.push_back(std::make_pair(1,400.0));
    test.push_back(std::make_pair(2,200.0));
    test.push_back(std::make_pair(2,300.0));
    test.push_back(std::make_pair(3,100.0));
    std::map<int, double> test2;

    if (test.empty()) {
        return 0; // 空向量直接返回
    }

    int current_key = test[0].first;
    double sum = 0.0;
    int count = 0;

    for (const auto& item : test) {
        if (item.first == current_key) {
            sum += item.second;
            count++;
        } else {
            // 计算上一组平均值存入结果
            test2[current_key] = sum / count;
            // 重置为新组的初始状态
            current_key = item.first;
            sum = item.second;
            count = 1;
        }
    }
    // 处理最后一组数据
    test2[current_key] = sum / count;

    return 0;
}

通用实现（无需提前排序） #

如果你后续遇到输入向量未排序的场景，可以用临时结构存储每个key的总和与计数，遍历完成后再计算平均值，实现如下：

#include <vector>
#include <map>
#include <utility>

int main() {
    std::vector<std::pair<int, double>> test;
    // 此处省略test初始化代码
    std::map<int, double> test2;
    // 临时结构：key对应<总和, 出现次数>
    std::map<int, std::pair<double, int>> temp;

    for (const auto& item : test) {
        temp[item.first].first += item.second;
        temp[item.first].second += 1;
    }

    // 计算平均值存入结果
    for (const auto& entry : temp) {
        test2[entry.first] = entry.second.first / entry.second.second;
    }

    return 0;
}

如果对性能要求更高且不需要结果按key排序，可以把std::map替换为std::unordered_map减少插入开销

内容的提问来源于stack exchange，提问作者pennyBoy