std::equal
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| (1) | (C++20 起为 constexpr) | |
| (2) | (C++20 起为 constexpr) | |
| (3) | (C++14 起) (C++20 起为 constexpr) |
|
| (4) | (C++14 起) (C++20 起为 constexpr) |
|
| |
(5) | (C++17 起) |
| |
(6) | (C++17 起) |
| |
(7) | (C++17 起) |
| |
(8) | (C++17 起) |
检查两个目标范围 [first1, last1) 和 [first2, last2) 是否相等。对于不带 last2 参数的重载，last2 是 std::next(first2, std::distance(first1, last1)。
1,3) 用
operator== 比较元素。2,4) 用给定的二元谓词
p 比较元素。5-8) 同 (1-4)，但按照
policy 执行。 这些重载只有在以下表达式的值是
true 时才会参与重载决议：
|
|
(C++20 前) |
|
|
(C++20 起) |
参数
| first1, last1 | - | 表示第一目标范围的迭代器对 |
| first2, last2 | - | 表示第二目标范围的迭代器对 |
| p | - | 若元素应被当做相等则返回 true 的二元谓词谓词函数的签名应等价于如下：
虽然签名不必有 |
| policy | - | 所用的执行策略 |
| 类型要求 | ||
-InputIt1, InputIt2 必须满足老式输入迭代器 (LegacyInputIterator) 。
| ||
-ForwardIt1, ForwardIt2 必须满足老式向前迭代器 (LegacyForwardIterator) 。
| ||
-BinaryPred 必须满足二元谓词 (BinaryPredicate) 。
| ||
返回值
如果两个范围大小相同，且范围内的对应元素都相等，那么返回 true。否则返回 false。
复杂度
给定 N1 为 std::distance(first1, last1)，N2 为 std::distance(first2, last2)：
1) 最多应用 N1 次
operator== 进行比较。2) 最多应用 N1 次
p。3) 最多应用 min(N1,N2) 次
operator== 进行比较。4) 最多应用 min(N1,N2) 次
p。5) 应用 𝓞(N1) 次
operator== 进行比较。6) 应用 𝓞(N1) 次
p。7) 应用 𝓞(min(N1,N2)) 次
operator== 进行比较。8) 应用 𝓞(min(N1,N2)) 次
p。异常
5-8) 在执行过程中：
- 如果并行化所需的临时内存资源不可用，那么就会抛出 std::bad_alloc。
- 如果在通过算法实参访问对象时抛出了未捕获的异常，那么行为由执行策略决定（标准策略会调用 std::terminate）。
可能的实现
| equal (1) |
|---|
template<class InputIt1, class InputIt2>
constexpr //< C++20 起
bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2)
{
for (; first1 != last1; ++first1, ++first2)
if (!(*first1 == *first2))
return false;
return true;
}
|
| equal (2) |
template<class InputIt1, class InputIt2, class BinaryPred>
constexpr //< C++20 起
bool equal(InputIt1 first1, InputIt1 last1,
InputIt2 first2, BinaryPred p)
{
for (; first1 != last1; ++first1, ++first2)
if (!p(*first1, *first2))
return false;
return true;
}
|
| equal (3) |
namespace detail
{
// 随机访问迭代器实现（可以快速检测范围大小）
template<class RandomIt1, class RandomIt2>
constexpr //< C++20 起
bool equal(RandomIt1 first1, RandomIt1 last1, RandomIt2 first2, RandomIt2 last2,
std::random_access_iterator_tag, std::random_access_iterator_tag)
{
if (last1 - first1 != last2 - first2)
return false;
for (; first1 != last1; ++first1, ++first2)
if (!(*first1 == *first2))
return false;
return true;
}
// 输入迭代器实现（需要手动与 “last2” 进行比较）
template<class InputIt1, class InputIt2>
constexpr //< C++20 起
bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
std::input_iterator_tag, std::input_iterator_tag)
{
for (; first1 != last1 && first2 != last2; ++first1, ++first2)
if (!(*first1 == *first2))
return false;
return first1 == last1 && first2 == last2;
}
}
template<class InputIt1, class InputIt2>
constexpr //< C++20 起
bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
{
details::equal(first1, last1, first2, last2,
typename std::iterator_traits<InputIt1>::iterator_category(),
typename std::iterator_traits<InputIt2>::iterator_category());
}
|
| equal (4) |
namespace detail
{
// 随机访问迭代器实现（可以快速检测范围大小）
template<class RandomIt1, class RandomIt2, class BinaryPred>
constexpr //< C++20 起
bool equal(RandomIt1 first1, RandomIt1 last1,
RandomIt2 first2, RandomIt2 last2, BinaryPred p,
std::random_access_iterator_tag, std::random_access_iterator_tag)
{
if (last1 - first1 != last2 - first2)
return false;
for (; first1 != last1; ++first1, ++first2)
if (!p(*first1, *first2))
return false;
return true;
}
// 输入迭代器实现（需要手动与 “last2” 进行比较）
template<class InputIt1, class InputIt2, class BinaryPred>
constexpr //< C++20 起
bool equal(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, BinaryPred p,
std::input_iterator_tag, std::input_iterator_tag)
{
for (; first1 != last1 && first2 != last2; ++first1, ++first2)
if (!p(*first1, *first2))
return false;
return first1 == last1 && first2 == last2;
}
}
template<class InputIt1, class InputIt2, class BinaryPred>
constexpr //< C++20 起
bool equal(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, BinaryPred p)
{
details::equal(first1, last1, first2, last2, p,
typename std::iterator_traits<InputIt1>::iterator_category(),
typename std::iterator_traits<InputIt2>::iterator_category());
}
|
注解
std::equal 不可应用到由 std::unordered_set、std::unordered_multiset、std::unordered_map 或 std::unordered_multimap 的迭代器构成的范围，因为即使此类容器存储相同的元素，在容器内元素存储的顺序也可能不同。
比较整个容器或字符串视图(C++17 起)是否相等时，针对该类型的 operator== 重载通常是更好的选择。
序列版本的 std::equal 不保证是短路的。例如，如果两个范围的首对元素不相等，剩余元素也可能被被比较。在用 std::memcmp 或实现特有的向量化算法比较范围时可能发生非短路比较。
示例
下面的代码使用 std::equal 来测试字符串是否是回文。
Run this code
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string_view>
constexpr bool is_palindrome(const std::string_view& s)
{
return std::equal(s.cbegin(), s.cbegin() + s.size() / 2, s.crbegin());
}
void test(const std::string_view& s)
{
std::cout << std::quoted(s)
<< (is_palindrome(s) ? " 是" : " 不是")
<< "回文\n";
}
int main()
{
test("radar");
test("hello");
}
输出：
"radar" 是回文
"hello" 不是回文
参阅
(C++20) |
判断两组元素是否相同 (算法函数对象) |
(C++11) |
查找首个满足特定条件的元素 (函数模板 & 算法函数对象) |
(C++20)(C++20)(C++20) |
|
| 以字典序比较两个范围 (函数模板 & 算法函数对象) | |
| 查找两个范围的首个不同之处 (函数模板 & 算法函数对象) | |
(C++20) |
|
| 搜索元素范围的首次出现 (函数模板 & 算法函数对象) | |
(C++20) |
|
| 使用二分搜索找出匹配给定值的元素范围 (函数模板 & 算法函数对象) | |
(C++20) |
|
实现 x == y 的函数对象 (类模板) |