https://svn.boost.org/trac10/ticket/13140 <p> The documentation of <a href="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</a> says: </p> <pre class="wiki">template&lt;typename InputIterator&gt; flat_map(InputIterator first, InputIterator last, const Compare &amp; comp = Compare(), const allocator_type &amp; a = allocator_type()); </pre><p> Effects: Constructs an empty flat_map using the specified comparison object and allocator, and inserts elements from the range [first ,last ). </p> <p> Complexity: Linear in N if the range [first ,last ) is already sorted using comp and otherwise N logN, where N is last - first. </p> <p> 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. </p> <p> A simple fix is to insert all elements at once and sort the vector backing <code>flat_set</code>. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/13140 Trac 1.4.3 anonymous Fri, 28 Jul 2017 00:59:39 GMT https://svn.boost.org/trac10/ticket/13140#comment:2 https://svn.boost.org/trac10/ticket/13140#comment:2 <ul> <li><strong>owner</strong> set to <span class="trac-author">Ion Gaztañaga</span> </li> <li><strong>component</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">container</span> </li> </ul> Ticket Constantin Makshin <cmakshin@…> Tue, 01 Aug 2017 20:45:43 GMT