如何从未排序的std :: vector删除重复,同时保持原有的排序使用算法? [英] How to remove duplicates from unsorted std::vector while keeping the original ordering using algorithms?
问题描述
我有一个整数数组,我需要删除重复,同时保持每个整数的第一次出现的顺序。我可以看到这样做,但想象有一个更好的方法,使使用STL算法更好?插入操作不受我的控制,因此我无法在插入之前检查重复项。
I have an array of integers that I need to remove duplicates from while maintaining the order of the first occurrence of each integer. I can see doing it like this, but imagine there is a better way that makes use of STL algorithms better? The insertion is out of my control, so I cannot check for duplicates before inserting.
int unsortedRemoveDuplicates(std::vector<int> &numbers) {
std::set<int> uniqueNumbers;
std::vector<int>::iterator allItr = numbers.begin();
std::vector<int>::iterator unique = allItr;
std::vector<int>::iterator endItr = numbers.end();
for (; allItr != endItr; ++allItr) {
const bool isUnique = uniqueNumbers.insert(*allItr).second;
if (isUnique) {
*unique = *allItr;
++unique;
}
}
const int duplicates = endItr - unique;
numbers.erase(unique, endItr);
return duplicates;
}
如何使用STL算法?
推荐答案
方法是使用 std :: set
告诉你。它是过度的,并且缓存局部性(缓慢)。
smart *的方式是适当地使用 std :: vector
(确保看到脚注底部):
The naive way is to use std::set
as everyone tells you. It's overkill and has poor cache locality (slow).
The smart* way is to use std::vector
appropriately (make sure to see footnote at bottom):
#include <algorithm>
#include <vector>
struct target_less
{
template<class It>
bool operator()(It const &a, It const &b) const { return *a < *b; }
};
struct target_equal
{
template<class It>
bool operator()(It const &a, It const &b) const { return *a == *b; }
};
template<class It> It uniquify(It begin, It const end)
{
std::vector<It> v;
v.reserve(static_cast<size_t>(std::distance(begin, end)));
for (It i = begin; i != end; ++i)
{ v.push_back(i); }
std::sort(v.begin(), v.end(), target_less());
v.erase(std::unique(v.begin(), v.end(), target_equal()), v.end());
std::sort(v.begin(), v.end());
size_t j = 0;
for (It i = begin; i != end && j != v.size(); ++i)
{
if (i == v[j])
{
using std::iter_swap; iter_swap(i, begin);
++j;
++begin;
}
}
return begin;
}
然后你可以使用它:
int main()
{
std::vector<int> v;
v.push_back(6);
v.push_back(5);
v.push_back(5);
v.push_back(8);
v.push_back(5);
v.push_back(8);
v.erase(uniquify(v.begin(), v.end()), v.end());
}
*注意: >在典型情况下,其中重复项的数量不会太高。有关更彻底的性能分析,请参阅相关问题的相关答案。
这篇关于如何从未排序的std :: vector删除重复,同时保持原有的排序使用算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!