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

Subject: Re: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2011-08-06 15:57:03

My instinct is that pre-sorting the incoming range is worthwhile.
I will now try to convince myself otherwise:

template<typename InputIterator>
void insert(InputIterator first, InputIterator last)
{
 // however it is done, I expect something like this would be worthwhile:
 // allocate once, enough space for all:
 make_room(distance(first, last));

 // presorting basically tells us where to start looking when
inserting the next item
 // ie once we insert the first pre-sorted item, we know the next one
will be somewhere after that.
 // Is that equivalent to something like the following, where we do a
similar comparison as we go?

 // imagine insert tells us where it was inserted
 // or some internal version of insert does.
 location = insert(first);
 for (i = ++first; i < last; i++)
 {
     if ( *i < *(i - 1) )
        location = insert_somewhere_before(location, i);
     else
        location = insert_somewhere_after(location, i);
 }
}

Then it just looks like this is equivalent to using the previous to
pick a pivot point.  Which isn't any big win.
Or did I do too much slight of hand there?

Tony