将排序范围插入关联容器的复杂性 [英] Complexity of inserting sorted range into associative container

问题描述

标准指定（23.4.4.2:5等）构造所有四个有序关联容器（ map ， multimap ，设置， multiset code>如果范围已经排序，则在 N = last-first 中是线性的。

The standard specifies (23.4.4.2:5, etc.) that constructing all four ordered associative containers (map, multimap, set, multiset) from a range [first, last) shall be linear in N = last - first if the range is already sorted.

将范围（例如，相同类型的容器）合并到现有容器中，然而，表22仅指定插入范围 [i，j）进入容器应具有复杂度 N log（a.size（）+ N）其中 N = distance（i，j）。这似乎表明使用提示插入：

For merging a range (e.g. a container of the same type) into an existing container, however, 23.2.4:8 table 102 specifies only that inserting a range [i, j) into the container shall have complexity N log(a.size() + N) where N = distance(i, j). This would seem to indicate that using the hinted insert:

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

可能比更有效a.insert（i，j） code>，其复杂性严格小于 N log（a.size（）+ N），取决于正确的提示比例case N == 0 ）;并且是线性的，因为每个提示是正确的，如果 a 最初为空。

could be more efficient than a.insert(i, j), having complexity strictly less than N log(a.size() + N), depending on the proportion of hints that are correct (except in the trivial case where N == 0); and being linear, since every hint is correct, if a is initially empty.

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

Is this a deficiency in the standard, or is there some other language (or facility) that covers this case? In practice, do implementations optimise for merging an ordered associative container into another?

贷记到 http://stackoverflow.com/a/11362162/567292 。

推荐答案

我假设在后一种情况下，标准只是指定关联容器合并的最坏情况保证的运行时性能，如果它们是可能。请记住，与其他语言不同，C ++规范正是这样的规范。没有参考实现。因此，可以编写仅满足某些性能标准的实现，或者可以决定实现将超过指定性能标准的特征。最后，虽然规范是设计为给你一个至少的性能保证，在某些算法的实现方式。

I would assume in the latter case that the standard is only specifying the worst-case guaranteed run-time performance of the associative container merge, leaving it up to the implementation to find faster performance short-cuts if they are possible. Keep in mind that unlike other languages, the C++ specification is exactly that - a spec. There is no "reference" implementation. Thus one could write an implementation that only meets certain performance criteria, or one could decide to implement features that would exceed the specified performance criteria. In the end though the specification is designed to give you an "at minimum" performance guarantee in the way certain algorithms are implemented.

话虽如此，你应该总是使用提示对于每个元素，你最坏的性能实际上是最后的两倍慢，如果你简单地插入没有提示。所以总是使用提示不一定是灵丹妙药。

That being said, should you always use hinting for every element, your worst-case performance actually ends up being twice as slow as if you had simply inserted without hinting. So always using hinting is not necessarily a panacea.

这篇关于将排序范围插入关联容器的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！