有没有STL算法可以基于某个容差找到容器中是否存在某个元素？

Question

我是一位有用的助手，能够将文本进行翻译。

我试图解决的问题是：我有一个浮点数容器（双向量向量）：

std::vector<std::vector<double>> dv { {0.0, 0.0}, {1.0, 0.0}, {0.0, 1.0}, {1.0, 1.0} };

然后，假设我有一个新点（双向量）：

std::vector<double> v1 {0.0001, 1.0};

我想检查一个点v1是否在容器dv中，基于一些公差。两个向量之间的距离被计算为欧几里得距离。

我已经查看了相关的问题和答案：

• 如何查找std :: vector中是否存在项目？
• 检查std :: vector是否包含某个对象？

并尝试使用std :: find_if()，但没有成功，因为它仅接受一元谓词。

目前，我想到了一个临时解决方案。首先，我创建了一个通用函数来查找两个向量之间的欧几里得距离：

template <typename InputIt1, typename InputIt2>
double EuclideanDistance(InputIt1 beg1, InputIt1 end1, InputIt2 beg2) {
  double val = 0.0;
  while (beg1 != end1) {
    double dist = (*beg1++) - (*beg2++);
    val += dist*dist;
  }
  return val > 0.0? sqrt(val) : 0.0;
}

第二步，我创建了check_if函数，根据公差（Epsilon）检查一个元素是否存在于容器中。

template <typename Container, typename Element>
bool check_if(const Container& c, const Element& el,
              const double Epsilon = 0.001) {
  auto pos = c.begin();
  for (; pos != c.end(); ++pos) {
    if (EuclideanDistance(pos->begin(), pos->end(), el.begin()) < Epsilon) {
      return true;
    }
  }
  return false;
}

然后我可以在这样的上下文中使用我的代码：

// Check if container contains v1 using check_if()
if (check_if(dv, v1)) {
  std::cout << "Using check_if() - Container contains v1\n";
}

所以我的问题如下：

1. 是否有内部STL算法来实现相同的目标？如果没有，我该如何改进我的代码？例如，我不确定如何在check_in()中使用任何距离函数而不是EuclideanDistance()？
2. 我想知道AshleysBrain建议（https://dev59.com/-3A75IYBdhLWcg3wJFcL#3451045）使用std::set而不是std::vector，对于一个包含浮点数的容器是否会有任何区别？

- Remis

---

我会将点存储在std::pair<double>或std::array<double,2>中 - 对于固定大小的数据，std::vector是过度杀伤，此外您需要验证它始终具有2个元素。 - Slava

使用捕获 Epsilon 的 lambda，并将该 lambda 传递给 find_if。 - Praetorian

再用std::find_if试一次，因为我看不出任何它不能工作的原因。 - juanchopanza

@Slava：EuclideanDistance接受一个包含double的容器的迭代器。如果OP使用了std::vector<Point>，那么代码会更清晰，这样就可以写成EuclideanDistance(pt, expected_pt) < Epsilon。 - Jarod42

@Jarod42 如果 OP 使用 Point，那么 v1 将成为该类型的一个对象，您也不需要使用 v1.begin()。 - Slava

Answer 1

同时他也尝试使用std::find_if()，但没有成功，因为它只接受一元谓词。

无论如何，这正是你想要的。单个参数将是您要查找的向量元素。

std::vector<std::vector<double>> dv{
    {0.0, 0.0}, {1.0, 0.0}, {0.0, 1.0}, {1.0, 1.0}};

std::vector<double> v1 {0.0001, 1.0};

auto find_result =
    std::find_if(begin(dv), end(dv), [&v1](std::vector<double> const &dve) {
      assert(dve.size() == v1.size());
      return EuclideanDistance(begin(dve), end(dve), begin(v1)) < 0.001;
    });

---

另外，如果你的点都是固定维度的话，使用 vector<double> 可能不是正确的表示方法。一个 tuple<double,double>、array<double 2> 或者重载了运算符的自定义类可能都是适当的替代方案。

- bames53

---

在我的情况下，所有的点都是n维向量。然而，只有在执行过程中，我才会知道这些点的确切维度(n)，即在不同的运行中，这些点的维度可能会有所不同。然而，在同一次运行中，所有的点都具有相同的维度。因此，我的目标是选择正确的容器来存储这些点，并且后续使用高效的算法来检查一个新的点是否已经存在于这个容器中。 - Remis

