Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-10 08:50:48

Den 04-10-2017 kl. 01:30 skrev Ion Gaztañaga via Boost:

> and I don’t know 
> if the use cases where devector is supposed to shine needs a whole new 
> library 
It's hard to guess about all the use-cases. We never had this as a type 
in our toolbox, so we never gave it any thought. Maybe systems working 
with RTL and LTR text would be natural.

Given that boost::flat_set/flat_map now has support for a custom 
container, I can easily see myself plugging in devector in there. Also 
with a small buffer optimization. And having deque backed by devector 
allows for example to use the small buffer for, say, one or two of the 
first segment pointers.

So what is the benefit of plugging devector into flat_set/flat_map?
Assume a balanced initial capacity (same front free capacity and back 
free capacity). Then compared with vector when we insert N elements

- if all go to the back end, both containers are optimal O(N \lg N)
- the worst case for vector is when all go to the front O(N^2), this is 
O(N \lg N) for devector
- unfortunately the average case is O(N^2) for both containers (so we 
only use it with relatively small sets)

/However, the average case for devector uses about half as many moves as 
vector./ Based on that, I would pick devector as the container in 
flat_set/flat_map in my code.

kind regards

Thorsten