合并算法

合并算法的实现 更多...

合并算法 的协作图:

函数
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Compare>
constexpr Iterator3	merge (Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Iterator3 result, Compare comp)
	合并两个已排序序列
template<typename Iterator1, typename Iterator2, typename Iterator3>
constexpr Iterator3	merge (Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Iterator3 result)
	合并两个已排序序列
template<typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void	inplace_merge (Iterator first, Iterator middle, Iterator last, Compare comp)
	原地合并两个已排序的连续范围
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	inplace_merge (Iterator first, Iterator middle, Iterator last)
	原地合并两个已排序的连续范围

详细描述

合并算法的实现

函数说明

inplace_merge() [1/2]

template<typename Iterator>

NEFORCE_CONSTEXPR20 void inplace_merge	(	Iterator	first,
		Iterator	middle,
		Iterator	last )

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

模板参数

Iterator

迭代器类型

参数

first	范围起始
middle	范围中间分割点
last	范围结束

在文件 merge.hpp 第 293 行定义.

引用了 inplace_merge().

inplace_merge() [2/2]

template<typename Iterator, typename Compare>

NEFORCE_CONSTEXPR20 void inplace_merge	(	Iterator	first,
		Iterator	middle,
		Iterator	last,
		Compare	comp )

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

模板参数

Iterator	迭代器类型
Compare	比较函数类型

参数

first	范围起始
middle	范围中间分割点
last	范围结束
comp	比较函数对象

将两个已排序的连续子范围 [first, middle) 和 [middle, last) 原地合并， 使得整个范围 [first, last) 成为有序的。

算法尝试分配临时缓冲区以提高性能，如果分配失败则使用无缓冲区的算法。

在文件 merge.hpp 第 269 行定义.

引用了 temporary_buffer< Iterator >::begin(), distance(), is_ranges_bid_iter_v , 以及 temporary_buffer< Iterator >::size().

被这些函数引用 inplace_merge(), merge_sort() , 以及 tim_sort().

merge() [1/2]

template<typename Iterator1, typename Iterator2, typename Iterator3>

Iterator3 merge ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Iterator3 result )

constexpr

合并两个已排序序列

模板参数

Iterator1	第一个输入迭代器类型
Iterator2	第二个输入迭代器类型
Iterator3	输出迭代器类型

参数

first1	第一个范围起始
last1	第一个范围结束
first2	第二个范围起始
last2	第二个范围结束
result	输出范围起始

返回

输出范围结束迭代器

在文件 merge.hpp 第 81 行定义.

引用了 merge().

merge() [2/2]

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Compare>

Iterator3 merge ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Iterator3 result, Compare comp )

constexpr

合并两个已排序序列

模板参数

Iterator1	第一个输入迭代器类型
Iterator2	第二个输入迭代器类型
Iterator3	输出迭代器类型
Compare	比较函数类型

参数

first1	第一个范围起始
last1	第一个范围结束
first2	第二个范围起始
last2	第二个范围结束
result	输出范围起始
comp	比较函数对象

返回

输出范围结束迭代器

将两个已排序的范围 [first1, last1) 和 [first2, last2) 合并到以 result 开始的范围。 结果范围包含来自两个输入范围的所有元素，并保持排序顺序。

前提条件：

1. 两个输入范围都已按照 comp 排序
2. 输出范围不与任一输入范围重叠
3. 输出范围有足够的空间容纳所有元素

在文件 merge.hpp 第 50 行定义.

引用了 copy() , 以及 is_ranges_fwd_iter_v.

被这些函数引用 merge().