Is there a way to get element position from within a lambda passed to sort?

Question

Lets assume I call sort with a lambda like this, with nearPoints being a vector of points in 3D.

sort(nearPoints.begin(), nearPoints.end(),
     [srcPoint](const kd_point &A, const kd_point &B)
     {return Distance(srcPoint, A) < Distance(srcPoint, B); });

In order to save on redundant calls to Distance, I would like to pre-calculate the values, and have the call to sort use them.

The elegant solution is, IMHO, to prep a second vector with distances, read it in the lambda, and switch elements as necessary.

My problem is how to find A's and B's indexes in nearPoints, so I would know which elements to access in the second vector. Is there a way to do it?

I know I can make a new vector with each elements containing a point and its distance from srcPoint, but that would require populating the new vector before the sort, and extracting the points back in the right order after the sort, which strikes me as inelegant.

Well, the index is just `&a - nearPoints.data()`, but it is useless here since `sort` is going to be swapping the elements around all over the place. — T.C., Dec 03 '15 at 20:34
If you want to speed this up, sort by distance-squared. It'll give the same order, but the `sqrt` operation is by far the most expensive part of a euclidean distance calculation — Ben Voigt, Dec 03 '15 at 20:39
Good starting points [are here](http://stackoverflow.com/a/11329249/2642204) [and here](http://stackoverflow.com/a/10962575/2642204). — BartoszKP, Dec 03 '15 at 20:45

bolov · Answer 1 · 2015-12-04T08:06:23.747

It can be done, you can get the index:

  std::sort(std::begin(near_points), std::end(near_points),
      [src_point, &near_points](int const &a, int const &b){
        auto ia = &a - near_points.data();
        auto ib = &b - near_points.data();
        ...
        return ...;
      });

But this would be useless, as the elements are moved all the time by the sort.

What you could do instead is create a hash map map (std::map or std::unordered_map) of <kd_point, int> where you precompute the distances. You would have to measure though to see if it will be faster, as a map adds a considerable overhead, both in terms of space and time. The computation of Distance() would have to be very slow in order to justify this.

If the Distance is just an euclidean distance, the simple yet effective optimization you can do is this: Since all you do is compare the distances, you don't need to compute the square root (which is the most time consuming). So you have SquareDist where you just compute (x2-x1)^2 + .... and the condition for the lambda becomes SquareDist(src, a) < SquareDist(src, b) You have to be careful not to overflow.

Is there a way to get element position from within a lambda passed to sort?

1 Answers1