[flat_set/flat_map] request for new constructor that accepts a sorted sequence

[Thorsten Ottosen-3]

Hi Ion,

It would be veyr nice to have the following constructor:


   template< class Iter >
   flat_container( Iter, Iter, bool /*tag*/ );

which allows one to give the container an already sorted sequence
(this would be the precondition).

-Thorsten
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Ion Gaztañaga]

2009/7/7 Thorsten Ottosen <thorsten.ottosen@...>:

> Hi Ion,
>
> It would be veyr nice to have the following constructor:
>
>
>  template< class Iter >
>  flat_container( Iter, Iter, bool /*tag*/ );
>
> which allows one to give the container an already sorted sequence
> (this would be the precondition).

You want this for performance reasons, right? I've also checked that
currently if ordered ranges are passed in ranges constructors
complexity was suppossed to be linear to std::distance(Iter, Iter)
instead of N log N but that's not true. I'll need to fix that.

I'll add this to the to-do list, but I won't be able to add them until
mid-august at least.

> -Thorsten

Best,

Ion
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Thorsten Ottosen-3]

Ion Gaztañaga skrev:

> 2009/7/7 Thorsten Ottosen <thorsten.ottosen@...>:
>> Hi Ion,
>>
>> It would be veyr nice to have the following constructor:
>>
>>
>>  template< class Iter >
>>  flat_container( Iter, Iter, bool /*tag*/ );
>>
>> which allows one to give the container an already sorted sequence
>> (this would be the precondition).
>
> You want this for performance reasons, right?

Right.

> I've also checked that
> currently if ordered ranges are passed in ranges constructors
> complexity was suppossed to be linear to std::distance(Iter, Iter)
> instead of N log N but that's not true. I'll need to fix that.
>
> I'll add this to the to-do list, but I won't be able to add them until
> mid-august at least.

no problem.

-Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Ion Gaztañaga]

Thorsten Ottosen escribió:

> Hi Ion,
>
> It would be veyr nice to have the following constructor:
>
>
>   template< class Iter >
>   flat_container( Iter, Iter, bool /*tag*/ );
>
> which allows one to give the container an already sorted sequence
> (this would be the precondition).

Hi,

I've been experimenting recently and I've realized that uniqueness is
also needed for set/map so I've been working on the following overloads
for flat_xxx and map/set family:

//Precondition: User must guarantee ordered an unique sequence
set::set(ordered_unique_t, Iter, Iter);

//Precondition: User must guarantee ordered an unique sequence
multiset::multiset(ordered_t, Iter, Iter);

//Usage
std::vector<T> v;
//...
std::sort(v.begin(), v.end());

flat_multimap m(ordered, v.begin(), v.end());

rbtree containers can also benefit from this optimization avoiding any
comparison and thus improving construction time. I haven't looked at
adding ordered range insertion (that would require checking for the
correct position and in the case of set/maps assuring no duplicates,
which we should handle in an efficient way) but that could be also
interesting. Of course, this could break container invariants if
preconditions are not met, but I think these advanced functions can be
interesting for efficiency hungry boosters.

> -Thorsten

Best,

Ion
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Thorsten Ottosen-3]

> I've been experimenting recently and I've realized that uniqueness is
> also needed for set/map so I've been working on the following overloads
> for flat_xxx and map/set family:
>
> //Precondition: User must guarantee ordered an unique sequence
> set::set(ordered_unique_t, Iter, Iter);
>
> //Precondition: User must guarantee ordered an unique sequence
> multiset::multiset(ordered_t, Iter, Iter);
>
> //Usage
> std::vector<T> v;
> //...
> std::sort(v.begin(), v.end());
>
> flat_multimap m(ordered, v.begin(), v.end());
>
> rbtree containers can also benefit from this optimization avoiding any
> comparison and thus improving construction time. I haven't looked at
> adding ordered range insertion (that would require checking for the
> correct position and in the case of set/maps assuring no duplicates,
> which we should handle in an efficient way) but that could be also
> interesting. Of course, this could break container invariants if
> preconditions are not met, but I think these advanced functions can be
> interesting for efficiency hungry boosters.

Seems fine to me. You may choose to check the precondition inside
BOOST_ASSERT since it can also be done in O(n) time.

-Thorsten
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost