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