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, BidirIt first, BidirIt middle, BidirIt last );	(2)	(C++17 起)
template< class BidirIt, class Compare > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );	(3)	(C++26 起為 constexpr)
template< class ExecutionPolicy, class BidirIt, class Compare > void inplace_merge( ExecutionPolicy&& policy, BidirIt first, BidirIt middle, BidirIt last, Compare comp );	(4)	(C++17 起)

將兩個連續的有序範圍 [first, middle) 和 [middle, last) 合併成一個有序範圍 [first, last)。

1) 如果 [first, middle) 或 [middle, last) 沒有按照 operator<(C++20 前)std::less{}(C++20 起) 排序，則行為未定義。

3) 如果 [first, middle) 或 [middle, last) 沒有按照 comp 排序，則行為未定義。

2,4) 同 (1,3)，但按 policy 執行。

僅當滿足所有以下條件時，這些過載才參與過載決議

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) 不是有效範圍。

*first 的型別不可 Swappable。	(C++11 前)
`BiditIt` 不可 ValueSwappable。 first 的型別不可 MoveConstructible。 first 的型別不可 MoveAssignable。	(C++11 起)

first	-	第一個有序範圍的起始迭代器
middle	-	第一個有序範圍的結束迭代器，也是第二個有序範圍的起始迭代器
last	-	第二個有序範圍的結束迭代器
policy	-	要使用的執行策略
comp	-	比較函式物件（即滿足 Compare 要求的物件），當第一個引數“小於”（即“排在”第二個引數之前）第二個引數時返回 true。比較函式的簽名應等效於以下內容 bool cmp(const Type1& a, const Type2& b); 儘管函式簽名不必帶有 const&，但該函式不得修改傳遞給它的物件，並且必須能夠接受 `Type1` 和 `Type2` 型別的所有（可能是 const 的）值，無論其值類別如何（因此，不允許 `Type1&`，也不允許 `Type1`，除非 `Type1` 的移動等效於複製(C++11 起)）。型別 Type1 和 Type2 必須使得型別 BidirIt 的物件可以被解引用，然後隱式轉換為這兩種型別。
型別要求
- `BidirIt` 必須滿足 LegacyBidirectionalIterator 的要求。
- `Compare` 必須滿足 Compare 的要求。

[編輯] 複雜度

給定 $\scriptsize N$ $N$ 作為 std::distance(first, last)

1) 如果有足夠的額外記憶體可用，則使用 operator<(C++20 前)std::less{}(C++20 起) 進行

N-1

次精確比較；否則進行

O(N\cdotlog(N))

次比較。

2) 使用 operator<(C++20 前)std::less{}(C++20 起) 進行

O(N\cdotlog(N))

次比較。

3) 如果有足夠的額外記憶體可用，則 comp 比較函式的精確應用次數為

N-1

；否則為

O(N\cdotlog(N))

次應用。

4) comp 比較函式的應用次數為

O(N\cdotlog(N))

。

[編輯] 異常

帶有模板引數 ExecutionPolicy 的過載按如下方式報告錯誤

如果作為演算法一部分呼叫的函式執行丟擲異常，並且 ExecutionPolicy 是標準策略之一，則呼叫 std::terminate。對於任何其他 ExecutionPolicy，行為是實現定義的。
如果演算法未能分配記憶體，則丟擲 std::bad_alloc。

[編輯] 可能實現

參見 libstdc++ 和 libc++ 中的實現。

[編輯] 註記

此函式嘗試分配臨時緩衝區。如果分配失敗，則選擇效率較低的演算法。

特性測試宏	值	標準	特性
`__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

[編輯] 參閱

merge	歸併兩個已排序的範圍 (函式模板) [編輯]
sort	將一個範圍按升序排序 (函式模板) [編輯]
stable_sort	對一個範圍的元素進行排序，同時保留相等元素之間的順序 (函式模板) [編輯]
ranges::inplace_merge (C++20)	就地歸併兩個有序範圍 (演算法函式物件)[編輯]

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作