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?

19 Mar 2015

      Mathias Gaunard  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.