Boost logo

Boost :

Subject: Re: [boost] [flat_set] When to sort?
From: Oswin Krause (Oswin.Krause_at_[hidden])
Date: 2017-03-26 19:03:30


> There is another variation of this approach, one I'm sure we've
> discussed before: the flat_set keeps the unsorted range at the end and
> on lookup tries both, first the unsorted part, then the sorted one.
> The unsorted part is merged into place when it exceeds some size. This
> doesn't do non-const operations on logically const lookups, but
> iteration becomes problematic if iterators have to give you a sorted
> view. (Although you could keep the suffix part sorted as well and
> merge on demand in iter::op++ if so inclined.)

This would have consequences both in asymptotic run time (lookups are
O(log(N)+K) where K is the maximum allowed size of the unsorted region)
as well as constants (more complex code, more ifs etc). If K is
independent of N, we would still have overall quadratic time of
inserting a lot of elements using insert(single_element). So this does
not help.

What I meant with my previous comment: it is probably the easiest way
just to buffer all elements to be inserted in an intermediate storage
area and then insert them at once. Of course we might not want to use
the current insert for this as this would require storing all new
elements. Here is my approach to this:

flat_set maintains an array and three iterators(set_begin, set_end and
vector_end). the range [set_begin,set_end) contains all inserted
elements and size() begin(), end() will only return this range. the
range [set_end, vector_end) contains all newly inserted elements,
however they´are still "staging" and will not show up unless the
flat_set is told to.

so we would add two new methods

staging_insert(single_element)//pushes element to the back of the
staging area
sort_staging()//calls sort() on the old range. afterwards

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