时间戳

首页 > 解决方案 > 是否有像地图这样的 C++ 结构，但不是值的键，而是值的句柄？

c++ - 是否有像地图这样的 C++ 结构，但不是值的键，而是值的句柄？

问题描述

我需要一个有点像 Map 的结构，但我不关心键值，只关心键对应的值。

在地图上，我需要做这样的事情：

map[1] = "value1"
map[2] = "value2"

它让我有责任不选择组合键。我可以通过这样做来解决这个问题：

let handle = randomValue();
map[handle] = "value1"

因为我不关心密钥的值，所以我只需要处理它。如果两个随机值相等，则仍然存在合并值的问题。我可以写一个小东西来检查地图中是否已经存在密钥并生成一个新的，但是一旦结构有点满，我就会遇到很多冲突。

List 一开始似乎是一个不错的选择，但事实并非如此，因为如果我删除一个元素，所有其他元素的索引都会重新排列。

我不想实现我自己的，而是想知道 C++ 中是否已经存在类似的东西：一个映射，您可以在其中获得一个句柄，使您可以访问该值。

我只是有另一个要求：有时我实际上需要将这个句柄传递给 Rust，所以我认为如果这个句柄可以转换为一个数字并返回它会非常有用。

标签： c++std

解决方案

IIUC，您需要一个具有以下功能的容器：

  • 添加新元素并获得数字句柄的能力
  • 删除现有元素的能力

您在这里不需要映射容器，因为您没有给定的密钥。但是您希望从句柄直接访问。所以你需要的是一个向量。我从不删除元素，将项目 push_back 到向量的末尾并获取它们的索引作为句柄。如果您希望能够快速删除元素，我会为空槽使用特殊值并将空索引存储在辅助容器中，通常是堆栈或队列。在这里我再次使用向量，因为它是一个非常简单的容器并将其用作堆栈，但如果您想将其用作队列，则可以使用 dequeue 或 forward_list。

因此，要删除一个元素，您将其标记为空并将其索引存储在空列表中，并添加一个元素，您首先尝试从空列表中获取下一个插槽，并将其 push_back 到主向量的末尾，如果列表是空的。

添加和删​​除都在恒定的时间内。

推荐阅读