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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at