From cebeed248606ba92597b7e32a5b0be1f474f7a91 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Sun, 15 Feb 2015 19:08:12 +0100 Subject: cmAlgorithms: Add cmRemoveDuplicates algorithm. 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. --- Source/cmAlgorithms.h | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 0f162a2..a996088 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -250,4 +250,33 @@ typename Range::const_iterator cmRemoveMatching(Range &r, MatchRange const& m) ContainerAlgorithms::BinarySearcher(m)); } +template +typename Range::const_iterator cmRemoveDuplicates(Range& r) +{ + std::vector unique; + unique.reserve(r.size()); + std::vector indices; + size_t count = 0; + for(typename Range::const_iterator it = r.begin(); + it != r.end(); ++it, ++count) + { + typename Range::iterator low = + std::lower_bound(unique.begin(), unique.end(), *it); + if (low == unique.end() || *low != *it) + { + unique.insert(low, *it); + } + else + { + indices.push_back(count); + } + } + if (indices.empty()) + { + return r.end(); + } + std::sort(indices.begin(), indices.end()); + return cmRemoveIndices(r, indices); +} + #endif -- cgit v0.12