[boost] [Containers] Complexity of flat_*::insert(first,last)

Subject: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-08-03 13:27:27

Hi Ion,

This library looks great.  A quick comment about range-insertion in the 
flat containers, e.g.:

     template<typename InputIterator>
       void insert(InputIterator first, InputIterator last);

     Requires: i, j are not iterators into *this.

     Effects: inserts each element from the range [i,j) .

     Complexity: N log(size()+N) (N is the distance from i to j) search
     time plus N*size() insertion time.

(Note typo: i,j vs, first,last)

What implementation are you assuming to get that complexity?  It seems 
to me that it is worse than it could be if you implement it something 
like this (PSEUDO-CODE):

template<typename InputIterator>
void insert(InputIterator first, InputIterator last)
{
   iterator m = end();
   insert(end(), first, last);
   sort(m,end());
   inplace_merge(begin(),m,end());
}

(I've only ever done this with multi* containers.  For set and map 
you'll need something to avoid duplicates.)

Regards,  Phil.

p.s. Having typed that I have developed a feeling of deja vu.  Have I 
asked you this before?