std::ranges::mergestd::mergestd::inplace_merge

std::ranges::merge 

是 C++20 引入的算法，用于将两个已排序的范围合并为一个有序序列。

基本功能 输入：两个已排序的范围（升序或降序，需一致）。输出：将两个范围合并后的结果写入目标范围，保持有序。稳定性：相等元素的相对顺序会被保留（稳定合并）。

Defined in header <algorithm>

Call signature

template< std::input_iterator I1, std::sentinel_for<I1> S1,

          std::input_iterator I2, std::sentinel_for<I2> S2,           std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr merge_result<I1, I2, O>     merge( I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},

           Proj1 proj1 = {}, Proj2 proj2 = {} );(1)(since C++20)template< ranges::input_range R1, ranges::input_range R2,

          std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,                         O, Comp, Proj1, Proj2> constexpr merge_result<ranges::borrowed_iterator_t<R1>,                        ranges::borrowed_iterator_t<R2>, O>     merge( R1&& r1, R2&& r2, O result, Comp comp = {},

           Proj1 proj1 = {}, Proj2 proj2 = {} ); 参数： first1, last1：第一个输入范围的起止迭代器。first2, last2：第二个输入范围的起止迭代器。result：目标范围的起始迭代器。comp：比较函数（默认为 std::ranges::less）。proj1, proj2：对输入元素的投影（默认为恒等投影 std::identity）。

---

示例代码 #include <algorithm> #include <vector> #include <iostream> #include <iterator> int main() { std::vector<int> v1 = {1, 3, 5, 7}; std::vector<int> v2 = {2, 4, 6, 8}; std::vector<int> result; // 确保目标容器有足够空间 result.resize(v1.size() + v2.size()); // 合并 v1 和 v2 到 result std::ranges::merge(v1, v2, result.begin()); // 输出结果 for (int x : result) { std::cout << x << " "; } // 输出：1 2 3 4 5 6 7 8 }

 详细说明

输入范围必须有序：

若输入未排序，结果可能无序。排序方向需一致（均升序或均降序）。

目标空间要求：

目标范围必须有足够空间容纳 size(v1) + size(v2) 个元素。可使用 resize() 或预先分配空间。

自定义比较和投影：

支持自定义比较函数（如降序合并）。投影允许对元素进行变换后再比较。 std::merge

用于将两个已排序的范围合并为一个新的已排序范围。它不会修改输入范围，而是将结果存储到另一个范围中。

Defined in header <algorithm>

template< class InputIt1, class InputIt2, class OutputIt >

OutputIt merge( InputIt1 first1, InputIt1 last1,                 InputIt2 first2, InputIt2 last2,

                OutputIt d_first );(1)(constexpr since C++20)template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy,                   ForwardIt1 first1, ForwardIt1 last1,                   ForwardIt2 first2, ForwardIt2 last2,

                  ForwardIt3 d_first );(2)(since C++17)template< class InputIt1, class InputIt2,

          class OutputIt, class Compare > OutputIt merge( InputIt1 first1, InputIt1 last1,                 InputIt2 first2, InputIt2 last2,

                OutputIt d_first, Compare comp );(3)(constexpr since C++20)template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2,           class ForwardIt3, class Compare > ForwardIt3 merge( ExecutionPolicy&& policy,                   ForwardIt1 first1, ForwardIt1 last1,                   ForwardIt2 first2, ForwardIt2 last2,

                  ForwardIt3 d_first, Compare comp );

 

参数说明

first1, last1: 第一个输入范围的起始和结束迭代器。

first2, last2: 第二个输入范围的起始和结束迭代器。

d_first: 目标范围的起始迭代器，用于存储合并后的结果。

comp: 可选的比较函数对象，用于定义元素的顺序。默认是 std::less。

返回值

返回目标范围的结束迭代器，指向最后一个写入元素的下一个位置。

---

示例 1：基本用法

以下是一个简单的示例，展示如何使用 std::merge 将两个已排序的数组合并为一个新的已排序数组。

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = {1, 3, 5, 7}; // 已排序 std::vector<int> v2 = {2, 4, 6, 8}; // 已排序 std::vector<int> result(v1.size() + v2.size()); // 目标范围 // 合并 v1 和 v2 到 result std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin()); // 输出结果 std::cout << "Merged result: "; for (int i : result) { std::cout << i << " "; } std::cout << "\n"; return 0; }

