c++ - 整数散列问题

Question

我有一个 (C++) std::map<int, MyObject*>包含数百万个 MyObject* 类型的对象.我可以拥有的最大对象数约为 1 亿。关键是对象的 ID。在某个过程中，必须尽快以某种方式标记这些对象(使用 0 或 1 )。标记不能发生在对象本身上(因此我不能引入成员变量并将其用于标记过程)。因为我知道最小和最大 ID(1 到 100_000_000)，所以我首先想到的是使用 std::bit_set<100000000>。并在那里进行我的标记。这解决了我的问题，并且在标记进程并行运行时也更容易，因为它们使用自己的 bit_set 来标记事物，但我想知道解决方案是什么，如果我必须使用其他东西而不是 0 - 1标记，例如，如果我必须用整数标记所有对象，我可以使用什么？

是否有某种形式的数据结构可以以紧凑(内存方式)的方式处理此类问题，而且速度很快？感兴趣的主要查询是一个对象是否被标记，以及用什么标记。

谢谢。

注:std::map<int, MyObject*>不能改变。无论我使用什么数据结构，都不能处理 map 本身。

Answer 1

制作 value_type 怎么样？你的 map std::pair<bool, MyObject*>而不是 MyObject* ？