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::partition_point with std::list 412 13
C++ std::partition_point with std::forward_list 332 14
C++ std::partition_point with multiset 407 27
C++ std::partition_point with std::array 367 16
C++ std::partition_point with std::deque 349 20
C++ std::partition_point with vector 309 15
C++ std::move_backward with std::list 360 20
C++ std::move_backward with std::deque 343 12
C++ std::move_backward with std::vector 341 20
C++ std::move_backward with std::array 286 20
C++ std::mismatch with std::forward_list 309 19
C++ std::mismatch with std::multiset 372 21
C++ std::mismatch with std::list 321 19
C++ std::mismatch with std::deque 355 26
C++ std::mismatch with std::vector 303 19
C++ std::mismatch with std::array 422 15
C++ std::partial_sort with std::array 356 12
C++ std::partial_sort with std::deque 283 13
C++ std::partial_sort with std::vector 324 23
C++ std::is_permutation with std::array 264 14
C++ std::is_permutation with std::vector 282 20
C++ std::is_permutation with std::deque 269 13
C++ std::reverse with std::deque 291 21
C++ std::reverse with std::vector 317 24
C++ std::reverse with std::array 281 18
C++ std::random_shuffle with std::deque 283 15
C++ std::random_shuffle with std::vector 330 14
C++ std::random_shuffle with std::array 299 24
C++ std::search with std::array 325 17
C++ std::search with std::vector 294 15
C++ std::search with std::deque 341 20
C++ std::nth_element with std::deque 509 18
C++ std::nth_element with std::array 338 23
C++ std::nth_element with std::vector 296 19
C++ std::count_if with std::vector 403 16
C++ std::count_if with std::list 290 15
C++ std::count_if with std::deque 307 26
C++ std::count_if with std::multiset 262 17
C++ std::count_if with std::array 325 23
C++ std::count with std::array 381 26
C++ std::count with std::multiset 248 14
C++ std::count with std::deque 335 20
C++ std::count with std::list 269 11
C++ std::count with std::vector 331 23
C++ program to reverse a path in binary search tree using queue 317 17
C++ program to connect nodes at same level 297 21
C++ program to remove all nodes which don%u2019t lie in any path with sum>= k 327 17
C++ program to find ways to color a skewed tree such that parent and child have different colors 321 28
C++ program to find root of the tree where children id sum for every node is given 329 21
C++ program to find largest subtree having identical left and right subtrees 248 14
C++ program to find mirror of a given node in binary tree 325 26
C++ program to find longest path with same values in a binary tree 278 11
C++ program to remove nodes on root to leaf paths of length < k 275 20
C++ program to find a number in minimum steps 279 23
C++ program to find longest consecutive sequence in binary tree 288 11
C++ program to find all duplicate subtrees 281 15
C++ program to find right sibling of a binary tree with parent pointers 331 16
C++ program to find extract leaves of a binary tree in a doubly linked list 236 17
C++ program to check if a given binary tree is sumtree 217 11
C++ program to find simple recursive solution to check whether binary search tree contains dead end 332 19
C++ program to find factor tree of a given number 384 16
C++ program to calculate tilt of binary tree 227 16
C++ program to check if all leaves are at same level 213 15
C++ program to find distance from root to given node in a binary tree 191 14
C++ program to find maximum width of a binary tree 190 14
C++ program to find deepest right leaf node in a binary tree using recursion 194 17
C++ program to find deepest left leaf node in a binary tree using recursion 153 20
C++ program to calculate size of a tree using recursion 348 11
C++ program to transform a binary search tree to greater sum tree 219 14
C++ program to find sum of nodes at k-th level in a tree represented as string 207 16

Comments