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?

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: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2015-03-19 11:56:13

Mathias Gaunard <mathias.gaunard_at_[hidden]> wrote:
> On 13/03/15 17:41, Phil Endecott wrote:
>> flat_set S;
>> {
>>    flat_set::batch b(S);
>>    b.insert(xxx);
>>    b.insert(yyy);
>> }  // b's dtor does the merge
>>
>
> How is that any different from the following?
>
> flat_set S;
> flat_set b;
> b.insert(xxx);
> b.insert(yyy);
> S.insert_sorted(b.begin(), b.end());

Your code uses more memory (temporarily) and does more copying.

To be clear, my "batch" is a small object that stores only a
reference to the flat_set and some iterators/indexes/pointers.
Here's a sketch of one way of doing it:

class batch
{
   flat_set& f;
   size_t orig_size;
public:
   batch(flat_set& f_): f(f_), orig_size(f.size()) {}
   void insert(const T& val) { f.push_back(val); }
   void rollback() { f.truncate(orig_size); }
   void commit() {
     sort(f.begin()+orig_size, f.end());
     inplace_merge(f.begin(),f.begin()+orig_size,f.end());
     orig_size = f.size();
   }
   ~batch() { commit(); }
};

Regards,  Phil.