5

我需要一个像地图一样的数据结构，但每个键可能有多个与其相关的值，但我需要将与单个键对应的所有值作为对象数组获取。那么哪种数据结构最好做到这一点。我不需要在数据结构中搜索，我只需要快速访问与特定键对应的所有值。我查看了 std::multimap 但它没有返回特定键的所有值。那么，我可以使用哪个 C++ 中最好的数据结构呢？

4

2 回答 2

6

我需要一个像地图一样的数据结构，但是......

std::map<key, std::vector<value>>

8000 万点是一个不错的选择——值得考虑其他选择。值得思考/实验/基准测试的包括：

  • 稀疏直接索引...要实现这一点，您不仅需要足够的内存来存储 8000 万个数据点，还需要它们跨越的整个 x/y/z 空间，然后可以进行[x][y][z]查找以找到单元格 ID 的向量 -这显然将是巨大的-从您的问题描述中不清楚它是可行的还是可取的

  • 一个排序的向量...取决于您的数据结构元素插入和查找的顺序/重叠，以及您是否负担得起压缩步骤 - 您可以对(x,y,z) 值进行std::map排序，然后由于的连续内存使用情况std::vectorstd::vectorbinary_searchstd::mapvector

  • std::unordered_map<key, std::vector<value>>... 假设 1 亿桶容量应该加快插入速度。这可能比其他选项更慢或更快......索引的内存页面可能比稀疏索引的页面少，但超过binary_search连续内存，每次查找访问的内存页面最少 # 个，但使用正常的哈希技术你'即使 x、y、z 坐标仅略有不同，也会有效地命中随机（但可重复）哈希桶，因此缓存命中可能比上述所有其他选项更差。

实际基准始终是调整的最佳方式，最好使用配置文件来确认成本是否出于预期原因。

于 2013-06-07T06:07:39.127 回答
4

@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的实现中，上面的迭代都是在执行基于节点的指针来追踪“连续”值元素，而不是你为based获得的连续迭代。由于cache-locality的原因，这可能很重要。std::vectorstd::map

我可以从该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));

您可能应该对您的程序进行基准测试，以查看哪个容器更方便。

于 2013-06-07T09:01:37.850 回答