Subject: Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?
From: Giacomo Drago (giacomo_at_[hidden])
Date: 2015-03-13 09:58:09
On 2015-03-13 13:38, Phil Endecott wrote:
> Hi Giacomo,
> No, "how it works" is the first thing I want to know! It's unlikely that
> you've invented something completely new...
Granted... I don't think I have invented anything new, but if I had
started describing the data structure (and I am not very good at it) I
would have got no answers. Raw milliseconds usually do the trick,
especially with C++ enthusiasts.
I am writing a PDF that explains how this thing works, but basically
it's a heap with a few tweaks.
>> Let's get straight to the benchmarks
> Rather than quantified benchmarks, to start with I'd like to know the
> big-O complexity of the operations.
The Big-O complexity of the operations is same or worse. Lookup is
O((log(n))^2), insertion/erasure is O(n), and full in-order traversal is
O(n (log(n))^2) as unfortunately you can't conveniently move to the next
element in the storage vector.
> (Personally, I have a flat_map that does batched insertions i.e. the new
> items are appended individually and then merged at the end of the batch.
> This will have significant benefits for some workloads.)
Indeed, that's the first thing I would do but I wanted to get better
insertions even when adding one element at a time, and interleaving
insertions with lookups, because that's what I do in my actual usage
Thank you for your time!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk