Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk