Possible bug in KDTree.h?

[SethKasmann]

I was browsing your implementation. On line 145 of KDTree.h you have this:

std::nth_element(start, mid, end, cmp); // linear time partition

// move left (if needed) so that all the equal points are to the right
// The tree will still be balanced as long as there aren't many points that are equal along each axis
while (mid > start && (mid - 1)->first[axis] == mid->first[axis]) {
    --mid;
}

How is this supposed to work? std::nth_element does not sort the elements that are lower, it just performs a partition. So even when the second condition fails of your while loop, you could still have elements that are equal at a lower index since it's not fully sorted.

From cpp reference https://en.cppreference.com/w/cpp/algorithm/nth_element:

More formally, nth_element partially sorts the range [first, last) in ascending order so that the condition !(*j < *i) (for (1-2), or comp(*j, *i) == false for (3-4)) is met for any i in the range [first, nth) and for any j in the range [nth, last). The element placed in the nth position is exactly the element that would occur in this position if the range was fully sorted.

I think if you want to use nth element you could do something like this (please test):

std::nth_element(start, mid, end, cmp); // linear time partition

// move left (if needed) so that all the equal points are to the right
// The tree will still be balanced as long as there aren't many points that are equal along each axis
mid = std::partition(start, mid, [=](const auto& em) {
    return em.first[axis] != mid->first[axis];
});