如何更改 unordered_map 中的密钥？

Question

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

|115|190|380|265|

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

所以基本上我首先需要确定匹配给定数字的键是否存在于数据结构中，然后我运行基于该条件的一些算法。独立于那种情况，我还想更新一个特定的密钥。比方说 190，我想给它添加 20，所以现在密钥是 210。现在数据结构看起来像这样：

|115|210|380|265|

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

以外的其他数据结构

Answer 1

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<int, int> m;
    m[42];  // add
    m[69];  // some
    m[90];  // keys

    int value = 90;  // value to check for
    auto it = m.find(90);

    if (it != m.end()) {
        m.erase(it);      // remove it
        m[value + 20];    // add an altered value
    }
}

Answer 2

您可以使用 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 更新密钥。时间复杂度相同

不过，既然你只需要一组数，我觉得unordered_set更适合你的算法。

Answer 3

#include <unordered_map>
#include <string>

int main() {
   // replace same key but other instance
   std::unordered_map<std::string, int> eden;

   std::string k1("existed key");
   std::string k2("existed key");

   const auto &[it, first] = eden.try_emplace(k1, 1);
   if (!first) {
      eden.erase(it);
      eden.emplace_hint(it, k2, 123);
   }
}

如何更改 unordered_map 中的密钥？

How to change the key in an unordered_map?

c++

algorithm

unordered-map