分隔操作（Partitioning operations）

将容器中指定范围内的元素根据特定条件分成两组
头文件：#include <algorithm>

一、is_partitioned

1、原型：

template< class InputIt, class UnaryPredicate >
bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

2、说明：

测试是否已经分割好

3、官网demo

#include <algorithm>
#include <array>
#include <iostream>int main()
{std::array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };auto is_even = [](int i){ return i % 2 == 0; };std::cout.setf(std::ios_base::boolalpha);std::cout << std::is_partitioned(v.begin(), v.end(), is_even) << ' ';std::partition(v.begin(), v.end(), is_even);std::cout << std::is_partitioned(v.begin(), v.end(), is_even) << ' ';std::reverse(v.begin(), v.end());std::cout << std::is_partitioned(v.begin(), v.end(), is_even);
}

Output:

false true false

二、partition

1、原型：

template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

2、说明：

将元素分成两组

3、官方demo

快速排序

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>template <class ForwardIt>void quicksort(ForwardIt first, ForwardIt last){if(first == last) return;auto pivot = *std::next(first, std::distance(first,last)/2);ForwardIt middle1 = std::partition(first, last, [pivot](const auto& em){ return em < pivot; });ForwardIt middle2 = std::partition(middle1, last, [pivot](const auto& em){ return !(pivot < em); });quicksort(first, middle1);quicksort(middle2, last);}int main()
{std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};std::cout << "Original vector:\n    ";for(int elem : v) std::cout << elem << ' ';auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});std::cout << "\nPartitioned vector:\n    ";std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));std::cout << " * ";std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};std::cout << "\nUnsorted list:\n    ";for(int n : fl) std::cout << n << ' ';std::cout << '\n';  quicksort(std::begin(fl), std::end(fl));std::cout << "Sorted using quicksort:\n    ";for(int fi : fl) std::cout << fi << ' ';std::cout << '\n';
}

Output:

Original vector:0 1 2 3 4 5 6 7 8 9 
Partitioned vector:0 8 2 6 4  *  5 3 7 1 9 
Unsorted list:1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 
Sorted using quicksort:-8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92

三、partition_copy

1、原型：

template< class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate >
std::pair<OutputIt1, OutputIt2>partition_copy( InputIt first, InputIt last,OutputIt1 d_first_true, OutputIt2 d_first_false,UnaryPredicate p );

2、说明：

将指定范围内的元素安特定条件分成两组，分别复制到d_first_true、d_first_false中。

3、官方demo

#include <iostream>
#include <algorithm>
#include <utility>int main()
{int arr [10] = {1,2,3,4,5,6,7,8,9,10};int true_arr [5] = {0};int false_arr [5] = {0};std::partition_copy(std::begin(arr), std::end(arr), std::begin(true_arr),std::begin(false_arr),[] (int i) {return i > 5;});std::cout << "true_arr: ";for (int x : true_arr) {std::cout << x << ' ';}std::cout << '\n'; std::cout << "false_arr: ";for (int x : false_arr) {std::cout << x << ' ';}std::cout << '\n'; return 0;}

Output:

true_arr: 6 7 8 9 10
false_arr: 1 2 3 4 5

四、stable_partition

1、原型：

template< class BidirIt, class UnaryPredicate >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );

2、说明：

将元素分为两组，同时保持它们的相对顺序

3、官方demo

#include <iostream>
#include <algorithm>
#include <vector>int main()
{std::vector<int> v{0, 0, 3, 0, 2, 4, 5, 0, 7};std::stable_partition(v.begin(), v.end(), [](int n){return n>0;});for (int n : v) {std::cout << n << ' ';}std::cout << '\n';
}

Output:

3 2 4 5 7 0 0 0 0

五、partition_point

1、原型；

template< class ForwardIt, class UnaryPredicate >
ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p );

2、说明：

返回已经分隔好的分割点的位置（迭代器）

3、官方demo

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>int main()
{std::array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };auto is_even = [](int i){ return i % 2 == 0; };std::partition(v.begin(), v.end(), is_even);auto p = std::partition_point(v.begin(), v.end(), is_even);std::cout << "Before partition:\n    ";std::copy(v.begin(), p, std::ostream_iterator<int>(std::cout, " "));std::cout << "\nAfter partition:\n    ";std::copy(p, v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Output:
Before partition:
8 2 6 4
After partition:
5 3 7 1 9

排序操作（Sorting operations）

一、is_sorted

1、原型：

template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

2、说明：

判断指定范围内的元素是否按照升序排列

3、官方demo

#include <iostream>
#include <algorithm>
#include <iterator>
int main() 
{int digits[] = {3, 1, 4, 1, 5};for (auto i : digits) std::cout << i << ' ';std::cout << ": is_sorted: " << std::boolalpha<< std::is_sorted(std::begin(digits), std::end(digits)) << '\n';std::sort(std::begin(digits), std::end(digits));for (auto i : digits) std::cout << i << ' ';std::cout << ": is_sorted: "<< std::is_sorted(std::begin(digits), std::end(digits)) << '\n';
}

Output:
3 1 4 1 5 : is_sorted: false
1 1 3 4 5 : is_sorted: true

二、is_sorted_until

1、原型：

template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );

