比较算法

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

比较算法 的协作图:

函数
template<typename Iterator1, typename Iterator2, typename BinaryPredicate>
constexpr bool	neforce::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>
constexpr bool	neforce::equal (Iterator1 first1, Iterator1 last1, Iterator2 first2) noexcept(noexcept(_NEFORCE equal(first1, last1, first2, _NEFORCE equal_to<>())))
	比较两个范围是否相等
template<typename Iterator, typename T, typename Compare>
constexpr pair< Iterator, Iterator >	neforce::equal_range (Iterator first, Iterator last, const T &value, Compare comp)
	查找值的相等范围
template<typename Iterator, typename T>
constexpr pair< Iterator, Iterator >	neforce::equal_range (Iterator first, Iterator last, const T &value)
	查找值的相等范围
template<typename T, typename Compare>
constexpr const T &	neforce::max (const T &a, const T &b, Compare comp) noexcept(noexcept(comp(a, b)))
	返回两个值中的较大者
template<typename T>
constexpr const T &	neforce::max (const T &a, const T &b) noexcept(noexcept(a< b))
	返回两个值中的较大者
template<typename T, typename Compare>
constexpr const T &	neforce::min (const T &a, const T &b, Compare comp) noexcept(noexcept(comp(b, a)))
	返回两个值中的较小者
template<typename T>
constexpr const T &	neforce::min (const T &a, const T &b) noexcept(noexcept(b< a))
	返回两个值中的较小者
template<typename T, typename Compare>
constexpr T	neforce::median (const T &a, const T &b, const T &c, Compare comp) noexcept(noexcept(comp(a, b)))
	返回三个值的中位数
template<typename T>
constexpr T	neforce::median (const T &a, const T &b, const T &c) noexcept(noexcept(a< b))
	返回三个值的中位数
template<typename Iterator, typename Compare>
constexpr Iterator	neforce::max_element (Iterator first, Iterator last, Compare comp)
	查找范围中的最大元素
template<typename Iterator>
constexpr Iterator	neforce::max_element (Iterator first, Iterator last)
	查找范围中的最大元素
template<typename T>
constexpr const T &	neforce::max (std::initializer_list< T > list)
	返回初始化列表中的最大值
template<typename Iterator, typename Compare>
constexpr Iterator	neforce::min_element (Iterator first, Iterator last, Compare comp)
	查找范围中的最小元素
template<typename Iterator>
constexpr Iterator	neforce::min_element (Iterator first, Iterator last)
	查找范围中的最小元素
template<typename T>
constexpr const T &	neforce::min (std::initializer_list< T > list)
	返回初始化列表中的最小值
template<typename Iterator, typename Compare>
constexpr pair< Iterator, Iterator >	neforce::minmax_element (Iterator first, Iterator last, Compare comp)
	同时查找范围中的最小和最大元素
template<typename Iterator>
constexpr pair< Iterator, Iterator >	neforce::minmax_element (Iterator first, Iterator last)
	同时查找范围中的最小和最大元素
template<typename T, typename Compare>
constexpr T	neforce::clamp (const T &value, const T &lower, const T &upper, Compare comp) noexcept(noexcept(comp(value, lower)))
	将值限制在指定范围内
template<typename T>
constexpr T	neforce::clamp (const T &value, const T &lower, const T &upper) noexcept(noexcept(lower< upper))
	将值限制在指定范围内
template<typename Iterator1, typename Iterator2, typename Compare>
constexpr bool	neforce::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>
constexpr bool	neforce::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>
constexpr pair< Iterator1, Iterator2 >	neforce::mismatch (Iterator1 first1, Iterator1 last1, Iterator2 first2, Compare comp)
	查找两个范围中首个不匹配的元素
template<typename Iterator1, typename Iterator2>
constexpr pair< Iterator1, Iterator2 >	neforce::mismatch (Iterator1 first1, Iterator1 last1, Iterator2 first2)
	查找两个范围中首个不匹配的元素

详细描述

比较算法的实现

函数说明

clamp() [1/2]

template<typename T>

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

constexprnoexcept

将值限制在指定范围内

模板参数

T

值类型

参数

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

返回

限制后的值

在文件 algorithm/compare.hpp 第 427 行定义.

引用了 clamp().

clamp() [2/2]

template<typename T, typename Compare>

T neforce::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

在文件 algorithm/compare.hpp 第 408 行定义.

引用了 clamp().

被这些函数引用 clamp(), clamp(), neforce::basic_string< char >::substr() , 以及 neforce::basic_string_view< typename Traits::char_type, Traits >::substr().

equal() [1/2]

template<typename Iterator1, typename Iterator2>

bool neforce::equal ( Iterator1 first1, Iterator1 last1, Iterator2 first2 )

