use*_*047 5 c++ map multimap data-structures c++11
我需要一个像地图一样的数据结构,但每个键可能有多个与之相关的值,但我需要将与单个键对应的所有值作为对象数组.那么哪种数据结构最适合这样做.我不需要在数据结构中搜索,我只需要快速访问与特定键对应的所有值.我查看了std :: multimap但它没有返回特定键的所有值.那么我可能使用哪种C++中最好的数据结构呢？
我需要一个像地图一样的数据结构但......
std::map<key, std::vector<value>>
8000万点是一个很好的打击 - 值得考虑其他选择.值得一点思考/实验/基准测试包括:
稀疏直接索引...为了实现这一点,你需要足够的内存不仅仅是8000万个数据点,而是它们跨越的整个x/y/z空间,但是可以进行[x][y][z]查找以找到单元格id的向量 -这显然是巨大的 - 无论是可行的还是可取的,你的问题描述都不清楚
一个有序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坐标只有一点差异,因此有效随机(但可重复)的哈希桶也会有效,因此缓存命中可能比上面的所有其他选项更糟糕.
实际基准测试始终是调整的最佳方式,最好使用配置文件来确认成本是出于预期的原因.