Complexity of inserting sorted range into associative container

[bbi5291 <bbi5291 at gmail dot com>]

Some sources, notably SGI's "Complexity guarantees" section for
"Unique Sorted Associative Container" and c plus plus dot com's page
on set::insert(), seem to suggest that
inserting a range into an associative container takes linear time in
the number of elements inserted, if they are already sorted according
to the container's comparison predicate. The comment in stl_set.h says
that range insert's complexity is "similar to that of the range
constructor."

I have been discussing this with some colleagues, and while it's not
hard to see how to construct a balanced tree out of a sorted range,
none of us can see how to insert a sorted range into a tree with
worst-case complexity better than O(N log(N + S)) (where N is the
number of elements to be inserted and S is the size of the set before
insertion). This seems to be the complexity specified by the standard,
without any special case for when the range is sorted.

Because we could not figure out this puzzle ourselves, I dug into
stl_tree.h and found the following:
-----begin code block-----
  template<typename _Key, typename _Val, typename _KoV,
           typename _Cmp, typename _Alloc>
    template<class _II>
      void
      _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
      _M_insert_unique(_II __first, _II __last)
      {
        for (; __first != __last; ++__first)
          _M_insert_unique_(end(), *__first);
      }
-----end code block-----
It looks to me as though the range insert code is simply inserting the
elements from the range one-by-one, always using end() as the
insertion hint. I can see how this would give a linear complexity if
merging two trees (which, in the literature, is always defined as
combining two trees such that the smallest element in the second is
greater than the greatest element in the first) or inserting a sorted
range into an empty tree (which seems to be how stl_set.h is
implementing the range constructor) but I can't see how this can give
linear complexity when inserting a general sorted range into a general
balanced tree. I was hoping that one of the library implementers could
shed some light on this.

This issue seems to have been touched upon in an earlier thread with
subject "[RFC] libstdc++/19422: complexity of ass. containers range
constr." but not actually addressed. Using the example posed in that
thread, of inserting the squares into a set missing them, we can see
that the end() iterator will be a useless hint almost every time.

(I apologize for the absence of links in this message, but it got
rejected as spam the first time I tried to send it.)

Thanks,
________________________________
Brian Bi