代码之家 › 专栏 › 技术社区 › Galaxy

如何在无序的地图中更改密钥?

unordered-map algorithm c++

Galaxy · 技术社区 · 6 年前

我需要使用一个数据结构,它平均支持常数时间查找。我认为使用 std::unordered_map

|115|190|380|265|

这些数字不必按特定顺序排列。我需要大约 O(1) 确定此数据结构中是否存在给定数字的时间。我有一个想法,使用 std::无序地图

所以基本上我首先需要确定数据结构中是否存在与给定数字匹配的密钥,然后根据这个条件运行一些算法。独立于这个条件,我还想更新一个特定的密钥。比如说 190 ,我想补充 20 所以现在关键是 210 . 现在数据结构如下所示:

|115|210|380|265|

int value ,以及指向左侧和右侧节点的两个指针。当到达一个叶节点时,我需要在“哈希表”数据结构中创建一个新字段来保存 current_node->value . 然后,当我返回递归中的树时,我需要将每个节点的值依次添加到存储在键中的前一个和中。以及为什么我的数据结构(我建议应该是 std::无序地图 有多个数字字段,因为它们中的每一个都代表从树上的叶子节点到中间的某个节点的唯一路径。我检查从叶子到给定节点的路径上所有节点的值之和是否等于该节点的值。所以基本上每个键加上节点的当前值,存储路径上所有节点的总和。我需要扫描该数据结构,以确定其中任何一个字段或键是否等于当前节点的值。我还想在几乎恒定的时间内将新值插入到数据结构中。这是竞争性编程,我会犹豫使用 std::vector 因为查找一个元素并插入一个元素需要线性时间,我认为。那会毁了我的时间复杂性。也许我应该使用另一种数据结构而不是 ?

2 回复 | 直到 6 年前

donnyxia 6 年前

你可以用 unordered_map::erase 和 unordered_map::insert unordered_map::extract

不过,既然你只需要一组数字,我想 unordered_set

Swordfish 6 年前

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

推荐文章

Julia · 矢量中相加为总和S的值的数量

1 年前

forumulator · 无序映射中的C++远程键

6 年前

ROBOT AI · 插入同一个键时,自定义类的无序_映射不会导致错误

7 年前

ontherocks · 以不同的方式填充地图

7 年前

Bgy · boost中以结构为键的boost变体::无序_映射

7 年前

danish sodhi · 在cpp中使用具有无序_映射的自定义类

7 年前

kreuzerkrieg · std::unordered_map不释放内存

8 年前

trong · C++如何在不调用构造函数的情况下分配对象

8 年前

rahman · 如何测量std::unordered_map的内存使用情况

10 年前

pdrak · stl unordered_set如何设置初始bucket计数

11 年前