比较算法

MSTL比较算法的实现 更多...

函数
template<typename Iterator1, typename Iterator2, typename BinaryPredicate, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_input_iter_v< Iterator2 >, int > = 0>
MSTL_NODISCARD constexpr bool	equal (Iterator1 first1, Iterator1 last1, Iterator2 first2, BinaryPredicate binary_pred) noexcept(noexcept(++first1) &&noexcept(++first2) &&noexcept(binary_pred(*first1, *first2)))
	比较两个范围是否相等
template<typename Iterator1, typename Iterator2>
MSTL_NODISCARD constexpr bool	equal (Iterator1 first1, Iterator1 last1, Iterator2 first2) noexcept(noexcept(_MSTL equal(first1, last1, first2, _MSTL equal_to< iter_value_t< Iterator1 > >())))
	比较两个范围是否相等
template<typename Iterator, typename T, typename Compare, enable_if_t< is_ranges_fwd_iter_v< Iterator >, int > = 0>
constexpr pair< Iterator, Iterator >	equal_range (Iterator first, Iterator last, const T &value, Compare comp)
	查找值的相等范围
template<typename Iterator, typename T>
constexpr pair< Iterator, Iterator >	equal_range (Iterator first, Iterator last, const T &value)
	查找值的相等范围
template<typename T, typename Compare>
constexpr const T &	max (const T &a, const T &b, Compare comp) noexcept(noexcept(comp(a, b)))
	返回两个值中的较大者
template<typename T>
constexpr const T &	max (const T &a, const T &b) noexcept(noexcept(a< b))
	返回两个值中的较大者
template<typename T, typename Compare>
constexpr const T &	min (const T &a, const T &b, Compare comp) noexcept(noexcept(comp(b, a)))
	返回两个值中的较小者
template<typename T>
constexpr const T &	min (const T &a, const T &b) noexcept(noexcept(b< a))
	返回两个值中的较小者
template<typename T, typename Compare>
constexpr const T &	median (const T &a, const T &b, const T &c, Compare comp) noexcept(noexcept(comp(a, b)))
	返回三个值的中位数
template<typename T>
constexpr const T &	median (const T &a, const T &b, const T &c) noexcept(noexcept(_MSTL median(a, b, c, _MSTL less< T >())))
	返回三个值的中位数
template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>
pair< iter_value_t< Iterator >, iter_value_t< Iterator > > constexpr	minmax (Iterator first, Iterator last, Compare comp)
	查找范围中的最小值和最大值
template<typename Iterator>
constexpr pair< iter_value_t< Iterator >, iter_value_t< Iterator > >	minmax (Iterator first, Iterator last)
	查找范围中的最小值和最大值
template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>
constexpr Iterator	max_element (Iterator first, Iterator last, Compare comp)
	查找范围中的最大元素
template<typename Iterator>
constexpr Iterator	max_element (Iterator first, Iterator last)
	查找范围中的最大元素
template<typename T>
constexpr const T &	max (std::initializer_list< T > list)
	返回初始化列表中的最大值
template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>
constexpr Iterator	min_element (Iterator first, Iterator last, Compare comp)
	查找范围中的最小元素
template<typename Iterator>
constexpr Iterator	min_element (Iterator first, Iterator last)
	查找范围中的最小元素
template<typename T>
constexpr const T &	min (std::initializer_list< T > list)
	返回初始化列表中的最小值
template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>
constexpr pair< Iterator, Iterator >	minmax_element (Iterator first, Iterator last, Compare comp)
	同时查找范围中的最小和最大元素
template<typename Iterator>
constexpr pair< Iterator, Iterator >	minmax_element (Iterator first, Iterator last)
	同时查找范围中的最小和最大元素
template<typename T, typename Compare>
constexpr const T &	clamp (const T &value, const T &lower, const T &upper, Compare comp) noexcept(noexcept(comp(value, lower)))
	将值限制在指定范围内
template<typename T>
constexpr const T &	clamp (const T &value, const T &lower, const T &upper) noexcept(noexcept(_MSTL clamp(value, lower, upper, _MSTL less< T >())))
	将值限制在指定范围内
template<typename Iterator1, typename Iterator2, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_input_iter_v< Iterator2 >, int > = 0>
MSTL_NODISCARD constexpr bool	lexicographical_compare (Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Compare comp) noexcept(noexcept(++first1) &&noexcept(++first2) &&noexcept(comp(*first1, *first2)) &&noexcept(first1==last1 &&first2 !=last2))
	字典序比较两个范围
