std::inplace_merge
Defined in header <algorithm> | ? | ? |
|---|---|---|
template< class BidirIt > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ); | (1) | ? |
template< class ExecutionPolicy, class BidirIt > void inplace_merge( ExecutionPolicy&& policy, BidirIt first, BidirIt middle, BidirIt last ); | (2) | (since C++17) |
template< class BidirIt, class Compare> void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp ); | (3) | ? |
template< class ExecutionPolicy, class BidirIt, class Compare> void inplace_merge( ExecutionPolicy&& policy, BidirIt first, BidirIt middle, BidirIt last, Compare comp ); | (4) | (since C++17) |
合并两个连续排序范围[first, middle)和[middle, last)进入一个排序范围[first, last)对于原始两个范围中的等效元素，第一个范围%28中的元素保留其原始顺序%29，而来自第二个范围的元素%28保留其原始顺序%29。
1%29个元素的比较operator<范围必须按照相同的顺序排序。
使用给定的二进制比较函数对3%29个元素进行比较。comp范围必须按照相同的顺序排序。
2，4%29与%281，3%29相同，但根据policy这些过载不参与过载解决，除非std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>是真的
参数
first | - | the beginning of the first sorted range |
|---|---|---|
middle | - | the end of the first sorted range and the beginning of the second |
last | - | the end of the second sorted range |
policy | - | the execution policy to use. See execution policy for details. |
comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ?true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function object must not modify the objects passed to it. The types Type1 and Type2 must be such that an object of type BidirIt can be dereferenced and then implicitly converted to both of them. ? |
类型要求
-取消引用的Bidirit必须符合可移动和可移动的要求。
返回值
%280%29
复杂性
给出N =std::distance(first, last)}
1，3%29N-1比较是否有足够的额外内存可用。如果内存不足，O(N log N)比较。
2，4%29O(N log N)比较。
例外
带有名为ExecutionPolicy报告错误如下：
- 如果执行作为算法一部分调用的函数，则引发异常
ExecutionPolicy是其中之一标准政策，，，std::terminate叫做。对于任何其他人ExecutionPolicy，行为是由实现定义的。
- 如果算法不能分配内存，
std::bad_alloc被扔了。
注记
此函数尝试分配临时缓冲区。如果分配失败，则选择效率较低的算法。
例
以下代码是合并排序的实现。
二次
#include <vector>
#include <iostream>
#include <algorithm>
template<class Iter>
void merge_sort(Iter first, Iter last)
{
if (last - first > 1) {
Iter middle = first + (last - first) / 2;
merge_sort(first, middle);
merge_sort(middle, last);
std::inplace_merge(first, middle, last);
}
}
int main()
{
std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
merge_sort(v.begin(), v.end());
for(auto n : v) {
std::cout << n << ' ';
}
std::cout << '\n';
}二次
产出：
二次
-2 0 1 2 3 7 8 11 11二次
另见
merge | merges two sorted ranges (function template) |
|---|---|
sort | sorts a range into ascending order (function template) |
stable_sort | sorts a range of elements while preserving order between equal elements (function template) |
? cppreference.com在CreativeCommonsAttribution下授权-ShareAlike未移植许可v3.0。
本文档系腾讯云开发者社区成员共同维护，如有问题请联系 cloudcommunity@tencent.com
