Std::nth_element is not giving the correct element-CodePudding

I don't know why in this case the function std::nth_element is not giving me the correct median for the X axis.

For this test I created a vector of point: std::vector<Point> points = {Point {70, 70}, Point {50, 30}, Point {35, 45}};

The function call is:

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

Where start = 0; end = 2; In my mind the correct median for the X axis is Point(50, 30), instead this code gives me Point(70, 70).

Below there is the code for finding the median:

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

CodePudding user response：

The variable end is not correctly pointing to the end of the vector. Hence, you only perform nth_element() on the first 2 elements. Since the variable median value is 1, the point with greater x value will be returned.

You can use points.end() instead of points.begin() end.

CodePudding user response：

If you carefully read the description of the function in the CPP reference here, then you will see:

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.

Important for your problem is [first, last) which denotes a half open range.

And per definition a half-open range is one which includes the first element, but NOT the last one. The last is not included. If you want to include it, you need to go one step further. In your case: last 1.

So, you simply call the function with a wrong parameter. No issue.

The correct code could be something like this:

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