Normally, constructing a rb-tree is O(N*log(N)) time.
However, initialization of std::set from sorted elements is linear time.
How does that work? Is there a sorted-check before initialization? Or search from the right-most one?
Read more here: https://stackoverflow.com/questions/66280462/complexity-of-stdset-constructor-from-sorted-elements
Content Attribution
This content was originally published by zjyhjqs at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.