使用重复的整数键在 C++ 哈希映射中高效插入或更新整数值

Question

我正在使用 C++ 中的

std::unordered_map<int, int>

，其中键和值都是整数。我的数据集包含许多重复的键。对于数据中的每个键值对：

如果映射中不存在该键：插入该键及其对应的值。 如果键已存在：通过向其中添加新值来更新现有值（即，map[key] = map[key] + newValue）。 目前，我在插入或更新之前检查密钥是否存在：

if (map.count(key) > 0) {
    // Key exists, update the value
    map[key] += newValue;
} else {
    // Key does not exist, insert the key-value pair
    map[key] = newValue;
}

但是，我担心在每次插入之前执行此存在性检查可能会将大型数据集的总体时间复杂度增加到 O(n²)。

是否有更有效的方法来处理在映射中插入或更新值，而无需每次显式检查键是否存在？

Answer 1

为什么你不使用 C++11 中的

unordered_map

或

unordered_multimap

或使用其对应的

boost

??

您也可以这样做：

auto i = map.find( "key" );
if( i == map.end() ) {insert into map}
i->second = new value;

如果值已存在于地图中，则使用此技术，您无需检查。并且根据

map

（甚至

unordered_map

）

map["key"]

将创建项目（如果它不存在）并默认初始化它!!

Answer 2

Lets say, you have a *map named* `m`, with **integer** `b` as value and `s` (can be of any data type, doesn't matter) as **key**, then you can use following snippet(C++):

auto i=m.find(s);              // iterator for map
if(i==m.end())             // element not found, if iterator reaches at end
    m.insert(make_pair(s,b));  // element inserted as new pair
else
{
    cin>>p;
    i->second+=p;          // accessing 'value' for given key and 
                           // incrementing it by p 
}