Search code examples
c++vectoriteratormedian

Std::nth_element is not giving the correct element


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

Solution

  • 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.