template<typename Iterator1, typename Iterator2, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_input_iter_v< Iterator2 >, int > = 0>
MSTL_NODISCARD constexpr bool	lexicographical_compare (Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) noexcept(noexcept(_INNER __lexicographical_compare_aux(first1, last1, first2, last2)))
	字典序比较两个范围
template<typename Iterator1, typename Iterator2, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_input_iter_v< Iterator2 >, int > = 0>
pair< Iterator1, Iterator2 > constexpr	mismatch (Iterator1 first1, Iterator1 last1, Iterator2 first2, Compare comp)
	查找两个范围中首个不匹配的元素
template<typename Iterator1, typename Iterator2>
constexpr pair< Iterator1, Iterator2 >	mismatch (Iterator1 first1, Iterator1 last1, Iterator2 first2)
	查找两个范围中首个不匹配的元素

详细描述

MSTL比较算法的实现

函数说明

clamp() [1/2]

template<typename T>

const T & clamp ( const T & value, const T & lower, const T & upper )

constexprnoexcept

将值限制在指定范围内

模板参数

T

值类型

参数

value	要限制的值
lower	下限值
upper	上限值

返回

限制后的值

在文件 compare.hpp 第 440 行定义.

引用了 _MSTL , 以及 clamp().

clamp() [2/2]

template<typename T, typename Compare>

const T & clamp ( const T & value, const T & lower, const T & upper, Compare comp )

constexprnoexcept

将值限制在指定范围内

模板参数

T	值类型
Compare	比较函数类型

参数

value	要限制的值
lower	下限值
upper	上限值
comp	比较函数对象

返回

限制后的值

将 value 限制在 [lower, upper] 范围内：

• 如果 value < lower，返回 lower
• 如果 value > upper，返回 upper
• 否则返回 value

要求 lower <= upper

在文件 compare.hpp 第 422 行定义.

被这些函数引用 clamp().

equal() [1/2]

template<typename Iterator1, typename Iterator2>

MSTL_NODISCARD constexpr bool equal ( Iterator1 first1, Iterator1 last1, Iterator2 first2 )

constexprnoexcept

比较两个范围是否相等

模板参数

Iterator1	第一个迭代器类型
Iterator2	第二个迭代器类型

参数

first1	第一个范围起始
last1	第一个范围结束
first2	第二个范围起始

返回

如果两个范围相等则返回true，否则返回false

在文件 compare.hpp 第 67 行定义.

引用了 _MSTL , 以及 equal().

equal() [2/2]

template<typename Iterator1, typename Iterator2, typename BinaryPredicate, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_input_iter_v< Iterator2 >, int > = 0>

MSTL_NODISCARD constexpr bool equal ( Iterator1 first1, Iterator1 last1, Iterator2 first2, BinaryPredicate binary_pred )

constexprnoexcept

比较两个范围是否相等

模板参数

Iterator1	第一个迭代器类型
Iterator2	第二个迭代器类型
BinaryPredicate	二元谓词类型

参数

first1	第一个范围起始
last1	第一个范围结束
first2	第二个范围起始
binary_pred	相等性谓词

返回

如果两个范围相等则返回true，否则返回false

比较范围 [first1, last1) 和以 first2 开始的范围是否相等。 使用二元谓词 binary_pred 判断两个元素是否相等。 要求第二个范围至少与第一个范围一样长。

在文件 compare.hpp 第 49 行定义.

被这些函数引用 equal().

equal_range() [1/2]

template<typename Iterator, typename T>

pair< Iterator, Iterator > equal_range ( Iterator first, Iterator last, const T & value )

constexpr

查找值的相等范围

模板参数

Iterator	迭代器类型
T	值类型

参数

first	范围起始
last	范围结束
value	要查找的值

返回

包含相等范围的pair<起始迭代器, 结束迭代器>

在文件 compare.hpp 第 122 行定义.

引用了 _MSTL , 以及 equal_range().

equal_range() [2/2]

template<typename Iterator, typename T, typename Compare, enable_if_t< is_ranges_fwd_iter_v< Iterator >, int > = 0>

pair< Iterator, Iterator > equal_range ( Iterator first, Iterator last, const T & value, Compare comp )

constexpr

查找值的相等范围

模板参数

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

参数

first	范围起始
last	范围结束
value	要查找的值
comp	比较函数对象

返回

包含相等范围的pair<起始迭代器, 结束迭代器>

在已排序的范围 [first, last) 中查找所有等于 value 的元素。 返回的pair包含相等范围的 [起始, 结束) 迭代器。

在文件 compare.hpp 第 87 行定义.

引用了 _MSTL, advance(), distance(), lower_bound() , 以及 upper_bound().

被这些函数引用 equal_range().

lexicographical_compare() [1/2]

