On 10/10/2017 10:50, Thorsten Ottosen via Boost wrote:
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.
Interesting points. Anyone willing to do some benchmark? ;-) Ion