我只想从容器中获取独特的元素。假设 srcContainer
是我想要从中获取独特元素的容器。我查看了三个选项:
使用 std::unique
std::sort(srcContainer.begin(), srcContainer.end()); srcContainer.erase(std::unique(srcContainer.begin(), srcContainer.end()), srcContainer.end());
使用 BOOST::unique
boost::erase(srcContainer, boost::unique<boost::return_found_end>(boost::sort(srcContainer)));
我自己的方法
std::set<T> uniqueElems(srcContainer.begin(), srcContainer.end()); srcContainer.clear(); srcContainer.insert(srcContainer.end(), uniqueElems.begin(), uniqueElems.end());
问题 1. 和 2. 是它们改变了成员在原始 srcContainer 中出现的顺序。对于 3.,顺序没有变化,此外,与上面的 1. 和 2(是因为 3. 中没有显式排序吗??)相比,它提供了更好的性能。上面 3 种方法经过的挂钟时间和 srcContainer 中的元素数量如下:
srcContainer 的大小(包含整数)= 1e+6
- std::unique = 1.04779 秒
- BOOST::unique = 1.04774 秒
- 自己的方法 = 0.481638 秒srcContainer 的大小(包含整数)= 1e+8
- std::unique = 151.554 秒
- BOOST::unique = 151.474 秒
- 自己的方法 = 57.5693 秒
我的问题是:
- 是否有更好的方法来使用 std::unique 或 BOOST::unique 或任何其他代码来查找唯一性并保持容器中的原始顺序?
- 使用上述方法 3 的任何问题。
为了性能分析,srcContainer
创建如下:
std::vector<int> srcContainer;
int halfWay = numElems/2;
for (size_t k=0; k<numElems; ++k) {
if (k < halfWay)
srcContainer.push_back(k);
else
srcContainer.push_back(k - halfWay);
}
编辑:
同意方法 3 的评论。也改变了元素的顺序。有没有更好的方法在不改变顺序的情况下获得独特的元素?
谢谢
最佳答案
根据有关源数据的信息进行编辑:
您看到集合插入比排序 vector 更快完成的原因是您的输入数据是两个已经排序的范围。对于快速排序(通常由 std::sort
使用),这是一个退化的情况,也是您可以给它的最糟糕的输入之一。对于 1e8
的输入大小,将排序从 std::sort
更改为 std::stable_sort
将运行时间从 ~25s 缩短到 <9s。
如果你想保持原来的项目顺序,你可以尝试像下面这样的东西,它会保留所有项目的哈希值。我不知道这会是什么性能,但是例如,您可以使用散列和 remove_if
的方法,如下所示:
struct Remover
{
explicit Remover(hash& found_items) : found_items_(found_items) { }
bool operator()(const Iter& item) { retval = <does exist in hash>; add to hash; return retval; }
hash& found_items_;
};
hash dup_finder;
Remover remover(dup_finder);
std::erase(std::remove_if(src.begin(), src.end(), remover), src.end());
我的回答的原始组成部分:
如果源容器中的元素大部分已经排序,您可能会看到使用 stable_sort
的性能比调用 unique
之前的排序更好。如果没有关于 yoru 数据集的更多信息,我无法猜测是什么导致选项 3 的性能优于 1 和 2。
选项 3 应该删除唯一值,但请记住,无论您断言什么,它仍会按照与前两个选项完全相同的方式重新排序项目。
关于c++ - 从容器中获取唯一元素 [c++],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16489848/