Std::nth_element 没有给出正确的元素

Question

我不知道为什么在这种情况下函数 std::nth_element 没有给我正确的 X 轴中值。

为了这个测试，我创建了一个点向量：std::vector<Point> points = {Point {70, 70}, Point {50, 30}, Point {35, 45}};

函数调用是：

int median = (start + end) / 2;
Point split = get(points.begin() + start, points.begin() + median, points.begin() + end);

其中 start = 0; end = 2; 在我看来，X 轴的正确中位数是 Point(50, 30)，而这段代码给了我 Point(70, 70).

下面是求中位数的代码：

template <typename Iterator>
    Point get(Iterator start, Iterator median, Iterator end) 
    {
        std::nth_element(
            start, 
            median, 
            end,
            [](const Point &point1, const Point &point2) { 
                return point1.getX() < point2.getX(); 
            }
        );
    
        std::vector<Point>::iterator iter = median;
        std::cout << *iter << std::endl;
        return *iter;
    }

Answer 1

变量 end 没有正确指向向量的末尾。因此，您只对前 2 个元素执行 nth_element()。由于变量median值为1，所以返回x值较大的点。

您可以使用 points.end() 而不是 points.begin() + end。

Answer 2

如果你仔细阅读了CPP参考资料here中对函数的描述，你会看到：

nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that: The element pointed at by nth is changed to whatever element would occur in that position if [first, last) were sorted.

对您的问题很重要的是 [first, last)，它表示半开范围。

根据定义，half-open 范围是包含第一个元素的范围，但 NOT 最后一个元素。最后一个不包括在内。如果要包含它，则需要更进一步。在你的情况下：last+1.

所以，你只是用错误的参数调用函数。没问题。

正确的代码可能是这样的：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

struct Point {
    int x{};
    int y{};
    int getX() const { return x; }
    int getY() const { return y; }

    friend std::ostream& operator << (std::ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
};

template <typename Iterator>
Point get(Iterator start, Iterator median, Iterator end)
{
    std::nth_element(
        start,
        median,
        end,
        [](const Point& point1, const Point& point2) {
            return point1.getX() < point2.getX();
        }
    );

    std::vector<Point>::iterator iter = median;
    return *iter;
}

int main() {
    std::vector<Point> points = { Point {70, 70}, Point {50, 30}, Point {35, 45} };

    int start = 0, end = 2;
    int median = (start + end) / 2;
    Point split = get(points.begin() + start, points.begin() + median, points.begin()+end+1);
    std::cout << split << '\n';
}

Std::nth_element 没有给出正确的元素

Std::nth_element is not giving the correct element

c++

iterator

vector

median