如何在unordered_map中更改键？

Question

我需要使用一种数据结构，它平均支持常数时间查找。我认为使用 std::unordered_map 是一个不错的选择。我的数据是一组数字的“集合”。

|115|190|380|265|

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

所以基本上我首先需要确定与给定数字匹配的键是否存在于数据结构中，并根据该条件运行一些算法。而独立于该条件，我还想更新特定的键。比如说190，我想加上20，现在键就是210了。 现在数据结构看起来像这样：

|115|210|380|265|

我想这么做的原因是，我有一个递归算法来遍历二叉搜索树。每个节点都有一个int值和两个指向左右节点的指针。当到达叶节点时，我需要在“哈希表”数据结构中创建一个新字段，其中包含current_node->value。然后，在递归中向上遍历树时，我需要依次将每个节点的值添加到之前存储在键中的先前总和中。我的数据结构（我建议应该是std::unordered_map）具有多个数字字段的原因是，每个数字字段代表从叶节点到中间某个节点的唯一路径。我检查从叶子节点到给定节点的路径上所有节点的值的总和是否等于该节点的值。因此，当前节点的当前值被添加到每个键中，存储了该路径上所有节点的总和。我需要扫描该数据结构以确定任何一个字段或键是否等于当前节点的值。此外，我想以近乎常数的时间将新值插入数据结构中。这是为了竞争性编程，我不想使用std::vector，因为查找元素和插入元素需要线性时间，我认为那会破坏我的时间复杂度。也许我应该使用除std::unordered_map之外的其他数据结构？

- Galaxy

Answer 1

你可以使用 unordered_map::erase 和 unordered_map::insert 来更新一个键。平均时间复杂度为 O(1)（顺带一提，最差时间复杂度为 O(n)）。如果你使用的是 C++17，你还可以使用 unordered_map::extract 来更新一个键。时间复杂度相同。

然而，由于你只需要一组数字，我认为 unordered_set 更适合你的算法。

- donnyxia

---

平均时间通常用theta（Θ）表示，而不是大O。 - Evan Zhao

不，大Omicron符号用于描述最坏情况下的上限时间复杂度，而大Theta符号则用于描述最好和最坏情况下时间复杂度的紧密界限；在这里不适用，因为O(1) != O(n)。 - Dúthomhas

最糟糕的时间难道不是在有n个元素需要插入/删除的情况下的O(n)吗？网站上提到当只有一个元素时，复杂度为O(1)。 - undefined

插入一个元素可能会触发rehash()，而rehash()的时间复杂度是O(n)。 - undefined

Answer 2

#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
    }
}

- Swordfish

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);
   }
}

- 신덕진

Answer 4

自C++17起，您还可以使用其extract函数，如下所示：

std::unordered_map<int, int> map = make_map();

auto node = map.extract(some_key);
node.key() = new_key;

map.insert(std::move(node));

- Dean Seo