template<typename Iterator1, typename Iterator2, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_input_iter_v< Iterator2 >, int > = 0>

MSTL_NODISCARD constexpr bool lexicographical_compare ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2 )

constexprnoexcept

字典序比较两个范围

模板参数

Iterator1	第一个迭代器类型
Iterator2	第二个迭代器类型

参数

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

返回

如果第一个范围字典序小于第二个范围则返回true，否则返回false

对连续迭代器进行优化，使用内存比较提高性能。

在文件 compare.hpp 第 543 行定义.

引用了 _INNER.

lexicographical_compare() [2/2]

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

MSTL_NODISCARD constexpr bool lexicographical_compare ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Compare comp )

constexprnoexcept

字典序比较两个范围

模板参数

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

参数

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

返回

如果第一个范围字典序小于第二个范围则返回true，否则返回false

比较范围 [first1, last1) 和 [first2, last2) 的字典序：

1. 比较对应元素，直到找到不相等的元素
2. 第一个范围的元素小于第二个范围的对应元素时返回true
3. 所有对应元素都相等，但第一个范围较短时返回true

在文件 compare.hpp 第 465 行定义.

max() [1/3]

template<typename T>

const T & max ( const T & a, const T & b )

constexprnoexcept

返回两个值中的较大者

模板参数

T

值类型

参数

a	第一个值
b	第二个值

返回

a和b中的较大者

在文件 compare.hpp 第 154 行定义.

max() [2/3]

template<typename T, typename Compare>

const T & max ( const T & a, const T & b, Compare comp )

constexprnoexcept

返回两个值中的较大者

模板参数

T	值类型
Compare	比较函数类型

参数

a	第一个值
b	第二个值
comp	比较函数对象

返回

a和b中的较大者

使用比较函数 comp 判断大小：

• 如果 comp(a, b) 返回 true，则 b 较大
• 否则 a 较大

在文件 compare.hpp 第 141 行定义.

被这些函数引用 allocate_shared(), make_shared(), minmax_element(), random_lcd::next_double(), random_lcd::next_double(), random_mt::next_double(), random_mt::next_double(), random_lcd::next_int(), random_lcd::next_int(), random_mt::next_int(), random_mt::next_int(), secret::next_int(), secret::next_int() , 以及 variant< Types >::swap().

max() [3/3]

template<typename T>

const T & max ( std::initializer_list< T > list )

constexpr

返回初始化列表中的最大值

模板参数

T

值类型

参数

list

初始化列表

返回

列表中的最大值

在文件 compare.hpp 第 323 行定义.

引用了 _MSTL , 以及 max_element().

max_element() [1/2]

template<typename Iterator>

Iterator max_element ( Iterator first, Iterator last )

constexpr

查找范围中的最大元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

指向最大元素的迭代器

在文件 compare.hpp 第 312 行定义.

引用了 _MSTL , 以及 max_element().

max_element() [2/2]

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

Iterator max_element ( Iterator first, Iterator last, Compare comp )

constexpr

查找范围中的最大元素

模板参数

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

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

指向最大元素的迭代器，如果范围为空则返回first

查找范围 [first, last) 中的最大元素。 如果有多个最大元素，返回第一个遇到的。

在文件 compare.hpp 第 296 行定义.

被这些函数引用 max(), max_element() , 以及 minmax_element().

median() [1/2]

template<typename T>

const T & median ( const T & a, const T & b, const T & c )

constexprnoexcept

返回三个值的中位数

模板参数

T

值类型

参数

a	第一个值
b	第二个值
c	第三个值

返回

a、b、c中的中位数

在文件 compare.hpp 第 232 行定义.

引用了 _MSTL , 以及 median().

median() [2/2]

template<typename T, typename Compare>

const T & median ( const T & a, const T & b, const T & c, Compare comp )

constexprnoexcept

返回三个值的中位数

模板参数

T	值类型
Compare	比较函数类型

参数

a	第一个值
b	第二个值
c	第三个值
comp	比较函数对象

返回

a、b、c中的中位数

使用比较函数 comp 确定三个值的中位数。 最多进行3次比较。

在文件 compare.hpp 第 205 行定义.

被这些函数引用 introspective_sort(), median() , 以及 nth_element().

min() [1/3]

template<typename T>

const T & min ( const T & a, const T & b )

constexprnoexcept

返回两个值中的较小者

模板参数

T

值类型

参数

a	第一个值
b	第二个值

返回

a和b中的较小者

在文件 compare.hpp 第 186 行定义.

min() [2/3]

template<typename T, typename Compare>

const T & min ( const T & a, const T & b, Compare comp )

constexprnoexcept

