c++ - 将排序范围插入关联容器的复杂性

Question

该标准指定(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)其中 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启发了这个问题。

Answer 1

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

也就是说，如果您始终对每个元素都使用提示，那么最坏情况下的性能实际上会比直接插入而不使用提示时慢两倍。所以总是使用提示并不一定是万能的。