inplace_merge-c和c++中文资料站

C&C++标准库

std::

inplace_merge

函数模板 <algorithm>

default (1)

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

custom (2)

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

合并连续排序范围

合并两个连续的排序范围:[first,middle)和[middle,last)，将结果放入合并后的排序范围[first,last)。

第一个版本使用操作符<比较元素，第二个版本使用comp操作符比较元素。两个范围内的元素应该已经按照相同的标准排序(操作符<或comp)。得到的范围也是根据这个排序的。

该函数保留具有相同值的元素的相对顺序，第一个范围内的元素在第二个范围内的相同元素之前。

☲ 参数

first: 指向第一个已排序序列要合并的初始位置的双向迭代器。这也是存储合并后的范围的初始位置。
middle: 指向第二个排序序列初始位置的双向迭代器，由于两个序列必须是连续的，因此匹配第一个序列的结束后位置。
last: 指向第二个已排序序列的结束位置的双向迭代器。这也是存储合并后的范围的后端位置。
comp: 二元函数，接受两个由迭代器指向的类型参数，并返回一个可转换为bool类型的值。返回的值表示在它定义的特定严格弱排序中，第一个参数是否被认为在第二个参数之前。。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。

双向迭代器(BidirectionalIterator)应指向一个类型，该类型的swap已正确定义，且既可移动构造又可移动赋值。

☉ 返回值

none

☣ 示例

// inplace_merge example
#include <iostream>     // std::cout
#include <algorithm>    // std::inplace_merge, std::sort, std::copy
#include <vector>       // std::vector

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);
  std::vector<int>::iterator it;

  std::sort (first,first+5);
  std::sort (second,second+5);

  it=std::copy (first, first+5, v.begin());
     std::copy (second,second+5,it);

  std::inplace_merge (v.begin(),v.begin()+5,v.end());

  std::cout << "The resulting vector contains:";
  for (it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

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

✥ 复杂度

如果有足够的额外内存可用，则first 和 last之间的距离为线性: 执行N-1次比较，并进行最多两倍的元素移动。
否则，可达线性:执行最多N*log(N)的元素比较(其中N是上面的距离)，以及那么多元素交换。

⇄ 数据竞争

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

☂ 异常安全性

如果任何元素比较，元素交换(或move)或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。

🍄 另请参阅

merge	合并已排序的范围(函数模板)
partition	获取分区点(函数模板)
includes	测试已排序范围是否包含另一个已排序范围(函数模板)