3

该标准规定（23.4.4.2:5 等）如果范围已经排序，则从范围构造所有四个有序关联容器（ map、multimap、set、multiset）[first, last)应是线性的。N = last - first

然而，为了将范围（例如，相同类型的容器）合并到现有容器中，23.2.4:8 表 102 仅指定insert将范围[i, j)合并到容器中应具有复杂性N log(a.size() + N)where N = distance(i, j)。这似乎表明使用提示插入：

for (auto it = a.begin(); i != j; ++i)
    it = next(a.insert(it, *i));

可能比 更有效a.insert(i, j)，复杂性严格小于N log(a.size() + N)，具体取决于正确提示的比例（除了在 微不足道的情况下N == 0）；并且是线性的，因为每个提示都是正确的，如果a最初是空的。

这是标准的缺陷，还是有其他语言（或设施）涵盖这种情况？在实践中，实现是否优化了将有序关联容器合并到另一个容器中？

感谢https://stackoverflow.com/a/11362162/567292启发了这个问题。

4

1 回答 1

1

我会假设在后一种情况下，该标准仅指定关联容器合并的最坏情况保证运行时性能，如果可能的话，让实现来寻找更快的性能捷径。请记住，与其他语言不同，C++ 规范正是如此——一个规范。没有“参考”实现。因此，一个人可以编写一个只满足某些性能标准的实现，或者一个人可以决定实现超过指定性能标准的特性。最后，尽管该规范旨在以某些算法的实现方式为您提供“至少”性能保证。

话虽如此，如果您总是对每个元素都使用提示，那么您在最坏情况下的性能实际上最终会比您在没有提示的情况下简单地插入慢两倍。所以总是使用提示不一定是灵丹妙药。

于 2012-07-06T14:46:15.307 回答