Is there an STL algorithm to find if an element is present in a container based on some tolerance?

Question

The problem I am trying to solve is a following: I have a container of floating points (vector of double vectors):

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

Then, assume I have a new point (double vector):

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

I want to check if a point v1 is present in dv container based on some tollerance. The distance between two vectors is calculated as Euclidean distance.

I have looked to the relevant questions and answers:

• How to find if an item is present in a std::vector?
• check if a std::vector contains a certain object?

and was also trying to use std::find_if() without any success, as it accepts only unary predicate.

At the moment I came up with a temporary solution. First, I created a generic function to find the Euclidean distance between two vectors:

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;
}

Second, I created check_if function to check if an element is presented in a container based on the tolerance (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;
}

And then I can use my code in a context like this:

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

So my questions are following:

1. Is there in-house an STL algorithm to achieve the same goal? If no, how could I improve my code? For example, I'm not sure how could I use any distance function in check_in() instead of EuclideanDistance()?
2. I wonder if AshleysBrain suggestion (https://stackoverflow.com/a/3451045/3737891) to use std::set instead of std::vector could make any difference having a container of floating points?

Answer 1

and was also trying to use std::find_if() without any success, as it accepts only unary predicate.

That's all you want anyway. The single argument is going to be the elements of the vector you're looking in.

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;
    });

---

On another note, if your points are all a fixed dimension then using vector<double> probably is not the right representation. A tuple<double,double>, or an array<double 2>, or a custom class that has overloaded operators would probably all be appropriate replacements.

Answer 2

Is there in-house an STL algorithm to achieve the same goal? If no, how could I improve my code? For example, I'm not sure how could I use any distance function in check_in() instead of EuclideanDistance()?

Non exactly STL (if I'm not wrong), but...

As suggested by others, instead of a std::vector<double>, for points coordinates, you should consider std::tuple<double, double, ...> or, if they are 2D points (your case, if I'm not wrong), std::pair<double, double>.

But there is another tamplated class that I suggest you (but only for 2D points, not for 3D points): std::complex<T>

Your dv could be

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

The new point

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

Another suggestion: avoid the square root (it's costly to compute); check the square of the distance against the square of Epsilon; using std::norm of the difference of a couple of complex numbers you get exactly (if I'm not wrong) the square of the distance

Using std::complex<double>, the example from bames53 become simply

#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;
 }

--- EDIT ---

I wonder if AshleysBrain suggestion (https://stackoverflow.com/a/3451045/3737891) to use std::set instead of std::vector could make any difference having a container of floating points?

I don't think that the "floating point" component is important in choosing between std::vector and std::set.

By example, if (for your application) it's important to mantain the order of insertion of points, you should use std::vector (or std::queue); if you have to do a lot of searches, I think is better std::set (or std::multiset if you use point with molteplicity`).

If you decide to use std::complex<double>, I give you another suggestion: give a look at std::valarray.

I don't know what exactly do you want to do with your points but... I suppose can be useful.

p.s.: sorry for my bad English