我需要一个类似于map的数据结构,但每个键可能有多个相关值,但我需要将所有与单个键对应的值作为对象数组获取。那么哪种数据结构最适合做到这一点呢?我不需要在数据结构中搜索,我只需要快速访问与特定键对应的所有值。我已经查阅了std :: multimap,但它不会返回特定键的所有值。那么在C ++中我可以使用哪种最佳的数据结构?
std::map<key, std::vector<value>>
8000万个数据点是相当大的数量-值得考虑其他选项。一些值得思考/实验/基准测试的选项包括:
稀疏直接索引...为了实现这一点,你需要足够的内存来容纳不仅是80 million个数据点,还有它们所跨越的整个x/y/z空间,但然后可以进行[x][y][z]查找以找到单元格id的向量-这显然会非常巨大-从你的问题描述中不清楚是否可行或者是否值得。
排序向量...取决于数据结构元素插入和查找的顺序/重叠情况,以及是否可以承受std::map到std::vector压缩步骤-你可以对(x,y,z)值的std::vector进行排序,然后由于vector的连续内存使用,使binary_search优于std::map。
std::unordered_map<key, std::vector<value>>...预设100 million个桶容量应该会稍微加快插入速度。这可能比其他选项更慢或更快...与稀疏索引相比,索引的页面可能较少,但比在连续内存上进行二进制搜索要多,每次查找访问最少的内存页数,但使用普通的哈希技术,即使x、y、z坐标只有一点不同,你也会命中有效随机(但可重复)的哈希桶,因此缓存命中可能比上面所有其他选项都要差。
实际基准测试始终是调整的最佳方法,最好使用配置文件来确认成本是否符合预期。
find
或operator[]
定位具有给定键的向量,并将其push_back
。 - David Rodríguez - dribeasstd::multimap<key, value>
搜索给定键的所有值应该具有相同的 O(log N)
复杂度
auto result = my_multimap.equal_range(my_key);
迭代仍然具有 O(N)
的复杂度:
for (auto it = result.first; it != result.second; ++it)
// bla
my_multimap.insert(std::make_pair(some_key, another_value);
对比
auto it = my_map.find(some_key);
if (it != my_map.end())
it->second.push_back(another_value);
else
my_map.insert(std::make_pair(some_key, another_value));
std::map<key_type, std::vector<value_type>>
。 - Yuushi