直接合并


类别：算法	组件类型：函数

原型

直接合并是一个重载名称：实际上有两个函数。直接合并说明

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

template <class BidirectionalIterator, class StrictWeakOrdering>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last, StrictWeakOrdering comp);

合并两个连续的已排序范围

直接合并[first, middle)和[middle, last)到一个单个已排序范围[first, last)。这也就是说，它从一个范围开始该范围由两部分组成，每部分处于升序中，并对其重新排序以使整个范围处于升序中。。这也就是说，它从一个范围开始是稳定的，这意味着在每个输入范围中元素的相对顺序被保留，以及对于两个输入范围中的等效元素 [1]，来自第一个范围的元素位于来自第二个范围的元素之前。直接合并两个版本的

在元素如何进行比较方面不同。第一个版本使用直接合并运算符<。也就是说，输入范围和输出范围满足以下条件：对于每个迭代器对ij[middle, last)如此位于j*j < *i如此, 之前为false。第二个版本使用函数对象ij[middle, last)如此位于j*j < *i如此, comp为false.

comp(j, i)

定义

在 algo.h 中定义。

对类型要求

对于第一个版本双向迭代器
对于第一个版本是双向迭代器的模型。
对于第一个版本是可变的。
的值类型是小于可比较类型的模型。对于第一个版本对

的值类型的对象的排序是严格部分有序，如小于可比较类型要求中定义。

对于第一个版本双向迭代器
对于第一个版本是双向迭代器的模型。
对于第二个版本严格弱有序
对于第一个版本是严格弱排序的模型。对于第二个版本的值类型可转换为

的自变量类型。

对类型要求

和前提条件
到一个单个已排序范围前提条件
和是一个有效的范围。j[middle, last)如此处于升序中。也就是说，对于每个迭代器对和位于j*j < *i如此, 之前为false.
到一个单个已排序范围是一个有效的范围。j[middle, last)如此处于升序中。也就是说，对于每个迭代器对到一个单个已排序范围位于j*j < *i如此, 之前为false.

的值类型的对象的排序是严格部分有序，如小于可比较类型要求中定义。

和前提条件
到一个单个已排序范围前提条件
和是一个有效的范围。j[middle, last)如此处于升序中。也就是说，对于每个迭代器对和位于j*j < *i如此, comp为false.
到一个单个已排序范围是一个有效的范围。j[middle, last)如此处于升序中。也就是说，对于每个迭代器对到一个单个已排序范围位于j*j < *i如此, comp为false.

中

直接合并复杂度直接合并是一个自适应算法：它尝试分配一个临时内存缓冲区，其运行时复杂度取决于可用的内存数量。。这也就是说，它从一个范围开始如果没有是一个空范围，则执行所有比较。否则，最坏的情况行为（如果无法使用辅助内存）为O(N log(N))其中为Nlast - first，且最佳情况（如果可以通过足够大的辅助内存缓冲区）最多为(last - first) - 1

比较。

int main()
{
  int A[] = { 1, 3, 5, 7, 2, 4, 6, 8 };

  inplace_merge(A, A + 4, A + 8);
  copy(A, A + 8, ostream_iterator<int>(cout, " "));  
  // The output is "1 2 3 4 5 6 7 8".
}

示例

备注[1] 请注意，你可以使用严格弱排序但不使用全排序，也就是说可能存在值[middle, last)x位于y, x < yx > y，且x == y[1] 请注意，你可以使用严格弱排序但不使用全排序，也就是说可能存在值[middle, last)x都为 false。（请参阅小于可比较类型要求，了解更全面的讨论。）如果既不是y也不是y < x. 但是，如果您正在使用总序（例如，如果您正在使用strcmp，或如果您正在对整数使用普通的算术比较），那么您可以忽略此技术区别：对于总序，相等性和等价性是相同的。

另请参阅

合并, 集合并集, 排序