partial_sort_copy


function template
<algorithm>
template <class InputIterator, class RandomAccessIterator>
  RandomAccessIterator
    partial_sort_copy ( InputIterator first,InputIterator last,
                        RandomAccessIterator result_first,
                        RandomAccessIterator result_last );

template <class InputIterator, class RandomAccessIterator, class Compare>
  RandomAccessIterator
    partial_sort_copy ( InputIterator first,InputIterator last,
                        RandomAccessIterator result_first,
                        RandomAccessIterator result_last, Compare comp );

Copy and partially sort range

Copies the smallest elements in the range [first,last) to [result_first,result_last), sorting the elements copied. The amount of elements copied is (result_last-result_first) (unless this is more than the amount of elements in [first,last)).

[first,last) remains unmodified.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last
Input iterators to the initial and final positions of the sequence to copy from. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
result_first, result_last
Random-Access iterators to the initial and final positions of the destination sequence. The range used is [result_first,result_last).
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.


Return value

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// partial_sort_copy example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (5);
  vector<int>::iterator it;

  // using default comparison (operator <):
  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());

  // using function as comp
  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end(), myfunction);

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}


Output:
myvector contains: 1 2 3 4 5


Complexity

Performs approximately N*log(N2) comparisons, where N is the length of [first,last) and N2 is the length of the shortests between [first,last) and [result_first,result_last).

See also

partial_sort Partially Sort elements in range (function template)
sort Sort elements in range (function template)
copy Copy range of elements (function template)
remove_copy_if Copy range removing values (function template)