本文共 12026 字，大约阅读时间需要 40 分钟。
分隔操作（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 #include #include int main(){ std::array 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 #include #include #include #include template 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 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 (std::cout, " ")); std::cout << " * "; std::copy(it, std::end(v), std::ostream_iterator (std::cout, " ")); std::forward_list 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 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 #include #include 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 10false_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 #include #include int main(){ std::vector 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 #include #include #include int main(){ std::array 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 (std::cout, " ")); std::cout << "\nAfter partition:\n "; std::copy(p, v.end(), std::ostream_iterator (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 #include #include 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 #include #include #include 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 elements4 5 9 3 1 1 : 3 initial sorted elements9 3 1 4 5 1 : 1 initial sorted elements1 3 5 4 1 9 : 3 initial sorted elements5 9 1 1 3 4 : 2 initial sorted elements4 9 1 5 1 3 : 2 initial sorted elements1 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 #include #include #include int main(){ std::array 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 ()); 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 #include #include #include int main(){ std::array 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 #include #include #include int main(){ std::vector v0{ 4, 2, 5, 1, 3}; std::vector v1{ 10, 11, 12}; std::vector v2{ 10, 11, 12, 13, 14, 15, 16}; std::vector ::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 ()); 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 3The return value is the end iteratorWriting to the larger vector in descending order gives: 5 4 3 2 1 15 16The 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 #include #include #include 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 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, Arthur108, Zaphod108, 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 #include #include #include int main(){ std::vector 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 ()); std::cout << "The second largest element is " << v[1] << '\n';}
Output:
The median is 5The second largest element is 7
转载地址：http://rbmei.baihongyu.com/