Re: [boost] Speeding up set and map insertion

Subject: Re: [boost] Speeding up set and map insertion
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-12-16 00:40:15

About what library are you posting?  If you put [<libraryname>] in your
subject line you're liable to get attention from the appropriate
developer.  Otherwise, well...

on Tue Dec 13 2011, Tweety <tweety3d-AT-gmail.com> wrote:

> 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.
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com