Is the complexity of std::set constructor listed on cppreference incorrect?

Question

On this page https://en.cppreference.com/w/cpp/container/set/set, it says:

4-5) log(N) where N = std::distance(first, last) in general, linear in N if the range is already sorted by value_comp().

Isnt that incorrect? I would expect it to be O(NlogN) in the general case because you are inserting elements N times into the tree and each insertion takes logN time.

Answer 1

Here's what the standard says about the complexity [set.cons]p4:

Complexity: Linear in N if the range [first, last) is already sorted with respect to comp and otherwise N log N, where N is last - first.

So it seems like a typo on cppreference, but someone can fix it: https://en.cppreference.com/mwiki/index.php?title=Template:cpp/container/constructor_ord&section=2&action=edit