Difference between revisions of "cpp/algorithm/partial sort copy"

Revision as of 05:10, 14 April 2020

Sorts some of the elements in the range [first, last) in ascending order, storing the result in the range [d_first, d_last).

At most d_last - d_first of the elements are placed sorted to the range [d_first, d_first + n). n is the number of elements to sort (n = min(last - first, d_last - d_first)). The order of equal elements is not guaranteed to be preserved.

Parameters

Return value

an iterator to the element defining the upper boundary of the sorted range, i.e. d_first + min(last - first, d_last - d_first).

Complexity

O(N·log(min(D,N)), where N = std::distance(first, last), D = std::distance(d_first, d_last) applications of cmp.

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

See also the implementations in libstdc++ and libc++.

Example

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
 
int main()
{
    std::vector<int> v0{4, 2, 5, 1, 3};
    std::vector<int> v1{10, 11, 12};
    std::vector<int> v2{10, 11, 12, 13, 14, 15, 16};
    std::vector<int>::iterator it;
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
 
    std::cout << "Writing to the smaller vector in ascending order gives: ";
    for (int a : v1) {
        std::cout << a << " ";
    }
    std::cout << '\n';
    if(it == v1.end())
        std::cout << "The return value is the end iterator\n";
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(), 
                                std::greater<int>());
 
    std::cout << "Writing to the larger vector in descending order gives: ";
    for (int a : v2) {
        std::cout << a << " ";
    }
    std::cout << '\n' << "The return value is the iterator to " << *it << '\n';
}

Writing to the smaller vector in ascending order gives: 1 2 3
The return value is the end iterator
Writing to the larger vector in descending order gives: 5 4 3 2 1 15 16
The return value is the iterator to 15

See also