Re: [boost] [flat_set] When to sort?

Subject: Re: [boost] [flat_set] When to sort?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-03-28 21:05:38

On 28/03/2017 22:04, Chris Glover via Boost wrote:
>>
>>
>> std::vector<int> buf=s.get_data(); // move, s becomes empty
>> for(...)buf.push_back(...); // populate
>> s.accept_data(buf); // move and sort
>>
>>
> I like this idea -- but I don't think accept_data can do the sort because
> sort might not be enough; the contents might need to be made unique too. We
> could add the call to unique inside accept_data, but that pessimises the
> case where I know my data is unique. So I think it would need to be more
> like;
>
> std::vector<int> buf=move(s).get_data();
> for(...) buf.push_back(...); // populate
> sort(buf);
> unique(buf); // If my contents might not be unique.
> s.adopt_ordered_unique_data(move(buf)); // Asserts data is in fact ordered
> and unique?

We can have different "adopt" variants depending on the guarantees the 
user provides, just like we have different "insert" versions 
(ordered_unique_t, etc.). The "safe" one can assume passed vector is 
unordered and just sorts and calls unique if needed. Other variants 
might just skip sorting if the user requires so.

We have asymptotically optimal in place sorting algorithms in boost.move 
now that can even avoid any temporary huge allocation (stable_sort needs 
O(N) auxiliary memory) and they can take advantage of the unused 
capacity()- size() memory of the vector.

In any case, this does not help people that inserts one by one but wants 
to do lookups between insertions. In that case, a new hybrid container 
(like those suggested in this thread, mixing an unordered vector and an 
ordered one, maybe using the same buffer) is needed. But that container 
is not flat_map, which has strict invariants and requires ordered traversal.

For people that does not care avoid traversal order, then a new 
container, flat_unordered_map, is needed. Something like an open 
addressing hash table, I guess.

Best,

Ion