Quote Originally Posted by laserlight View Post
Not quite: there may be as many insertions as there are objects in the range, but each insertion would normnally take logarithmic time.
Yes, very true. An oversight on my part. I just meant to say that as a general rule, you shouldn't hope for better than o(N). (At least, in a non-destructive fashion, and containers that don't share their internals, AFAIK).

That said, I was looking at the standards.
C++98 has this to say: "Nlog(size()+N) (N is the distance from i to j) in general; linear if [i, j) is sorted according to value_comp()"
but C++11 has this relaxed to simply: "N log(a.size() + N) (N has the value distance(i, j)"

Although cplusplus.com does state: "Implementations may optimize if the range is already sorted."

The more you know I guess. It's interesting to discover this little changes from 98 to 11.