我有这样的 vector
vector<Point*> points;
我想给这个 vector 添加一个新的点。但是我最多有 50 个内部 vector 点,但其中很多都是重复的。实现添加非重复值的最有效方法是什么。到目前为止,我是这样做的:
boolean add_point(vector<Point*> *p, int x, int y){
for(vector<Point*>::iterator i = p->begin(); i != p->end(); i++){
if((*i)->x == x && (*i)->y == y)
return false;
}
p->push_back(new Point(x,y));
return true;
}
然而,当我调用该函数时,我的应用程序的执行时间增加了很多。
根据我尝试做的堆栈主题之一:
sort( points.begin(), points.end() );
points.erase( unique( points.begin(), points.end() ), points.end() );
然而,两种代码的结果是不同的。排序/删除在指针 vector 上运行良好吗?
有什么解决这个问题的建议吗?
最佳答案
假设您的 Point
结构类似于
struct Point { int x, y; }
然后只存储Points
自己在 vector 中,并提供比较功能
bool operator==(Point const& p1, Point const& p2)
{
return p1.x == p2.x && p1.y == p2.y
}
bool operator<(Point const& p1, Point const& p2)
{
return p1.x != p2.x ? p1.x < p2.x : p1.y < p2.y;
}
之后,您可以使用以下方法删除重复项:
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
如果你想让你的容器自动防止重复使用 std::set<Point>
/std::unordered_set<Point>
(您需要为后者提供 std::hash
的特化),尽管使用具有最终排序的 vector 并删除重复项总体上可能更快。正如@PorkyBrain 指出的那样,您可以使用 std::lower_bound
对 vector 进行排序。插入时避免最后排序。
所有这些中最高效的完全取决于您的用例,因为总是首先使用最简单的方法编写您的程序,然后分析它是否需要改进。
关于c++ - 在指针 vector 中添加非重复值的最有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24989745/