std::inplace_merge
定义于头文件 <algorithm> |
||
template< class BidirIt > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ); |
(1) | (C++26 起为 constexpr) |
template< class ExecutionPolicy, class BidirIt > void inplace_merge( ExecutionPolicy&& policy, |
(2) | (C++17 起) |
template< class BidirIt, class Compare > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, |
(3) | (C++26 起为 constexpr) |
template< class ExecutionPolicy, class BidirIt, class Compare > void inplace_merge( ExecutionPolicy&& policy, |
(4) | (C++17 起) |
将两个连续的有序范围 [
first,
middle)
和 [
middle,
last)
合并成一个有序范围 [
first,
last)
。
[
first,
middle)
或 [
middle,
last)
没有按照 comp 排序,则行为未定义。
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true。 |
(C++20 前) |
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true。 |
(C++20 起) |
此合并函数是稳定的,这意味着对于原始两个范围中的等价元素,来自第一个范围的元素(保留其原始顺序)排在来自第二个范围的元素(保留其原始顺序)之前。
如果满足以下任何条件,则行为是未定义的:
-
[
first,
middle)
或[
middle,
last)
不是 有效范围。
|
(C++11 前) |
|
(C++11 起) |
目录 |
[编辑] 参数
first | - | 第一个有序范围的起始迭代器 |
middle | - | 第一个有序范围的结束迭代器,也是第二个有序范围的起始迭代器 |
last | - | 第二个有序范围的结束迭代器 |
policy | - | 要使用的 执行策略 |
comp | - | 比较函数对象(即满足 Compare 要求的对象),当第一个参数“小于”(即“排在”第二个参数之前)第二个参数时返回 true。 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 尽管函数签名不必带有 const&,但该函数不得修改传递给它的对象,并且必须能够接受 |
类型要求 | ||
-BidirIt 必须满足 LegacyBidirectionalIterator 的要求。 | ||
-Compare 必须满足 Compare 的要求。 |
[编辑] 复杂度
给定 N 作为 std::distance(first, last)
[编辑] 异常
带有模板参数 ExecutionPolicy
的重载按如下方式报告错误
- 如果作为算法一部分调用的函数执行抛出异常,并且
ExecutionPolicy
是标准策略之一,则调用 std::terminate。对于任何其他ExecutionPolicy
,行为是实现定义的。 - 如果算法未能分配内存,则抛出 std::bad_alloc。
[编辑] 可能实现
[编辑] 注记
此函数尝试分配临时缓冲区。如果分配失败,则选择效率较低的算法。
特性测试宏 | 值 | 标准 | 特性 |
---|---|---|---|
__cpp_lib_constexpr_algorithms |
202306L |
(C++26) | constexpr 原地合并 (1), (3) |
[编辑] 示例
以下代码是归并排序的一种实现。
#include <algorithm> #include <iostream> #include <vector> 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 (const auto& n : v) std::cout << n << ' '; std::cout << '\n'; }
输出
-2 0 1 2 3 7 8 11 11
[编辑] 参阅
归并两个已排序的范围 (函数模板) | |
将一个范围按升序排序 (函数模板) | |
对一个范围的元素进行排序,同时保留相等元素之间的顺序 (函数模板) | |
(C++20) |
就地归并两个有序范围 (算法函数对象) |