Home » C++ STL

std::nth_element() in C++

C++ STL | std::nth_element(): In this article, we are going to see what the use of the standard library function nth_element() is and details about the syntax, usage, and application? By Radib Kar Last updated : December 11, 2023

Introduction to std::nth_element() in C++

The standard library of C++ has a huge number of functions that are not so explored but can be very handy in case of specific usages. It helps you to write less number of codes and do things quickly. Say, you are building some backend system in C++ and that has thousands of lines already. In such scenarios, these standard library functions help a lot to reduce codebase size. Also in competitive coding where submission time matters, these kinds of function usages may make your day!

C++ std::nth_element()

The std::nth_element() is one such std function which helps to find nth element out of a list range if the list was sorted.

For example,

Say the list is:
[4, 1, 2, 3, 6, 7, 5]

Using nth_element() function if you want to find 3^rd element(0-indexed) out of the entire range you may have your list updated to something like,

[3, 1, 2, 4, 6, 7, 5]

Which tells you that the 3^rd element in the sorted list would be arr[3]=4

Features C++ std::nth_element()

The most important features of this function is:

1. It only gives your nth element in the correct order
2. For the rest of the element, you can't guess what would be the arrangement. It depends on the compiler. What you can get assured is that the elements preceding the nth element would be all smaller than the nth element and the element which comes after the nth element are greater than the nth element.

Syntax of C++ std::nth_element()

Below is the syntax of nth_element() function:

void nth_element(iterator start, iterator nth, iterator end)
// so it doesn't returns anything,
// rather updates the list internally

iterator start  = start of your range
iterator end    = end of your range
iterator nth    = nth term you want to see in position 
                  if the list was sorted (0-indexed)

So for the above example say the vector name is arr. Then, it would be:

nth_iterator(arr.begin(),arr+3,arr.end())

Since the range is first to last of the list and we need to find the 3^rd element(0-indexed) if the list was sorted.

Example of C++ std::nth_element()

This example demonstrates the use of std::nth_element() in C++.

#include <bits/stdc++.h>
using namespace std;

//to print the vector
void print(vector<int> arr)
{
    for (auto it : arr) {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    //to see how it's initialized 
    vector<int> arr{ 4, 1, 2, 3, 6, 7, 5 };

    cout << "Printing initially...\n";
    print(arr);

    //find 3rd element if list was sorted
    nth_element(arr.begin(), arr.begin() + 3, arr.end());
    
    cout << "the 3rd element if the list was sorted is: " << arr[3] << endl;

    cout << "the new rearrangement of the array...\n";
    print(arr);
    
    return 0;
}

Output

Printing initially...
4 1 2 3 6 7 5
the 3rd element if the list was sorted is: 4
the new rearrangement of the array...
3 1 2 4 5 6 7

Application or Usages of C++ std::nth_element()

We can use this standard library function whenever we need to find the nth_element() if the array was sorted at one go.

An important application can be finding the median in an unsorted array.