std::lexicographical_compare
定义在头文件 <algorithm> 中 |
||
template< class InputIt1, class InputIt2 > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(1) | (从 C++20 开始为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > |
(2) | (从 C++17 开始) |
template< class InputIt1, class InputIt2, class Compare > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(3) | (从 C++20 开始为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > |
(4) | (从 C++17 开始) |
检查第一个范围 [
first1,
last1)
是否字典序上小于第二个范围 [
first2,
last2)
。
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true 时参与重载解析。 |
(直到 C++20) |
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true。 |
(从 C++20 开始) |
字典序比较是一种具有以下属性的操作
- 两个范围逐个元素进行比较。
- 第一个不匹配的元素决定哪个范围字典序上小于或大于另一个范围。
- 如果一个范围是另一个范围的前缀,则较短的范围字典序上小于另一个范围。
- 如果两个范围具有等效的元素并且长度相同,则这些范围字典序上相等。
- 空范围字典序上小于任何非空范围。
- 两个空范围字典序上相等。
内容 |
[编辑] 参数
first1, last1 | - | 要检查的第一个元素范围 |
first2, last2 | - | 要检查的第二个元素范围 |
policy | - | 要使用的执行策略。有关详细信息,请参阅 执行策略。 |
comp | - | 比较函数对象(即满足 Compare 要求的对象),如果第一个参数小于第二个参数则返回 true。 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 虽然签名不需要具有 const&,但函数不能修改传递给它的对象,并且必须能够接受类型(可能是常量) |
类型要求 | ||
-InputIt1, InputIt2 必须满足 LegacyInputIterator 的要求。 | ||
-ForwardIt1, ForwardIt2 必须满足 LegacyForwardIterator 的要求。 | ||
-Compare 必须满足 Compare 的要求。 |
[edit] 返回值
如果第一个范围在词法上小于第二个范围,则为 true,否则为 false。
[edit] 复杂度
给定 N
1 作为 std::distance(first1, last1) 和 N
2 作为 std::distance(first2, last2)
1,N
2) 次使用 operator< 的比较。
1,N
2) 次比较函数 comp 的应用。
[edit] 异常
具有名为 ExecutionPolicy
的模板参数的重载报告错误如下
- 如果作为算法的一部分调用的函数的执行抛出异常,并且
ExecutionPolicy
是 标准策略 之一,则调用 std::terminate。对于任何其他ExecutionPolicy
,行为是实现定义的。 - 如果算法无法分配内存,则抛出 std::bad_alloc。
[edit] 可能的实现
lexicographical_compare (1) |
---|
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); } |
lexicographical_compare (3) |
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); } |
[edit] 示例
#include <algorithm> #include <iostream> #include <random> #include <vector> void print(const std::vector<char>& v, auto suffix) { for (char c : v) std::cout << c << ' '; std::cout << suffix; } int main() { std::vector<char> v1{'a', 'b', 'c', 'd'}; std::vector<char> v2{'a', 'b', 'c', 'd'}; for (std::mt19937 g{std::random_device{}()}; !std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end());) { print(v1, ">= "); print(v2, '\n'); std::shuffle(v1.begin(), v1.end(), g); std::shuffle(v2.begin(), v2.end(), g); } print(v1, "< "); print(v2, '\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
[edit] 缺陷报告
以下更改行为的缺陷报告被追溯应用于先前发布的 C++ 标准。
DR | 应用于 | 已发布的行为 | 正确的行为 |
---|---|---|---|
LWG 142 | C++98 | 最多允许进行 min(N 1,N 2) 次比较,但 这是不可能的(等效性由 2 次比较确定) |
将限制翻倍 |
LWG 1205 | C++98 | 涉及空范围的词法比较的结果不清楚 | 澄清 |
[edit] 另请参阅
确定两组元素是否相同 (函数模板) | |
使用三方比较比较两个范围 (函数模板) | |
如果一个范围在词法上小于另一个范围,则返回 true (niebloid) |