Boost logo

Boost :

Subject: Re: [boost] [flat_set/flat_map] request for new constructor that accepts a sorted sequence
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2009-08-07 04:50:45


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


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