C++ std::nth_element with std::deque
Implementable on C++11/14/17
Description:
nth_element( ) is a Standard Template Library function under the <algorithm> header
which rearranges the elements in a container such that element at nth position is the one which should be present at that position if the list were to be sorted.
which rearranges the elements in a container such that element at nth position is the one which should be present at that position if the list were to be sorted.
nth_element( ) Definition:
1. using < operator
template <class RandomAccessIterator>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
2. making use of comp
template <class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
*Here we are implementing the first definition.
Return type : returns no value.
Working: The nth_element( ) function takes in 3 parameters, start position iterator, nth position iterator and end position
iterator. In the range of start iterator to end iterator of the given container, the function treats the nth position as a pivot and rearranges the elements of the container such that elements present on the left of the nth position are less
than the element at the nth position and right greater. The element at nth position is obtained.
Container used here:- std::deque. Generalised version of Queue data structure, Double-ended Queue .
Implementation:
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int main () {
deque<int> arr{ 1, 5, 4, 2, 3, 6, 7, 8, 9 };
int pos = 0;
cout<<"Enter the position 'n' required."<<endl;
cin>>pos;
nth_element(arr.begin(), arr.begin()+pos, arr.end()); //rearranging the container elements to get the element at nth position
cout<<"If the container were to be in a sorted manner, The element at "<<pos<<" would be: "<<arr[pos]<<endl;
return 0;
}
Sample Output:Enter the position 'n' required.
3
If the container were to be in a sorted manner, The element at 3 would be: 4
Comments