我应该使用哪种数据结构来实现我的目的？

Question

我需要一个类似于map的数据结构，但每个键可能有多个相关值，但我需要将所有与单个键对应的值作为对象数组获取。那么哪种数据结构最适合做到这一点呢？我不需要在数据结构中搜索，我只需要快速访问与特定键对应的所有值。我已经查阅了std :: multimap，但它不会返回特定键的所有值。那么在C ++中我可以使用哪种最佳的数据结构？

- ab_11

---

std::map<key_type, std::vector<value_type>>。 - Yuushi

只是一点小提示，multimap可以按键返回值，而不是数组，但是可以。http://www.cplusplus.com/reference/map/multimap/equal_range/ - ForEveR

@ForEveR，是的，我知道，但我想知道是否有一些东西可以将所有值作为数组返回。 - ab_11

还有一个问题：您是否需要关于给定地图相关值的特定内容？例如，您可能需要唯一性、某些排序等。 - Matthieu M.

你为什么需要将值作为数组？ - David Rodríguez - dribeas

最好我向你解释整个事情。 我有一个3D网格，现在它有许多由一组点形成的不同形状的单元格。 现在我需要知道具有特定点的所有单元格的索引。 因此，我的映射中的“键”将是该点的索引，而我的“值”应该是共享该点的所有单元格的索引。 现在，我不想反复迭代std :: map，因为我有大约8000万这样的点，需要填充地图。 希望你明白我想表达什么。 - ab_11

Answer 1

我需要一个类似于map的数据结构，但是...

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坐标只有一点不同，你也会命中有效随机（但可重复）的哈希桶，因此缓存命中可能比上面所有其他选项都要差。

实际基准测试始终是调整的最佳方法，最好使用配置文件来确认成本是否符合预期。

- Tony Delroy

---

谢谢，但是如何在map中插入键值对呢？ 我需要多次为同一个键插入值，而且我不打算先填充向量。 - ab_11

使用find或operator[]定位具有给定键的向量，并将其push_back。 - David Rodríguez - dribeas

@mymap[key].push_back(value)（假设您不需要检查值的唯一性或顺序）。 - Matthieu M.

@Tony D，你还没有听到全部的问题，我还需要找出80百万个数据点中距离50百万个数据点半径为r的所有最近邻居，并且我不知道如何使用Kd树或八叉树来解决这个问题。我需要好的教程。这是我必须做的主要事情，之前我解释的问题（这个问题所指的）是次要的。 - ab_11

@user2401047：变得有点棘手了 - 最优或接近最优的取决于数据集的稀疏程度、你需要处理的半径值的分布情况、是否有充足的RAM等因素。我从未听说过kd树或八叉树，所以无法推荐任何教程。祝好运！ - Tony Delroy

好的，无论如何感谢您，我会发布另一个问题来解决这个。 - ab_11

Answer 2

@TonyD的答案当然很好，但与之相比有一些权衡。

std::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

然而，在所有实际的std :: multimap实现中，上述迭代是基于节点的指针跟踪，而不是基于连续值元素的连续迭代，这可能涉及到缓存局部性方面的原因。

我能看到的std :: vector解决方案的主要缺点是你正在保持所有值在一起，这可能会产生一些开销，取决于你多频繁地复制数据。

multimap方法使得容器中的单个值也更容易插入/提取。

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));

你可能需要对你的程序进行基准测试，以确定哪种容器更方便。

- TemplateRex