C++ 算法 inplace_merge()

C++ 算法 inplace_merge() 函数用于将两个连续的已排序范围 [first, middle) 和 [middle, last) 合并成一个已排序的范围 [first, last)。

对于第一个版本，使用运算符 < 比较元素，或者对于第二个版本，使用给定的二元比较函数 comp 比较元素。

语法

参数

first: 一个双向迭代器，指向要合并并排序成单个范围的两个连续已排序范围中第一个范围的第一个元素。

last: 一个双向迭代器，指向要合并并排序成单个范围的两个连续已排序范围中第二个范围的最后一个元素的后一个位置。

middle: 一个双向迭代器，指向要合并并排序成单个范围的两个连续已排序范围中第二个范围的第一个元素的位置。

comp: 用户定义的二元谓词函数，接受两个参数，如果这两个参数有序则返回 true，否则返回 false。它遵循严格弱序来排序元素。

返回值

无

复杂度

如果提供足够的额外内存，则复杂性与 first 和 last 之间的距离呈线性关系：执行 N-1 次比较，以及最多两倍的元素移动。

否则，复杂性为对数线性：执行最多 N*log(N) 次元素比较，其中 N = last - first，以及最多相同次数的元素交换。

数据竞争

范围 [first, last) 中的对象被修改。

异常

如果任何元素比较、元素交换（或移动）或迭代器操作抛出异常，则此函数会抛出异常。

注意：无效参数会导致未定义行为。

示例 1

让我们看一个简单的例子来演示 inplace_merge() 的用法

输出

Vector v1 :  5 10 15 20 25
Vector v2 :  10 20 30 40 50
Vector v3 :  5 10 10 15 20 20 25 30 40 50

示例 2

让我们看另一个简单示例

输出

The resulting vector contains: 5 10 10 15 20 20 25 30 40 50

示例 3

让我们再看一个简单的例子来演示使用运算符 < 的 inplace_merge() 的用法

输出

1
2
3
4
5

示例 4

让我们看一个简单的例子来演示使用比较函数的 inplace_merge() 的用法

输出

5
4
3
2
1

示例 5

让我们看另一个简单示例

输出

-9 0 1 2 3 4 7 9 10