Quadratic complexity of a flat_set constructor

[victor.zverovich@…]

The documentation of 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.

[anonymous]

I mixed flat_map and flat_set above but the same issue applies to both.

[Constantin Makshin <cmakshin@…>]

The suggested fix will create invalid map/set if the source range contains values which must be "collapsed" into one element of the target container (pairs with the same first element for map, same values for set).

[victor.zverovich@…]

This can be fixed by additional unique pass without changing the complexity (also the sort might have to be stable in this case).