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

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

unordered-map algorithm c++

Galaxy · 技术社区 · 7 年前

我需要使用一个数据结构,它平均支持常数时间查找。我认为使用 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 回复 | 直到 7 年前

donnyxia 7 年前

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

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

Swordfish 7 年前

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

推荐文章

AstralHex · 矩阵乘法代码工作不正常

7 月前

Baba Dan Constantin · SSE4.1在矩阵4x4乘法上比SSE3慢?

7 月前

Giogre · 为包含许多数值字段的简单“struct”重载比较运算符

8 月前

einpoklum · 定义一个并不真正提供now()函数的std::chrono Clock是“合法的”吗?

8 月前

Fishie · 作为类成员的智能指针是否仍然自动释放?[关闭]

8 月前

Die4Toast · 递归调用成员箭头运算符->

8 月前

Angle.Bracket · 如何用C++将UTF-8文件名写入MS Windows控制台?

8 月前

Anka HanÄ±m · 关于结构和动态数组地址的问题

8 月前

Adam Barnes · 我如何定义一个基于constexpr函数返回值进行限制的概念?

8 月前

user2138149 · 为什么我不能获取包含多个元素的结构体中某些元素的地址?[副本]

8 月前