0

我们使用 multimap<int,string> 存储数十万个项目 (>300K)，当我们意识到我们需要添加更多数据进行分析时。所以我们创建了一个类，其中包含一些项目和必要的 stl 重写运算符，并使用了 multimap<ourStruct,String>。这工作得很好，并且没有比以前花太多时间（使用一些测试数据），当我们意识到一个 stl <list> 就可以了，只要我们在完成添加所有项目后对其进行排序。令我们惊讶的是，我们发现将所有项目添加到 multimap 仍然很容易超过将所有项目添加到列表然后排序的总时间。
这对我们 EE 类型没有意义，因为我们认为每次插入到 multimap 都必须遍历列表然后将其添加到末尾，而与列表一样，我们只需添加到末尾（通过推回） ，那么希望排序不会花那么长时间。
另一个事实：我们最初在没有对列表进行排序的情况下进行了比较测试，并且很高兴看到使用列表的速度显着提高。然后我们添加了排序，有点惊呆了……
那里的任何 CS 大师都愿意权衡吗？

4

2 回答 2

0

删除 ref 到 hash .. 平衡树是为什么只需要 n2 遍历的原因。

于 2011-04-21T23:17:17.290 回答
0

std::multimap使用平衡树1，因此在插入项目时它不会遍历整个列表。为插入而遍历的项目数大约是集合中项目数的以 2 为底的对数。

根据你所说的，你最好的选择可能是将你的数据放在一个向量中，然后排序。

1从技术上讲，该标准并不直接要求平衡树，但它要求能够按排序顺序遍历，以及在最坏情况下插入和删除的对数复杂度，我不知道还有许多其他数据结构可以满足那个要求。

于 2011-04-21T23:17:32.980 回答