Re: [boost] [container] moving a pre-built vector into a flat_set

Subject: Re: [boost] [container] moving a pre-built vector into a flat_set
From: Francois Duranleau (xiao.bai.xiong_at_[hidden])
Date: 2015-09-16 13:40:00

On Wed, Sep 16, 2015 at 11:10 AM, Sam Kellett <samkellett_at_[hidden]> wrote:
>>
>> > Well, almost.
>> >
>> > IMO, we need three things to make it perfect:
>> >
>> > A. flat_set/map should have an additional template argument specifying
>> the
>> > internal vector type (it can default to the current choice).
>> >
>> > B. You should be able to move the whole container, as suggested.
>> >
>> > C. The constructor should contain an assertion with a call to is_sorted()
>>
>> So essentially, flat_set/map would now be an adapter like a stack or queue.
>> Makes sense. About C, I rather think that we should have two constructors:
>>
>> flat_set/map(storage raw)
>> flat_set/map(ordered_unique_range_t, storage sorted)
>>
>
> +1
>
>
>> and then the is_sorted() assert check should be done in the second
>> constructor, and the first one would call sort().
>>
>
> i'd be scared that this check will nullify a lot of the benefit of this new
> constructor. as the is_sorted assertion i assume would have to go through
> the data to verify this which brings this constructor down to the same O(n)
> complexity as it's iterator pair counterpart.
>
> does the flat_set(ordered_unique_t, first, last) constructor do the
> is_sorted check? or is it undefined behaviour if the input data is out of
> order? i guess it does seeing as how it has to loop through the data anyway
> it might as well..
>
> i would err on the side of this new constructor simply being undefined
> behaviour if non-sorted data is given to it

The is_sorted check would be in an assert, so it would go away in release
builds (this is just validation of precondition, much like we would assert in
std::vector<T>::operator[] for out-of-range indices). Granted, this check is
costly, and ideally we would like to have control on how expensive we allow
validation of preconditions to be. Personally, I wouldn't mind if the check is
not done at all. I was merely suggesting in which case we might add this
check.

-- 
François