1

我需要在 a 中找到一个元素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;
}

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

4

4 回答 4

3

地图似乎更自然：

#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_boundstd::equal_range

于 2013-09-08T19:43:15.883 回答
0

这取决于你的约束。如果您有唯一键（第一个元素），您可以使用它std::map<K,V>来保存您的对象。然后增加它很容易。如果V有一个默认构造函数将其初始化为零，您甚至可以跳过添加新元素而只是递增（我不确定它是否可以与整数一起使用）。

std::map<K,V> data;
data[key] = data[key] + 1;

[]用于不存在键的运算符将使用其默认构造函数为您创建对象。仅访问数据使用at或find方法。

于 2013-09-08T19:47:03.327 回答
0

扩展 sehe 的答案：std::multimap如果您可能有重复的键，您可以以相同的方式使用。这个容器还保持<K,V>对排序（键）的顺序，所以二进制搜索方法显然加快了速度。

于 2013-09-08T19:48:45.440 回答
0

您的问题没有确切的答案：这取决于。

我的第一个答案是：使用std::find_if（在<algorithm>C++ 标准库的一部分中可用），然后分析您的代码。如果搜索结果是一个值得关注的瓶颈，那么尝试另一种方法。

小心使用 a std::map，因为它会按它们的第一个组件对对进行排序（也就是说，插入顺序将丢失）。此外，它不允许您存储具有相同第一个组件的两对。

正如其他人所提到的，您可以解决这些警告（如果它们确实是对您的问题的警告），但是，就像我之前提到的那样，只有在您首先证明搜索结果是一个瓶颈之后才值得您花时间使用标准算法。

于 2013-09-08T20:05:47.397 回答