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

Subject: Re: [boost] [flat_set/flat_map] request for new constructor that accepts a sorted sequence
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2009-08-20 08:28:23

> 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