gpt4 book ai didi

c++ - 删除重复项和对 vector 进行排序的最有效方法是什么?

转载 作者:IT老高 更新时间:2023-10-28 11:25:23 26 4
gpt4 key购买 nike

我需要获取一个可能包含很多元素的 C++ vector ,删除重复项并对其进行排序。

我目前有以下代码,但它不起作用。

vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());

我怎样才能正确地做到这一点?

此外,先删除重复项(类似于上面的代码)还是先执行排序更快?如果我确实先执行排序,是否保证在执行 std::unique 后保持排序?

或者还有其他(可能更有效)的方法来完成这一切吗?

最佳答案

我同意 R. PateTodd Gardner ;一个 std::set在这里可能是个好主意。即使您无法使用 vector ,但如果您有足够多的重复项,您最好创建一个集合来完成这项繁琐的工作。

让我们比较三种方法:

只使用 vector ,排序+唯一

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

转换为设置(手动)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

转换为集合(使用构造函数)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

随着重复数量的变化,这些表现如何:

comparison of vector and set approaches

总结:当重复的数量足够大时,实际上转换为集合然后将数据转储回 vector 会更快

由于某种原因,手动进行集合转换似乎比使用集合构造函数更快——至少在我使用的玩具随机数据上。

关于c++ - 删除重复项和对 vector 进行排序的最有效方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1041620/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com