返回两个值中的较小者

模板参数

T	值类型
Compare	比较函数类型

参数

a	第一个值
b	第二个值
comp	比较函数对象

返回

a和b中的较小者

使用比较函数 comp 判断大小：

• 如果 comp(b, a) 返回 true，则 b 较小
• 否则 a 较小

在文件 compare.hpp 第 173 行定义.

被这些函数引用 minmax_element(), random_lcd::next_double(), random_mt::next_double(), random_lcd::next_int(), random_mt::next_int() , 以及 secret::next_int().

min() [3/3]

template<typename T>

const T & min ( std::initializer_list< T > list )

constexpr

返回初始化列表中的最小值

模板参数

T

值类型

参数

list

初始化列表

返回

列表中的最小值

在文件 compare.hpp 第 368 行定义.

引用了 _MSTL , 以及 min_element().

min_element() [1/2]

template<typename Iterator>

Iterator min_element ( Iterator first, Iterator last )

constexpr

查找范围中的最小元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

指向最小元素的迭代器

在文件 compare.hpp 第 357 行定义.

引用了 _MSTL , 以及 min_element().

min_element() [2/2]

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

Iterator min_element ( Iterator first, Iterator last, Compare comp )

constexpr

查找范围中的最小元素

模板参数

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

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

指向最小元素的迭代器，如果范围为空则返回first

查找范围 [first, last) 中的最小元素。 如果有多个最小元素，返回第一个遇到的。

在文件 compare.hpp 第 341 行定义.

被这些函数引用 min(), min_element() , 以及 minmax_element().

minmax() [1/2]

template<typename Iterator>

pair< iter_value_t< Iterator >, iter_value_t< Iterator > > minmax ( Iterator first, Iterator last )

constexpr

查找范围中的最小值和最大值

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

包含最小值和最大值的pair

在文件 compare.hpp 第 278 行定义.

引用了 _MSTL , 以及 minmax().

minmax() [2/2]

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

pair< iter_value_t< Iterator >, iter_value_t< Iterator > > constexpr minmax ( Iterator first, Iterator last, Compare comp )

constexpr

查找范围中的最小值和最大值

模板参数

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

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

包含最小值和最大值的pair

同时查找范围 [first, last) 中的最小值和最大值。 如果范围为空，返回默认构造的pair。

在文件 compare.hpp 第 252 行定义.

引用了 _MSTL , 以及 make_pair().

被这些函数引用 minmax().

minmax_element() [1/2]

template<typename Iterator>

pair< Iterator, Iterator > minmax_element ( Iterator first, Iterator last )

constexpr

同时查找范围中的最小和最大元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

pair<指向最小元素的迭代器, 指向最大元素的迭代器>

在文件 compare.hpp 第 399 行定义.

引用了 _MSTL , 以及 minmax_element().

minmax_element() [2/2]

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

pair< Iterator, Iterator > minmax_element ( Iterator first, Iterator last, Compare comp )

constexpr

同时查找范围中的最小和最大元素

模板参数

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

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

pair<指向最小元素的迭代器, 指向最大元素的迭代器>

同时查找范围 [first, last) 中的最小和最大元素。 如果范围为空，两个迭代器都指向first。

在文件 compare.hpp 第 385 行定义.

引用了 _MSTL, make_pair(), max(), max_element(), min() , 以及 min_element().

被这些函数引用 minmax_element().

mismatch() [1/2]

template<typename Iterator1, typename Iterator2>

pair< Iterator1, Iterator2 > mismatch ( Iterator1 first1, Iterator1 last1, Iterator2 first2 )

constexpr

查找两个范围中首个不匹配的元素

模板参数

Iterator1	第一个迭代器类型
Iterator2	第二个迭代器类型

参数

first1	第一个范围起始
last1	第一个范围结束
first2	第二个范围起始

返回

pair<第一个范围中不匹配的位置, 第二个范围中对应的位置>

在文件 compare.hpp 第 585 行定义.

引用了 _MSTL , 以及 mismatch().

mismatch() [2/2]

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

pair< Iterator1, Iterator2 > constexpr mismatch ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Compare comp )

constexpr

查找两个范围中首个不匹配的元素

模板参数

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

参数

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

返回

pair<第一个范围中不匹配的位置, 第二个范围中对应的位置>

比较范围 [first1, last1) 和以 first2 开始的范围， 返回第一个不满足 comp(*it1, *it2) 的位置。 如果所有对应元素都满足谓词，返回 pair<last1, first2 + (last1 - first1)>

在文件 compare.hpp 第 568 行定义.

引用了 _MSTL , 以及 make_pair().

被这些函数引用 mismatch().