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: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-10-10 21:26:35

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