Answer 2

是否有内部的STL算法可以达到相同的目的？如果没有，我该如何改进我的代码？例如，在check_in()中，我不确定如何使用任何距离函数来代替EuclideanDistance()？

非精确地说，不是STL（如果我没记错的话），但是......

正如其他人建议的那样，对于点的坐标，您应该考虑使用std::tuple或者如果它们是2D点（您的情况，如果我没有记错）,则使用std::pair，而不是std::vector。

但是还有另一个模板化的类我建议你使用（仅适用于2D点，而不是3D点）：std::complex 您的dv可以是：

std::vector<std::complex<double>> dv { {0.0, 0.0}, {1.0, 0.0}, {0.0, 1.0}, {1.0, 1.0} };

新观点

std::complex<double>  v1 {0.0001, 1.0};

另一个建议：避免平方根（计算成本高）；将距离的平方与 Epsilon 的平方进行比较；使用一对复数的差的std::norm，您可以准确地（如果我没有错的话）得到距离的平方。

使用std::complex<double>，bames53的示例变得简单。

#include <vector>
#include <complex>
#include <iostream>
#include <algorithm>

int main()
 {
   std::vector<std::complex<double>> dv
    { {0.0, 0.0}, {1.0, 0.0}, {0.0, 1.0}, {1.0, 1.0} };

   std::complex<double> v1 {0.0001, 1.0};

   auto find_result =
      std::find_if(begin(dv), end(dv), [&v1](std::complex<double> const &dve)
                   { return std::norm(v1-dve) < 0.000001; });

   std::cout << *find_result << std::endl;  // print (0,1)

   return 0;
 }

--- 编辑 ---

我想知道AshleysBrain的建议(https://dev59.com/-3A75IYBdhLWcg3wJFcL#3451045)，即在浮点数容器中使用std::set而不是std::vector，是否有任何区别？

我认为在选择std::vector和std::set时，“浮点数”组件并不重要。

例如，如果（对于您的应用程序）保持点插入顺序很重要，则应使用std::vector（或std::queue）；如果您需要进行大量搜索，则我认为最好使用std::set（或std::multiset如果您使用具有多重性的点）。

如果您决定使用std::complex<double>，我给出另一个建议：看一下std::valarray。

我不知道您想要如何处理您的点，但是......我认为这可能会有用。

p.s.：对我的糟糕英语感到抱歉

- max66

Answer 3

根据您的评论（“在我的情况下，点可以是任意维度向量...”），我了解到建议使用 std::complex<double> 来表示点坐标（或者使用 std::pair<double, double> 或 std::tuple<double, double, ...>）不适用。

因此，我建议使用 std::array<double, N> 代替 std::vector<double>，其中 N 是点的维数。

我仍然建议避免使用平方根，并将距离的平方与 Epsilon 的平方进行比较。

我的第三个建议是以以下方式使用 std::inner_product()（使用 N == 3 的示例）

#include <vector>
#include <array>
#include <numeric>
#include <iostream>
#include <algorithm>

int main()
 {
   std::vector<std::array<double, 3>> dv
    { {{0.0, 0.0, 0.0}}, {{1.0, 0.0, 0.0}},
      {{0.0, 1.0, 0.0}}, {{0.0, 0.0, 1.0}},
      {{1.0, 1.0, 0.0}}, {{1.0, 0.0, 1.0}},
      {{0.0, 1.0, 1.0}}, {{1.0, 1.0, 1.0}} };

   std::array<double, 3> v1 { {0.0001, 1.0, -0.0001} };

   auto result = std::find_if(dv.cbegin(), dv.cend(),
           [&v1](std::array<double, 3> const & dve)
            { return std::inner_product(v1.cbegin(), v1.cend(),
                 dve.cbegin(), 0.0, std::plus<double>(),
                 [](double d1, double d2){ auto d = d1-d2; return d*d; })
                 < 0.00001; });

   std::cout << "result: ";

   for ( const auto & d : *result )
      std::cout << '(' << d << ')';

   std::cout << std::endl;

   return 0;
 }

输出是。

result: (0)(1)(0)

对于我的英语再次表示抱歉。

- max66