c++ - 检查点是否在向量内

Question

我想检查一个给定的点x和y值是否在点向量内：

bool inside_vector(int x, int y, vector<Point2i>& points)
{
  for(vector<Point2i>::const_iterator it = points.begin();
    it != points.end();
    ++it)
  {
    if(it->x == y && it->y == y)
    {
      return true;
    }
  }
  return false;
}

还有其他没有for循环的方法吗？

Answer 1

您可以将std::find 或 std::find_if与合适的仿函数一起使用，以避免编写自己的循环。但是你并没有获得复杂性：它仍然是 O(n)。例如，

bool operator==(const Point2i& lhs, const Point2i& rhs)
{
  return lhs.x == rhs.x && lhs.y == rhs.y;
}

Point2Di somePoint = Point2Di(x,y); // point to find
auto it = std::find(points.begin(), points.end(), somePoint);

或者，没有相等运算符，

auto it = std::find_if(points.begin(), 
                       points.end(), [&somePoint](const Point2Di& p)
                                     {return somePoint.x == p.x && somePoint.y == p.y;});

Answer 2

假设您已operator==为您的Point2i结构定义，您可以使用std::find()，如下所示：

std::vector<Point2i>::const_iterator findIt = std::find(
    points.begin(),
    points.end(),
    Point2i(x, y));

我还假设您有一个Point2i采用两个坐标的构造函数。