如何用vector<pair<int,int>>替代unordered_map统计元素频率？

因为vector<pair<int,int>>没有内置的键值查找机制，不像unordered_map那样可以直接通过mp[element]++操作，所以需要手动实现查找和更新逻辑，下面给两种可行的方式：

方式一：手动遍历vector #

直接遍历整个vector，找到目标元素就更新频率，没找到就新增元素：

// 更新元素频率的函数
void updateFreq(vector<pair<int, int>>& freqVec, int element) {
    for (auto& item : freqVec) {
        if (item.first == element) {
            item.second++;
            return;
        }
    }
    // 没找到就添加新元素，初始频率为1
    freqVec.emplace_back(element, 1);
}

方式二：使用标准库的find_if算法 #

借助<algorithm>头文件里的find_if，用lambda表达式匹配目标元素，代码更简洁：

#include <algorithm>

void updateFreq(vector<pair<int, int>>& freqVec, int element) {
    auto it = find_if(freqVec.begin(), freqVec.end(), 
        [element](const pair<int, int>& item) {
            return item.first == element;
        });
    
    if (it != freqVec.end()) {
        it->second++;
    } else {
        freqVec.emplace_back(element, 1);
    }
}

注意事项 #

• 这两种方式的时间复杂度都是O(n)，而unordered_map的查找更新是O(1)，如果你的数据量很大，这种vector的方式会比原来的哈希表慢不少，需要权衡插入顺序和性能的需求。
• 调用的时候直接传入你的vector和要统计的元素即可，比如：

vector<pair<int, int>> myFreqVec;
updateFreq(myFreqVec, 5);
updateFreq(myFreqVec, 3);
updateFreq(myFreqVec, 5); // 此时5的频率会变成2

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