cppreference上std::set构造函数的复杂度描述是否有误？

你提到的cppreference上关于std::set第4-5版本构造函数的复杂度描述是笔误，正确的复杂度应该是：

4-5) 一般情况为 O(N log N)（其中N = std::distance(first, last)），如果输入范围已经按value_comp()排序，则复杂度为线性O(N)。

你的理解完全正确：当插入N个无序元素时，每个元素插入到平衡二叉搜索树（比如红黑树）中都需要O(log k)的时间（k是插入时树中已有的元素数量），累加下来总复杂度就是O(N log N)。而当输入范围已经有序时，实现可以采用更高效的批量构建方式，直接按顺序构造平衡树，无需每次插入都进行旋转调整，因此能达到线性时间复杂度。

cppreference上的这个描述属于排版错误，把O(N log N)误写成了log(N)，这类笔误在社区中已经被多次指出并修正过。

内容的提问来源于stack exchange，提问作者Sourav Ganguly