2、说明：

从first找到已经排序的位置（迭代器）

3、官方demo

#include <iostream>
#include <algorithm>
#include <iterator>
#include <random>int main()
{std::random_device rd;std::mt19937 g(rd());const int N = 6;int nums[N] = {3, 1, 4, 1, 5, 9};const int min_sorted_size = 4;int sorted_size = 0;do {std::shuffle(nums, nums + N, g);int *sorted_end = std::is_sorted_until(nums, nums + N);sorted_size = std::distance(nums, sorted_end);for (auto i : nums) std::cout << i << ' ';std::cout << " : " << sorted_size << " initial sorted elements\n";} while (sorted_size < min_sorted_size);
}

Possible output:

4 1 9 5 1 3  : 1 initial sorted elements
4 5 9 3 1 1  : 3 initial sorted elements
9 3 1 4 5 1  : 1 initial sorted elements
1 3 5 4 1 9  : 3 initial sorted elements
5 9 1 1 3 4  : 2 initial sorted elements
4 9 1 5 1 3  : 2 initial sorted elements
1 1 4 9 5 3  : 4 initial sorted elements

三、sort

1、原型：

template< class RandomIt >
void sort( RandomIt first, RandomIt last );template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

2、说明：

升序排列
注意：
相等元素的顺序不能保证被保留。

3、官方demo

#include <algorithm>
#include <functional>
#include <array>
#include <iostream>int main()
{std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; // 使用默认操作符排序std::sort(s.begin(), s.end());for (auto a : s) {std::cout << a << " ";}   std::cout << '\n';// 使用标准库比较函数对象排序std::sort(s.begin(), s.end(), std::greater<int>());for (auto a : s) {std::cout << a << " ";}   std::cout << '\n';// 使用自定义函数对象排序struct {bool operator()(int a, int b) const{   return a < b;}   } customLess;std::sort(s.begin(), s.end(), customLess);for (auto a : s) {std::cout << a << " ";}   std::cout << '\n';// 使用lambda表达式排序 std::sort(s.begin(), s.end(), [](int a, int b) {return a > b;   });for (auto a : s) {std::cout << a << " ";} std::cout << '\n';
}

Output:

0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0

四、partial_sort

1、原型：

template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );

2、说明：

在[first, last)范围内找到前middle-first个最小的元素并排序。后面的元素不保证顺序。
注意：
相等元素的顺序不能保证被保留。

3、官方demo

#include <algorithm>
#include <functional>
#include <array>
#include <iostream>int main()
{std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};std::partial_sort(s.begin(), s.begin() + 3, s.end());for (int a : s) {std::cout << a << " ";} 
}

Possible output:

0 1 2 7 8 6 5 9 4 3

五、partial_sort_copy

1、原型：

template< class InputIt, class RandomIt >
RandomIt partial_sort_copy( InputIt first, InputIt last,RandomIt d_first, RandomIt d_last );template< class InputIt, class RandomIt, class Compare >
RandomIt partial_sort_copy( InputIt first, InputIt last,RandomIt d_first, RandomIt d_last,Compare comp );

2、说明：

将最多d_last-d_first个元素排列处理。保存到d_first开始的范围内

3、官方demo

#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';
}

Output:

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

六、stable_sort

1、原型：

template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );

2、说明：

升序排列，同时保存相等的元素按原来顺序排列。

3、官方demo

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>struct Employee
{int age;std::string name;  // Does not participate in comparisons
};bool operator<(const Employee & lhs, const Employee & rhs)
{return lhs.age < rhs.age;
}int main()
{std::vector<Employee> v ={ {108, "Zaphod"},{32, "Arthur"},{108, "Ford"},};  std::stable_sort(v.begin(), v.end());for (const Employee & e : v)std::cout << e.age << ", " << e.name << '\n';
}

Output:

32, Arthur
108, Zaphod
108, Ford

七、nth_element

1、原型：

template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,Compare comp );

2、说明：

nth之前的元素全都小于nth之后的元素，但是这两部分没有排序

3、官方demo

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>int main()
{std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());for (auto a : v) {std::cout << a << " ";}   std::cout << "The median is " << v[v.size()/2] << '\n';std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());std::cout << "The second largest element is " << v[1] << '\n';
}

Output:

The median is 5
The second largest element is 7