比较算法

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

比较算法 的协作图:

函数
template<typename Iterator1, typename Iterator2, typename BinaryPredicate>
NEFORCE_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>
NEFORCE_NODISCARD constexpr bool	equal (Iterator1 first1, Iterator1 last1, Iterator2 first2) noexcept(noexcept(_NEFORCE equal(first1, last1, first2, _NEFORCE equal_to< iter_value_t< Iterator1 > >())))
	比较两个范围是否相等
template<typename Iterator, typename T, typename Compare>
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(_NEFORCE median(a, b, c, _NEFORCE less< T >())))
	返回三个值的中位数
template<typename Iterator, typename Compare>
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>
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>
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>
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(_NEFORCE clamp(value, lower, upper, _NEFORCE less< T >())))
	将值限制在指定范围内
template<typename Iterator1, typename Iterator2, typename Compare>
NEFORCE_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>
NEFORCE_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>
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)
	查找两个范围中首个不匹配的元素

详细描述

比较算法的实现

函数说明

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

引用了 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 第 445 行定义.

被这些函数引用 clamp().

equal() [1/2]

template<typename Iterator1, typename Iterator2>

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

constexprnoexcept

比较两个范围是否相等

模板参数

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

参数

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

返回

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

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

引用了 equal().

equal() [2/2]

template<typename Iterator1, typename Iterator2, typename BinaryPredicate>

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

引用了 is_ranges_input_iter_v.

被这些函数引用 equal(), array< byte_t, MAC_LEN >::operator==(), bitmap::operator==(), deque< T, Alloc, BufSize >::operator==(), list< pair< Key, Value > >::operator==(), rb_tree< Key, pair< const Key, T >, select1st< pair< const Key, T > >, Compare, Alloc >::operator==() , 以及 vector< byte_t >::operator==().

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

引用了 equal_range().

equal_range() [2/2]

template<typename Iterator, typename T, typename Compare>

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

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

被这些函数引用 equal_range().

lexicographical_compare() [1/2]

template<typename Iterator1, typename Iterator2>

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

constexprnoexcept

字典序比较两个范围

模板参数

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

参数

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

返回

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

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

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

引用了 is_ranges_input_iter_v.

lexicographical_compare() [2/2]

template<typename Iterator1, typename Iterator2, typename Compare>

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

引用了 is_ranges_input_iter_v.

被这些函数引用 array< byte_t, MAC_LEN >::operator<(), bitmap::operator<(), deque< T, Alloc, BufSize >::operator<(), hashtable< pair< const Key, T >, Key, HashFcn, select1st< pair< const Key, T > >, EqualKey, Alloc >::operator<(), list< pair< Key, Value > >::operator<(), rb_tree< Key, pair< const Key, T >, select1st< pair< const Key, T > >, Compare, Alloc >::operator<() , 以及 vector< byte_t >::operator<().

max() [1/3]

template<typename T>

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

constexprnoexcept

返回两个值中的较大者

模板参数

T

值类型

参数

a	第一个值
b	第二个值

返回

a和b中的较大者

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

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

被这些函数引用 allocate_shared(), basic_string< char >::basic_string(), vector< byte_t >::insert(), make_shared(), minmax_element(), random_lcd::next_float(), random_lcd::next_float(), random_mt::next_float(), random_mt::next_float(), secret::next_float(), secret::next_float(), random_lcd::next_int(), random_lcd::next_int(), random_mt::next_int(), random_mt::next_int(), secret::next_int(), secret::next_int(), random_lcd::next_uint64(), random_mt::next_uint64(), secret::next_uint64(), hashtable< pair< const Key, T >, Key, HashFcn, select1st< pair< const Key, T > >, EqualKey, Alloc >::rehash(), vector< byte_t >::reserve(), meta_function::set_arg_hints() , 以及 variant< none_t, ::sockaddr_in, ::sockaddr_in6 >::swap().

max() [3/3]

template<typename T>

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

constexpr

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

模板参数

T

值类型

参数

list

初始化列表

返回

列表中的最大值

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

引用了 list< T, Alloc >::begin(), list< T, Alloc >::end() , 以及 max_element().

max_element() [1/2]

template<typename Iterator>

Iterator max_element ( Iterator first, Iterator last )

constexpr

查找范围中的最大元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

指向最大元素的迭代器

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

引用了 max_element().

max_element() [2/2]

template<typename Iterator, typename Compare>

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

constexpr

查找范围中的最大元素

模板参数

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

参数

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

返回

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

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

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

引用了 is_ranges_input_iter_v.

被这些函数引用 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 第 241 行定义.

引用了 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 第 214 行定义.

被这些函数引用 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 第 196 行定义.

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

被这些函数引用 basic_string< char >::append(), basic_string< char >::append(), basic_string< char >::basic_string(), char_traits_compare(), char_traits_find_last_not_of(), char_traits_find_last_of(), char_traits_rfind(), char_traits_rfind_char(), char_traits_rfind_not_char(), basic_string< char >::copy(), basic_string< char >::erase(), basic_string< char >::erase(), minmax_element(), random_lcd::next_float(), random_mt::next_float(), secret::next_float(), random_lcd::next_int(), random_mt::next_int(), secret::next_int(), select_sort(), meta_function::set_arg_hints(), basic_string< char >::substr(), tim_sort(), basic_string< char >::view(), vector< byte_t >::view() , 以及 vector< byte_t >::view().

min() [3/3]

template<typename T>

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

constexpr

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

模板参数

T

值类型

参数

list

初始化列表

返回

列表中的最小值

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

引用了 list< T, Alloc >::begin(), list< T, Alloc >::end() , 以及 min_element().

min_element() [1/2]

template<typename Iterator>

Iterator min_element ( Iterator first, Iterator last )

constexpr

查找范围中的最小元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

指向最小元素的迭代器

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

引用了 min_element().

min_element() [2/2]

template<typename Iterator, typename Compare>

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

constexpr

查找范围中的最小元素

模板参数

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

参数

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

返回

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

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

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

引用了 is_ranges_input_iter_v.

被这些函数引用 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 第 288 行定义.

引用了 minmax().

minmax() [2/2]

template<typename Iterator, typename Compare>

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

引用了 is_ranges_input_iter_v , 以及 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 第 422 行定义.

引用了 minmax_element().

minmax_element() [2/2]

template<typename Iterator, typename Compare>

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

constexpr

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

模板参数

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

参数

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

返回

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

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

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

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

被这些函数引用 bucket_sort_greater(), bucket_sort_less(), counting_sort() , 以及 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 第 611 行定义.

引用了 mismatch().

mismatch() [2/2]

template<typename Iterator1, typename Iterator2, typename Compare>

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

引用了 is_ranges_input_iter_v , 以及 make_pair().

被这些函数引用 mismatch().