Subject: Re: [boost] [flat_set] When to sort?
From: Oswin Krause (Oswin.Krause_at_[hidden])
Date: 2017-03-26 14:08:19
>> containers are not well suited for frequent modifications, so that is
>> kind of expected.
> Understood. The described use-case constructs the flat_set only once
> (but a big one and one insert at a time). So, on the surface all
> appeared by the book -- constructed once, traversed/searched often.
> Still, the observed construction overhead really stunned me.
I think the issue is that you use the wrong insert method. a single
insert is O(N)in the size of the container (worst case: insert sorted
from largest to smallest element), so inserting K element into an empty
flat set has runtime O(K^2). You are essentially doing insertion sort on
flat_set has range-insert:
template<typename InputIterator> void insert(InputIterator,
void insert(ordered_unique_range_t, InputIterator, InputIterator);
inserting a range of size K in a flat_set of size N should have
complexity O(K log(K) + K+N) in the first case (implementable as: copy
all new elements to the end, sort the new elements and perform an
inplace-merge). in the second call, only a simple merge is needed,
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk