整数哈希问题

Question

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

是否有某种形式的数据结构可以以紧凑（内存方面）的方式处理此类问题，并且速度很快？感兴趣的主要查询是对象是否被标记以及标记的内容。

谢谢。

注意：std::map 无法更改。无论我使用什么数据结构，都不能处理地图本身。

Answer 1

如何将地图的 value_type 设为 std::pair 而不是 MyObject*？

Answer 2

如果您不关心内存，那么 std::vector （或任何适合您需要的东西来代替 int）应该可以工作。

如果您不喜欢这样，并且无法修改地图，那么为什么不为标记创建并行地图呢？

std::map<id,T> my_object_map;
std::map<id,int> my_marker_map;

如果您无法直接修改对象，您是否考虑过在将对象放入地图之前将其包装起来？例如：

struct
{
    int marker;
    T *p_x;
} T_wrapper;


std::map<int,T_wrapper> my_map;

如果您无论如何都需要进行查找，那么这不会慢。

编辑：正如@tenfour在他/她的回答中所建议的，std::pair在这里可能是一个更干净的解决方案，因为它保存了struct< /代码> 定义。就我个人而言，我不是 std::pair 的忠实粉丝，因为您必须将所有内容都称为 first 和 second，而不是而不是有意义的名字。但这只是我...


Answer 3

要问自己的最重要的问题是“这 100,000,000 个对象中有多少可能被标记（或保持未标记）？”如果答案大约小于 100,000,000/(2*sizeof(int))，则只需使用另一个 std::set 或 std::tr1:: unordered_set（hash_set 位于 tr1 之前）来跟踪哪些已标记（或未标记）。

2*sizeof(int) 从哪里来？它是对在将标记的项目列表的双端队列中维护堆结构所需的内存开销的估计。

如果它更大，则使用您即将使用的 std::bitset 。对于您所需的数量规模，其管理费用实际上为 0%。您将需要大约 13 MB 的连续 RAM 来保存位集。

如果您需要存储标记和状态，请使用 std::tr1::unordered_map（使用 Object* 键和 marker_type 值）代码>.同样，如果标记节点的百分比高于上述比较，那么您将需要使用某种 bitset 来保存所需的位数，并适当调整大小，即 12.5每比特兆字节。

考虑到需求的澄清，持有bitset的专门构建的对象可能是您的最佳选择。

---

编辑：这假设您已经对您可接受的解决方案进行了适当的时间复杂度计算，因为不再允许更改基本 std::map 结构。

Answer 4

如果您不介意使用 hack，请查看 内存优化。它可以在存储指针的 LSB 中存储一位。