我有许多由其二维坐标（有符号短距离）标识的项目。每个项目都是包含 64KB 数据的类。任何时候都有大约 500-1500 个项目。项目通常围绕一个点以约 20 个为一组。我的问题是我应该如何映射它们，以免占用太多内存。项目将被缓慢添加/删除（每秒 1-10 个），并且会被非常频繁地获取，因此从列表中获取元素（指向更大结构的指针）应该尽可能快。
我想出的是会有一些 gridContainer 类，可以说它将存储 64x64 指针的矩形。我将拥有主网格容器，它将存储其他 gridContainer，而这个嵌套的 gridContainer 将存储我想要映射的实际项目（这将允许 4096x4096 个实际项目）。要访问特定项目，例如 [260, 130]，我会将其除以 64 并取商以找到父 gridContainer 位置，余数以找到嵌套 gridContainer 位置。所以对于 [270,145] 我将有 [4,2] 和 [14,17]。
我也在考虑使用std::map，但我不知道它的内部结构，也不知道我应该期待它的性能。
对我的方法有什么建议或有更好的方法吗？
您可以使用已经建议的 std::map ，它只是 ab 树容器，或者您可以使用哈希表，它有可能更快。四叉树也是一个选项，它比前两个选项涉及更多，但会提供早期选项。
具有最小负载的哈希表很有可能是 O(1) 查找，但当 n = 存在时，最坏的情况是 O(n)。如果您可以将负载保持在大约 10% 以下，那么您必须拥有一个非常可怕的散列函数才能变得比 O(1) 更糟。这显然会消耗大量额外的内存，但它有可能成为最快的选择。哈希表的比较类型非常复杂。您有一个哈希函数，它接受键类型的输入，在本例中是一对短裤，并返回一个索引。该索引对应于半固定对象数组上的位置。如果那里已经有对象，则必须解决碰撞，这可能会导致不利的运行时间，因此越稀疏越好。
四叉树的最佳情况返回时间为 O(1)，但仅适用于空单元格，而如果存在项目，则查找时间为 O(log n)，其中 n 是所需字段的大小。除非您的对象很少，否则这可能会比哈希表消耗更多的内存，但如上所述，您可以获得不错的运行时间，并且不产生任何结果的查找可以以相对速度终止。四叉树的比较类型通常只是级联布尔检查。
std::map 的查找时间恒定为 O(log n)，其中 n 是映射中的元素。这是内存效率最高的选项，但对于任何查找都有保证的运行时间。std::map 的比较类型是级联小于运算，在 int ((short1<<16)|short2) 的情况下，它也相当快。
您可能会使用的容器有一个很好的概述。您应该使用哪一个取决于您期望您的桌子的负载程度。只需几个对象（< 500），std::map 可能是您最好的选择。对于 500 到大约 5000，您可能应该使用四叉树。除此之外，您将开始为树使用大量内存，并且可能应该使用哈希表。
您始终可以使用std::map<std::pair<short, short>, *item>这将允许log(n)及时检索和添加，但要获得更准确的答案，我们必须知道您需要哪些操作才能快速
四叉树似乎是您正在寻找的东西。