Boost logo

Boost :

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.



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