[Boost-bugs] [Boost C++ Libraries] #13140: Quadratic complexity of a flat_set constructor

Subject: [Boost-bugs] [Boost C++ Libraries] #13140: Quadratic complexity of a flat_set constructor
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-07-28 00:53:15

#13140: Quadratic complexity of a flat_set constructor
--------------------------------+---------------------
 Reporter:  victor.zverovich@…  |      Owner:  (none)
     Type:  Bugs                |     Status:  new
Milestone:  To Be Determined    |  Component:  None
  Version:  Boost 1.63.0        |   Severity:  Problem
 Keywords:                      |
--------------------------------+---------------------
 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`.

-- 
Ticket URL: <https://svn.boost.org/trac10/boost/ticket/13140>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.