合并算法

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

函数
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Compare, enable_if_t< is_ranges_fwd_iter_v< Iterator1 > &&is_ranges_fwd_iter_v< Iterator2 > &&is_ranges_fwd_iter_v< Iterator3 >, int > = 0>
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, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>
constexpr void	inplace_merge (Iterator first, Iterator middle, Iterator last, Compare comp)
	原地合并两个已排序的连续范围
template<typename Iterator>
constexpr void	inplace_merge (Iterator first, Iterator middle, Iterator last)
	原地合并两个已排序的连续范围

详细描述

MSTL合并算法的实现

函数说明

inplace_merge() [1/2]

template<typename Iterator>

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

constexpr

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

模板参数

Iterator

迭代器类型

参数

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

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

引用了 _MSTL , 以及 inplace_merge().

inplace_merge() [2/2]

template<typename Iterator, typename Compare, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>

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

constexpr

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

模板参数

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

参数

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

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

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

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

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

被这些函数引用 inplace_merge() , 以及 merge_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 第 73 行定义.

引用了 _MSTL , 以及 merge().

merge() [2/2]

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Compare, enable_if_t< is_ranges_fwd_iter_v< Iterator1 > &&is_ranges_fwd_iter_v< Iterator2 > &&is_ranges_fwd_iter_v< Iterator3 >, int > = 0>

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 第 45 行定义.

引用了 _MSTL , 以及 copy().

被这些函数引用 merge().