[boost] Speeding up set and map insertion

Subject: [boost] Speeding up set and map insertion
From: Tweety (tweety3d_at_[hidden])
Date: 2011-12-13 10:15:19

Hi,
I think it would speed up inserting range of elements into set and map, when in
tree.hpp we replace:

template <class InputIterator>
   void insert_equal(InputIterator first, InputIterator last)
   {
      //Insert with end hint, to achieve linear
      //complexity if [first, last) is ordered
      const_iterator end(this->cend());
      for( ; first != last; ++first)
         this->insert_equal(end, *first);
   }

with:

template <class InputIterator>
   void insert_equal(InputIterator first, InputIterator last)
   {
      //Insert with hint, to achieve linear
      //complexity if data is even partially ordered
      const_iterator it(this->cend());
      for( ; first != last; ++first)
         it = this->insert_equal(it, *first);
   }

I will make almost linear complexity when data is ordered ascending, descending,
and even partially ordered.
Because when inserting with end hint (btw. wasn't here a bug? because "end"
wasn't updated) it's only linear if we insert elements in ascending order.