<分区>
我需要一个像 map 一样的数据结构，但每个键可能有多个与之相关的值，但我需要获取与单个键对应的所有值作为对象数组。那么哪种数据结构最适合执行此操作。我不需要在数据结构中搜索，我只需要快速访问与特定键对应的所有值。我查看了 std::multimap 但它没有返回特定键的所有值。那么我可能会使用哪种 C++ 中最好的数据结构？
<分区>
我需要一个像 map 一样的数据结构，但每个键可能有多个与之相关的值，但我需要获取与单个键对应的所有值作为对象数组。那么哪种数据结构最适合执行此操作。我不需要在数据结构中搜索，我只需要快速访问与特定键对应的所有值。我查看了 std::multimap 但它没有返回特定键的所有值。那么我可能会使用哪种 C++ 中最好的数据结构？
最佳答案
I need a data structure just like a map but...
std::map<key, std::vector<value>>
8000 万点是一个不错的选择 - 值得考虑其他选择。值得思考/实验/基准测试的包括:
稀疏直接索引...要实现这一点，您不仅需要足够的内存来容纳 8000 万个数据点，还需要它们跨越的整个 x/y/z 空间，然后可以执行 [x][y][z]查找单元格 ID 的 vector - 这显然会很大 - 从你的问题描述中不清楚它是否可行或可取
排序 vector ...取决于您的数据结构元素插入和查找的顺序/重叠，以及您是否负担得起 std::map至 std::vector压缩步骤 - 你可以对 std::vector 进行排序(x,y,z) 值然后有 binary_search优于std::map由于 vector 的连续内存使用
std::unordered_map<key, std::vector<value>> ... 假设 1 亿个存储桶的容量应该会稍微加快插入速度。这可能比其他选项更慢或更快……索引的内存页面可能比稀疏索引少，但多于 binary_search在连续内存上，每次查找访问的最少 # 个内存页，但使用普通的哈希技术，即使 x、y、z 坐标仅略有不同，缓存命中率可能更差，您也会有效地随机(但可重复)命中哈希桶比上面的所有其他选项。
实际基准始终是最好的调整方式，最好使用配置文件来确认成本是否出于预期原因。
关于c++ - 我应该为我的目的使用哪种数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16977319/