id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
13140,Quadratic complexity of a flat_set constructor,victor.zverovich@…,Ion Gaztañaga,"The documentation of [http://www.boost.org/doc/libs/1_64_0/doc/html/boost/container/flat_map.html#boost.container.flat_mapconstruct-copy-destruct boost flat_set constructor taking two iterators] says:


{{{
template<typename InputIterator> 
  flat_map(InputIterator first, InputIterator last, 
           const Compare & comp = Compare(), 
           const allocator_type & a = allocator_type());
}}}
Effects: Constructs an empty flat_map using the specified comparison object and allocator, and inserts elements from the range [first ,last ).

Complexity: Linear in N if the range [first ,last ) is already sorted using comp and otherwise N logN, where N is last - first.

However, the complexity of this constructor is O(N*N) because the implementation of the constructor inserts each element into a vector at position found by binary search and insertion is linear in distance to the end of the vector.

A simple fix is to insert all elements at once and sort the vector backing `flat_set`.
",Bugs,new,To Be Determined,container,Boost 1.63.0,Problem,,,