如何更改unordered_map中的键? [英] How to change the key in an unordered_map?

问题描述

我需要使用一个平均支持恒定时间查找的数据结构.我认为使用 std :: unordered_map 是一种很好的方法.我的数据是数字的集合".

I need to use a data structure which supports constant time lookups on average. I think that using a std::unordered_map is a good way to do it. My data is a "collection" of numbers.

|115|190|380|265|

这些数字不必按特定顺序排列.我需要大约 O(1)时间来确定此数据结构中是否存在给定的数字.我有一个使用 std :: unordered_map 的想法，它实际上是一个哈希表(我正确吗?).所以数字将是键，然后我将只有虚拟值.

These numbers do not have to be in a particular order. I need to have about O(1) time to determine whether or not a given number exists in this data structure. I have the idea of using a std::unordered_map, which is actually a hash table (am I correct?). So the numbers will be keys, and then I would just have dummy values.

因此，基本上我首先需要确定与给定数字匹配的键是否存在于数据结构中，然后根据该条件运行一些算法.而且与该条件无关，我还想更新一个特定的密钥.假设 190 ，我想在其中添加 20 ，所以现在的密钥将是 210 .现在，数据结构将如下所示:

So basically I first need to determine if the key matching a given number exists in the data structure, and I run some algorithm based on that condition. And independently of that condition I also want to update a particular key. Let's say 190, and I want to add 20 to it, so now the key would be 210. And now the data structure would look like this:

|115|210|380|265|

之所以要这样做，是因为我有一个遍历二进制搜索树的递归算法.每个节点都有一个 int值，以及指向左节点和右节点的两个指针.当到达叶节点时，我需要在哈希表"数据结构中创建一个新字段，其中包含 current_node-> value .然后，当我递归返回树时，需要将每个节点的值依次加到存储在键中的先前总和中.而且我的数据结构(我建议应为 std :: unordered_map )具有多个数字字段的原因是，每个数字字段都代表从树的叶节点到树的唯一路径.中间的某个节点.我检查从叶子到给定节点的路径上节点的所有值的总和是否等于该节点的值.因此，基本上，将每个节点的当前值添加到每个键中，以存储该路径上所有节点的总和.我需要扫描该数据结构，以确定任何字段或键是否等于当前节点的值.我也想在几乎恒定的时间内将新值插入数据结构.这是为了进行竞争性编程，我会犹豫使用 std :: vector ，因为我认为查找元素并插入元素需要线性时间.那会增加我的时间复杂度.也许我应该使用 std :: unordered_map 以外的其他数据结构?

The reason I want to do this is because I have a recursive algorithm which traverses a binary search tree. Each node has an int value, and two pointers to the left and right nodes. When a leaf node is reached, I need to create a new field in the "hash table" data structure holding the current_node->value. Then when I go back up the tree in the recursion, I need to successively add each of the node's value to the previous sum stored in the key. And the reason why my data structure (which I suggest should be a std::unordered_map) has multiple fields of numbers is because each one of them represents a unique path going from a leaf node up the tree to a certain node in the middle. I check if the sum of all the values of the nodes on the path from the leaf going up to a given node is equal to the value of that node. So basically into each key is added the current value of the node, storing the sum of all the nodes on that path. I need to scan that data structure to determine if any one of the fields or keys is equal to the value of the current node. Also I want to insert new values into the data structure in near constant time. This is for competitive programming, and I would hesitate to use a std::vector because looking up an element and inserting an element takes linear time, I think. That would screw up my time complexity. Maybe I should use another data structure other than a std::unordered_map?

推荐答案

您可以使用 unordered_map ::擦除和 unordered_map ::插入到更新密钥.平均时间复杂度为O(1)(BTW，最差的时间为O(n)).如果您使用的是C ++ 17，则还可以使用 unordered_map :: extract 更新密钥.时间复杂度是相同的.

You can use unordered_map::erase and unordered_map::insert to update a key. The average time complexity is O(1)(BTW, the worst is O(n)). If you are using C++17, you can also use unordered_map::extract to update a key. The time complexity is the same.

但是，由于您只需要一组数字，我认为 unordered_set 更适合您的算法.

However, since you only need a set of number, I think unordered_set is more suitable for your algorithm.

这篇关于如何更改unordered_map中的键?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！