Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk