std::lexicographical_compare
定义于头文件 <algorithm>
|
||
(1) | ||
template< class InputIt1, class InputIt2 > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(C++20 前) | |
template< class InputIt1, class InputIt2 > constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(C++20 起) | |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool lexicographical_compare( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, |
(2) | (C++17 起) |
(3) | ||
template< class InputIt1, class InputIt2, class Compare > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(C++20 前) | |
template< class InputIt1, class InputIt2, class Compare > constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(C++20 起) | |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > bool lexicographical_compare( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, |
(4) | (C++17 起) |
检查第一个范围 [first1, last1) 是否按字典序小于第二个范围 [first2, last2) 。
operator<
比较元素。comp
比较函数。policy
执行。这些重载仅若 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> (C++20 前)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> (C++20 起) 为 true 才参与重载决议。。字典序比较是拥有下列属性的操作:
- 逐元素比较二个范围。
- 首个不匹配元素定义范围是否按字典序小于或大于另一个。
- 若一个范围是另一个的前缀,则较短的范围小于另一个。
- 若二个范围拥有等价元素和相同长度,则范围按字典序相等。
- 空范围按字典序小于任何非空范围。
- 二个空范围按字典序相等。
参数
first1, last1 | - | 要检验的第一个元素范围 |
first2, last2 | - | 要检验的第二个元素范围 |
policy | - | 所用的执行策略。细节见执行策略。 |
comp | - | 比较函数对象(即满足比较 (Compare) 要求的对象),若首个参数小于第二个,则返回 true 。 比较函数的签名应等价于如下: bool cmp(const Type1 &a, const Type2 &b); 虽然签名不必有 const & ,函数也不能修改传递给它的对象,而且必须接受(可为 const 的)类型 |
类型要求 | ||
-InputIt1, InputIt2 必须满足遗留输入迭代器 (LegacyInputIterator) 的要求。
| ||
-ForwardIt1, ForwardIt2 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
|
返回值
若第一范围按字典序小于第二个则为 true 。
复杂度
至多应用 2·min(N1, N2) 次比较运算,其中 N1 = std::distance(first1, last1) 而 N2 = std::distance(first2, last2) 。
异常
拥有名为 ExecutionPolicy
的模板形参的重载按下列方式报告错误:
- 若作为算法一部分调用的函数的执行抛出异常,且
ExecutionPolicy
为标准策略之一,则调用 std::terminate 。对于任何其他ExecutionPolicy
,行为是实现定义的。 - 若算法无法分配内存,则抛出 std::bad_alloc 。
可能的实现
版本一 |
---|
template<class InputIt1, class InputIt2> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) { for ( ; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2 ) { if (*first1 < *first2) return true; if (*first2 < *first1) return false; } return (first1 == last1) && (first2 != last2); } |
版本二 |
template<class InputIt1, class InputIt2, class Compare> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp) { for ( ; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2 ) { if (comp(*first1, *first2)) return true; if (comp(*first2, *first1)) return false; } return (first1 == last1) && (first2 != last2); } |
示例
#include <algorithm> #include <iostream> #include <vector> #include <random> int main() { std::vector<char> v1 {'a', 'b', 'c', 'd'}; std::vector<char> v2 {'a', 'b', 'c', 'd'}; std::mt19937 g{std::random_device{}()}; while (!std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end())) { for (auto c : v1) std::cout << c << ' '; std::cout << ">= "; for (auto c : v2) std::cout << c << ' '; std::cout << '\n'; std::shuffle(v1.begin(), v1.end(), g); std::shuffle(v2.begin(), v2.end(), g); } for (auto c : v1) std::cout << c << ' '; std::cout << "< "; for (auto c : v2) std::cout << c << ' '; std::cout << '\n'; }
可能的输出:
a b c d >= a b c d d a b c >= c b d a b d a c >= a d c b a c d b < c d a b
参阅
确定两个元素集合是否是相同的 (函数模板) |