Skip to content
  • Stephen Kelly's avatar
    cmAlgorithms: Add cmRemoveDuplicates algorithm. · cebeed24
    Stephen Kelly authored
    Start by creating a vector to hold a unique values of the input range.  We
    expect that in most cases, there will be relatively few duplicates, so
    reserving enough memory for a complete copy is worthwhile.  Unlike a solution
    involving a std::set, this algorithm allocates all the memory it needs
    in one go and in one place, so it is more cache friendly.
    
    Populate the unique copy with a lower_bound insert algorithm and record the
    indices of duplicates.  This is the same complexity as the std::set insert
    algorithm, but without the need to allocate memory on the heap and other
    disadvantages of std::set.
    
    Remove the duplicates with the cmRemoveIndices algorithm.
    cebeed24