nodiscardconstexprnoexcept

比较两个范围是否相等

模板参数

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

参数

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

返回

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

在文件 algorithm/compare.hpp 第 78 行定义.

引用了 equal().

equal() [2/2]

template<typename Iterator1, typename Iterator2, typename BinaryPredicate>

bool neforce::equal ( Iterator1 first1, Iterator1 last1, Iterator2 first2, BinaryPredicate binary_pred )

nodiscardconstexprnoexcept

比较两个范围是否相等

模板参数

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

参数

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

返回

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

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

在文件 algorithm/compare.hpp 第 54 行定义.

引用了 equal() , 以及 is_ranges_input_iter_v.

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

equal_range() [1/2]

template<typename Iterator, typename T>

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

constexpr

查找值的相等范围

模板参数

Iterator	迭代器类型
T	值类型

参数

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

返回

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

在文件 algorithm/compare.hpp 第 114 行定义.

引用了 equal_range().

equal_range() [2/2]

template<typename Iterator, typename T, typename Compare>

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

constexpr

查找值的相等范围

模板参数

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

参数

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

返回

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

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

在文件 algorithm/compare.hpp 第 98 行定义.

引用了 equal_range(), is_ranges_fwd_iter_v, lower_bound(), make_pair() , 以及 upper_bound().

被这些函数引用 equal_range() , 以及 equal_range().

lexicographical_compare() [1/2]

template<typename Iterator1, typename Iterator2>

bool neforce::lexicographical_compare ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2 )

nodiscardconstexprnoexcept

字典序比较两个范围

模板参数

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

参数

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

返回

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

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

在文件 algorithm/compare.hpp 第 504 行定义.

引用了 is_ranges_input_iter_v , 以及 lexicographical_compare().

lexicographical_compare() [2/2]

template<typename Iterator1, typename Iterator2, typename Compare>

bool neforce::lexicographical_compare ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Compare comp )

nodiscardconstexprnoexcept

字典序比较两个范围

模板参数

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

参数

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

返回

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

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

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

在文件 algorithm/compare.hpp 第 450 行定义.

引用了 is_ranges_input_iter_v , 以及 lexicographical_compare().

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

max() [1/3]

template<typename T>

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

constexprnoexcept

返回两个值中的较大者

模板参数

T

值类型

参数

a	第一个值
b	第二个值

返回

a和b中的较大者

在文件 algorithm/compare.hpp 第 145 行定义.

引用了 max().

max() [2/3]

template<typename T, typename Compare>

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

constexprnoexcept

返回两个值中的较大者

模板参数

T	值类型
Compare	比较函数类型

参数

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

返回

a和b中的较大者

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

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

在文件 algorithm/compare.hpp 第 133 行定义.

引用了 max().

被这些函数引用 allocate_shared(), neforce::basic_string< char >::basic_string(), neforce::string_builder::build(), neforce::flat_hashtable< pair< Key, T >, Key, HashFcn, select1st< pair< Key, T > >, EqualKey, Alloc >::emplace_equal(), neforce::flat_hashtable< pair< Key, T >, Key, HashFcn, select1st< pair< Key, T > >, EqualKey, Alloc >::emplace_unique(), neforce::vector< Value, Alloc >::insert(), make_shared(), max(), max(), max(), minmax_element(), neforce::random_lcd::next_float(), neforce::random_lcd::next_float(), neforce::random_mt::next_float(), neforce::random_mt::next_float(), neforce::secret::next_float(), neforce::secret::next_float(), neforce::random_lcd::next_int(), neforce::random_lcd::next_int(), neforce::random_mt::next_int(), neforce::random_mt::next_int(), neforce::secret::next_int(), neforce::secret::next_int(), neforce::random_lcd::next_uint64(), neforce::random_mt::next_uint64(), neforce::secret::next_uint64(), neforce::hashtable< pair< const Key, T >, Key, HashFcn, select1st< pair< const Key, T > >, EqualKey, Alloc >::rehash(), neforce::vector< Value, Alloc >::reserve(), neforce::reflect::meta_function::set_arg_hints(), neforce::http::load_balancer::set_max_failures(), neforce::http::http_client::set_max_redirects(), neforce::http::http_server::set_max_sessions(), neforce::color::set_opacity(), neforce::variant< none_t, ::sockaddr_in, ::sockaddr_in6 >::swap() , 以及 neforce::system_event::wait().

max() [3/3]

template<typename T>

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

constexpr

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

模板参数

T

值类型

参数

list

初始化列表

返回

列表中的最大值

在文件 algorithm/compare.hpp 第 270 行定义.

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

max_element() [1/2]

template<typename Iterator>

Iterator neforce::max_element ( Iterator first, Iterator last )

