c++ - 用于增加 "vector<pair>"值的优雅而高效的算法

Question

我需要在 vector<pair<int, float>> 中找到一个元素并增加第二个值。 我尝试了一种方法。

template <typename K, typename V>
struct match_first {
    const K _k; match_first(const K& k) : _k(k) {}
    bool operator()(const pair<K, V>& el) const {
        return _k == el.first;
    }
};

例如使用.:

vector< pair<int, float> > vec;
vec.push_back(make_pair(2, 3.0));
vec.push_back(make_pair(3, 5.0));
vec.push_back(make_pair(1, 1.0));

vector< pair<int, float> >::iterator it = find_if(vec.begin(), vec.end(), match_first<int, float>(3));
if (it != vec.end()) {
    it->second += 9;
}

有没有更有效的方法来完成这项任务？

Answer 1

map 看起来更自然:

#include <map>

int main()
{
    std::map<int, float> m;
    m.insert(std::make_pair(2, 3.0));
    m.insert(std::make_pair(3, 5.0));
    m.insert(std::make_pair(1, 1.0));

    auto it = m.find(3);
    if (it != m.end()) {
        it->second += 9;
    }
}

它也会更快，因为查找是 O(log(n))

您可以通过使用 std::lower_bound(或 std::equal_range 如果键可以重复)