-
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