代码之家 › 专栏 › 技术社区 › 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
    }
}

推荐文章

patrick · 从boost::绑定1和2占位符运行make失败。。。?

1 年前

rookie · 检查函数模板的所有参数包参数是否属于int

1 年前

ivaigult · -W转换和隐式字符串到布尔类型转换

1 年前

David Bien · declval<_Xp(&)()>()()-这在下面的上下文中意味着什么?

1 年前

khallad sayed · 在%上,C++表达式必须具有整型或无范围枚举类型

1 年前

rainer · 后台插入程序的初始化

1 年前

Community wiki · 以理智、安全和高效的方式复制文件

1 年前

Shefali Kanaujia · 对C中向量的向量进行排序++

1 年前

Prakritish Ghosh · 现在显示正确输出的函数中的Infix到Postfix错误[重复]

1 年前

Ma Joonyoung · 粗粒度和细粒度链表的时间比较

1 年前