c++ - 在指针 vector 中添加非重复值的最有效方法

Question

我有这样的 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 上运行良好吗？

有什么解决这个问题的建议吗？

Answer 1

假设您的 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 进行排序。插入时避免最后排序。

所有这些中最高效的完全取决于您的用例，因为总是首先使用最简单的方法编写您的程序，然后分析它是否需要改进。