输出

Merged result: 1 2 3 4 5 6 7 8 示例 2：使用自定义比较函数

std::merge 允许你提供一个自定义的比较函数来控制排序的顺序。例如，如果你想按降序合并两个已排序的范围。

排序方式需与 comp 一致

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = {7, 5, 3, 1}; // 已排序（降序） std::vector<int> v2 = {8, 6, 4, 2}; // 已排序（降序） std::vector<int> result(v1.size() + v2.size()); // 目标范围 // 合并 v1 和 v2 到 result，按降序排列 std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin(), std::greater<int>()); // 输出结果 std::cout << "Merged result (descending): "; for (int i : result) { std::cout << i << " "; } std::cout << "\n"; return 0; }

输出

Merged result (descending): 8 7 6 5 4 3 2 1

解释

v1 和 v2 是两个已按降序排序的向量。

std::merge 使用 std::greater<int> 作为比较函数，将两个向量合并为一个新的降序排序的向量 result。

示例 4：合并到原始范围

如果你希望使用 std::merge将结果直接存储到原始范围中，可以先将结果存储到一个临时范围，然后再复制回原始范围。

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = {1, 3, 5, 7}; // 已排序 std::vector<int> v2 = {2, 4, 6, 8}; // 已排序 std::vector<int> result(v1.size() + v2.size()); // 目标范围 // 合并 v1 和 v2 到 result std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin()); // 将结果复制回 v1 v1 = result; // 输出结果 std::cout << "Merged result in v1: "; for (int i : v1) { std::cout << i << " "; } std::cout << "\n"; return 0; } 输出

复制

Merged result in v1: 1 2 3 4 5 6 7 8 解释

std::merge 将 v1 和 v2 合并到 result。

然后将 result 复制回 v1，使 v1 包含合并后的结果。

下列这几个容器在C++17时加入了自己的merge接口:

std::map std::set std::multimap std::multiset std::unordered_map std::unordered_set std::unordered_multimap std::unordered_multiset

std::vector 和 std::array是没有merge的，需要通过std::merge库函数来merge。

如果你希望将结果直接存储到原始范围中，可以使用 std::inplace_merge。

std::inplace_merge

用于将两个已排序的连续序列合并为一个有序序列，且合并过程直接在原序列中进行（不额外分配内存）。它通常用于归并排序的实现。

Defined in header <algorithm>

template< class BidirIt > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

(1)(constexpr since C++26)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)(constexpr since C++26)template< class ExecutionPolicy, class BidirIt, class Compare >

void inplace_merge( ExecutionPolicy&& policy,                     BidirIt first, BidirIt middle, BidirIt last,

                    Compare comp ); 参数： first：第一个有序序列的起始迭代器。middle：第一个有序序列的结束位置，同时也是第二个有序序列的起始位置。last：第二个有序序列的结束位置。comp：自定义比较函数（可选，默认使用 < 运算符）。 关键点 前提条件： [first, middle) 和 [middle, last) 必须是已排序的序列。排序方式需与 comp 一致（若提供）。 时间复杂度： 如果额外内存足够，复杂度为 O(N)（N 为元素总数）。否则为 O(N log N)。 原地操作：合并后的结果直接存储在 [first, last) 中。

 

示例 示例 1：合并两个有序子数组 #include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> v = {1, 3, 5, 2, 4, 6}; // 前3个和后3个已分别排序 std::inplace_merge(v.begin(), v.begin() + 3, v.end()); for (int x : v) { std::cout << x << " "; } }

输出：

1 2 3 4 5 6

示例 2：自定义比较函数 #include <algorithm> #include <vector> #include <iostream> bool compare(int a, int b) { return a > b; // 降序排序 } int main() { std::vector<int> v = {5, 3, 1, 6, 4, 2}; // 前3个和后3个已按降序排序 std::inplace_merge(v.begin(), v.begin() + 3, v.end(), compare); for (int x : v) { std::cout << x << " "; } // 输出：6 5 4 3 2 1 } 应用场景 归并排序：在递归合并步骤中使用 std::inplace_merge。合并相邻有序区间：例如处理分段排序后的数据。 注意事项 确保输入区间已按指定顺序排序。若对性能要求高，需关注内存分配的影响（尽量保证有足够内存）。 std::ranges::inplace_merge