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?
Submitted by Radib Kar, on July 11, 2020

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!

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 3rd 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 3rd element in the sorted list would be arr[3]=4

The most important feature 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 n-th element:

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 3rd element(0-indexed) if the list was sorted.

Example:

#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:

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.






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.