• Mark Logan's avatar
    Fix worst-case quadratic behavior of iterator constructors and range insert() · 3ffcb010
    Mark Logan authored
    Summary:
    The iterator constructors and the range insert() method previously
    had quadratic runtime if given an unsorted range. This is now fixed. We
    append the entire range to the container, sort that subrange, and merge it
    into the already-sorted container. Sorting and merging is skipped when possible.
    
    Reviewed By: yfeldblum
    
    Differential Revision: D4493534
    
    fbshipit-source-id: e6d73b5c19e374001f9e340ff527c5257bef2ca3
    3ffcb010
sorted_vector_test.cpp 13.9 KB