constexpr

查找范围中的最大元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

指向最大元素的迭代器

在文件 algorithm/compare.hpp 第 259 行定义.

引用了 max_element().

max_element() [2/2]

template<typename Iterator, typename Compare>

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

constexpr

查找范围中的最大元素

模板参数

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

参数

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

返回

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

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

在文件 algorithm/compare.hpp 第 237 行定义.

引用了 is_ranges_input_iter_v , 以及 max_element().

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

median() [1/2]

template<typename T>

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

constexprnoexcept

返回三个值的中位数

模板参数

T

值类型

参数

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

返回

a、b、c中的中位数

在文件 algorithm/compare.hpp 第 220 行定义.

引用了 median().

median() [2/2]

template<typename T, typename Compare>

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

constexprnoexcept

返回三个值的中位数

模板参数

T	值类型
Compare	比较函数类型

参数

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

返回

a、b、c中的中位数

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

在文件 algorithm/compare.hpp 第 193 行定义.

引用了 median().

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

min() [1/3]

template<typename T>

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

constexprnoexcept

返回两个值中的较小者

模板参数

T

值类型

参数

a	第一个值
b	第二个值

返回

a和b中的较小者

在文件 algorithm/compare.hpp 第 175 行定义.

引用了 min().

min() [2/3]

template<typename T, typename Compare>

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

constexprnoexcept

返回两个值中的较小者

模板参数

T	值类型
Compare	比较函数类型

参数

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

返回

a和b中的较小者

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

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

在文件 algorithm/compare.hpp 第 163 行定义.

引用了 min().

被这些函数引用 neforce::basic_string< char >::append(), neforce::basic_string< char >::append(), neforce::basic_string< char >::basic_string(), char_traits_compare(), char_traits_find_last_not_of(), char_traits_find_last_not_of(), char_traits_find_last_of(), char_traits_find_last_of(), char_traits_rfind(), char_traits_rfind_char(), char_traits_rfind_not_char(), neforce::basic_string< char >::compare_ignore_case(), neforce::basic_string_view< typename Traits::char_type, Traits >::compare_ignore_case(), neforce::basic_string< char >::copy(), neforce::basic_string< char >::erase(), neforce::basic_string< char >::erase(), neforce::basic_string< char >::max_size(), min(), min(), min(), minmax_element(), neforce::random_lcd::next_float(), neforce::random_mt::next_float(), neforce::secret::next_float(), neforce::random_lcd::next_int(), neforce::random_mt::next_int(), neforce::secret::next_int(), neforce::utf8_iterator::operator++(), select_sort(), neforce::reflect::meta_function::set_arg_hints(), neforce::color::set_opacity(), neforce::basic_string< char >::substr(), tim_sort(), neforce::basic_string< char >::view(), neforce::vector< Value, Alloc >::view() , 以及 neforce::vector< Value, Alloc >::view().

min() [3/3]

template<typename T>

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

constexpr

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

模板参数

T

值类型

参数

list

初始化列表

返回

列表中的最小值

在文件 algorithm/compare.hpp 第 320 行定义.

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

min_element() [1/2]

template<typename Iterator>

Iterator neforce::min_element ( Iterator first, Iterator last )

constexpr

查找范围中的最小元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

指向最小元素的迭代器

在文件 algorithm/compare.hpp 第 309 行定义.

引用了 min_element().

min_element() [2/2]

template<typename Iterator, typename Compare>

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

constexpr

查找范围中的最小元素

模板参数

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

参数

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

返回

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

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

在文件 algorithm/compare.hpp 第 287 行定义.

引用了 is_ranges_input_iter_v , 以及 min_element().

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

minmax_element() [1/2]

template<typename Iterator>

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

constexpr

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

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

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

在文件 algorithm/compare.hpp 第 386 行定义.

引用了 minmax_element().

minmax_element() [2/2]

template<typename Iterator, typename Compare>

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

constexpr

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

模板参数

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

参数

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

返回

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

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

在文件 algorithm/compare.hpp 第 337 行定义.

引用了 is_ranges_input_iter_v, make_pair(), max(), min(), minmax_element() , 以及 next().

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

mismatch() [1/2]

template<typename Iterator1, typename Iterator2>

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

constexpr

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

模板参数

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

参数

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

返回

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

在文件 algorithm/compare.hpp 第 548 行定义.

引用了 mismatch().

mismatch() [2/2]

template<typename Iterator1, typename Iterator2, typename Compare>

pair< Iterator1, Iterator2 > neforce::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)>

在文件 algorithm/compare.hpp 第 528 行定义.

引用了 is_ranges_input_iter_v, make_pair() , 以及 mismatch().

被这些函数引用 mismatch() , 以及 mismatch().