C++ std::nth_element with std::deque














































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.

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

More Articles of GHANASHYAM KATTI:

Name Views Likes
C++ std::reverse with std::vector 658 24
C++ std::search with std::vector 613 15
C++ std::is_permutation with std::vector 664 20
C++ program to reverse a path in binary search tree using queue 695 17
C++ std::partial_sort with std::vector 609 23
C++ std::partition_point with vector 631 15
C++ std::partition_point with multiset 704 27
C++ program to calculate tilt of binary tree 507 16
C++ program to find right sibling of a binary tree with parent pointers 936 16
C++ program to find root of the tree where children id sum for every node is given 665 21
C++ std::count with std::vector 673 23
C++ std::mismatch with std::deque 605 26
C++ std::partial_sort with std::array 758 12
C++ program to remove nodes on root to leaf paths of length < k 521 20
C++ std::mismatch with std::array 950 15
C++ std::is_permutation with std::array 570 14
C++ std::nth_element with std::array 786 23
C++ std::count_if with std::list 687 15
C++ std::move_backward with std::deque 636 12
C++ std::mismatch with std::list 576 19
C++ std::move_backward with std::list 698 20
C++ std::random_shuffle with std::array 564 24
C++ std::mismatch with std::forward_list 552 19
C++ std::count with std::array 772 26
C++ program to find simple recursive solution to check whether binary search tree contains dead end 728 19
C++ program to find ways to color a skewed tree such that parent and child have different colors 681 28
C++ std::count_if with std::array 786 23
C++ program to find deepest left leaf node in a binary tree using recursion 456 20
C++ program to check if a given binary tree is sumtree 546 11
C++ program to calculate size of a tree using recursion 760 11
C++ program to transform a binary search tree to greater sum tree 493 14
C++ program to find longest path with same values in a binary tree 965 11
C++ program to find extract leaves of a binary tree in a doubly linked list 514 17
C++ program to find sum of nodes at k-th level in a tree represented as string 839 16
C++ std::count_if with std::multiset 740 17
C++ std::count with std::deque 1572 20
C++ program to find all duplicate subtrees 690 15
C++ program to find mirror of a given node in binary tree 604 26
C++ program to find deepest right leaf node in a binary tree using recursion 549 17
C++ std::mismatch with std::vector 626 19
C++ program to find maximum width of a binary tree 637 14
C++ std::partition_point with std::array 595 16
C++ program to find distance from root to given node in a binary tree 510 14
C++ program to find factor tree of a given number 1171 16
C++ std::partition_point with std::list 803 13
C++ std::reverse with std::deque 896 21
C++ program to remove all nodes which don%u2019t lie in any path with sum>= k 593 17
C++ std::count with std::list 559 11
C++ std::partition_point with std::deque 662 20
C++ std::count_if with std::deque 674 26
C++ std::partial_sort with std::deque 683 13
C++ std::mismatch with std::multiset 656 21
C++ std::search with std::deque 581 20
C++ std::partition_point with std::forward_list 578 14
C++ std::count_if with std::vector 811 16
C++ program to find largest subtree having identical left and right subtrees 546 14
C++ std::random_shuffle with std::deque 1099 15
C++ std::nth_element with std::vector 630 19
C++ std::move_backward with std::array 724 20
C++ program to find a number in minimum steps 597 23
C++ std::reverse with std::array 724 18
C++ std::random_shuffle with std::vector 632 14
C++ program to check if all leaves are at same level 490 15
C++ std::count with std::multiset 449 14
C++ program to connect nodes at same level 523 21
C++ std::move_backward with std::vector 658 20
C++ std::is_permutation with std::deque 530 13
C++ std::search with std::array 685 17
C++ std::nth_element with std::deque 1220 18
C++ program to find longest consecutive sequence in binary tree 565 11

Comments