std::equal

Определено в заголовочном файле `<algorithm>`
template< class InputIt1, class InputIt2 > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2 );	(1)	(constexpr начиная с C++20)
template< class InputIt1, class InputIt2, class BinaryPred > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPred p );	(2)	(constexpr начиная с C++20)
template< class InputIt1, class InputIt2 > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );	(3)	(начиная с C++14) (constexpr начиная с C++20)
template< class InputIt1, class InputIt2, class BinaryPred > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryPred p );	(4)	(начиная с C++14) (constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );	(5)	(начиная с C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPred p );	(6)	(начиная с C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(7)	(начиная с C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(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:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Параметры

first1, last1	-	пара итераторов, определяющих первый целевой диапазон
first2, last2	-	пара итераторов, определяющих второй целевой диапазон
p	-	бинарный предикат, возвращающий `true`, если элементы следует считать равными. Сигнатура функции-предиката должна быть эквивалентна следующей: boolpred(constType1&a,constType2&b); Хотя сигнатура не обязана содержать `const &`, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1 &` не допускается, как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию(начиная с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объекты типов InputIt1 и InputIt2 можно было разыменовать, а затем неявно преобразовать соответственно в Type1 и Type2.
policy	-	политика выполнения, которую следует использовать
Требования к типам
-`InputIt1, InputIt2` должен соответствовать требованиям LegacyInputIterator.
-`ForwardIt1, ForwardIt2` должен соответствовать требованиям LegacyForwardIterator.
-`BinaryPred` должен соответствовать требованиям BinaryPredicate.

Возвращаемое значение

Если два целевых диапазона имеют одинаковый размер и каждый соответствующий элемент в обоих диапазонах равен, возвращает true. В противном случае возвращает false.

Сложность

Пусть \(\scriptsize N_1\)N₁ — это std::distance(first1, last1), а \(\scriptsize N_2\)N₂ — это std::distance(first2, last2):

1) Не более \(\scriptsize N_1\)N₁ сравнений с помощью operator==.

2) Не более \(\scriptsize N_1\)N₁ применений p.

3) Не более \(\scriptsize \min(N_1,N_2)\)min(N₁,N₂) сравнений с помощью operator==.

4) Не более \(\scriptsize \min(N_1,N_2)\)min(N₁,N₂) применений p.

5) \(\scriptsize \mathcal{O}(N_1)\)𝓞(N₁) сравнений с помощью operator==.

6) \(\scriptsize \mathcal{O}(N_1)\)𝓞(N₁) применений p.

7) \(\scriptsize \mathcal{O}(\min(N_1,N_2))\)𝓞(min(N₁,N₂)) сравнений с помощью operator==.

8) \(\scriptsize \mathcal{O}(\min(N_1,N_2))\)𝓞(min(N₁,N₂)) применений p.

Если и InputIt1, и InputIt2 (или ForwardIt1 и ForwardIt2 для параллельных перегрузок) соответствуют требованиям LegacyRandomAccessIterator, а \(\scriptsize N_1 \neq N_2\)N₁≠N₂, сравнения не выполняются.

Исключения

5-8) В ходе выполнения:

Если требуемые для распараллеливания временные ресурсы памяти недоступны, выбрасывается std::bad_alloc.
Если при доступе к объектам через аргумент алгоритма возникает необработанное исключение, поведение определяется политикой выполнения (для стандартных политик вызывается std::terminate).

Возможная реализация

equal (1)
template<class InputIt1, class InputIt2> constexpr //< since 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 //< since 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 { // random-access iterator implementation (allows quick range size detection) template<class RandomIt1, class RandomIt2> constexpr //< since 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; } // input iterator implementation (needs to manually compare with “last2”) template<class InputIt1, class InputIt2> constexpr //< since 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 //< since 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 { // random-access iterator implementation (allows quick range size detection) template<class RandomIt1, class RandomIt2, class BinaryPred> constexpr //< since 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; } // input iterator implementation (needs to manually compare with “last2”) template<class InputIt1, class InputIt2, class BinaryPred> constexpr //< since 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 //< since 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, поскольку порядок хранения элементов в этих контейнерах может различаться, даже если в обоих контейнерах хранятся одинаковые элементы.

При сравнении на равенство целых контейнеров или строковых представлений string view(начиная с C++17) обычно предпочтительнее использовать operator== соответствующего типа.

Последовательное std::equal не гарантирует досрочного завершения. Например, если первые элементы обеих диапазонов не равны, могут быть также сравнены остальные элементы. Сравнение без досрочного завершения может происходить, когда диапазоны сравниваются с помощью std::memcmp или векторизованных алгоритмов, зависящих от реализации.

Пример

В следующем коде используется std::equal, чтобы проверить, является ли строка палиндромом.

#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) ? " is" : " is not")
              << " a palindrome\n";
}

int main()
{
    test("radar");
    test("hello");
}

Вывод:

"radar" is a palindrome
"hello" is not a palindrome

См. также

ranges::equal (C++20)	определяет, одинаковы ли два набора элементов (функциональный объект алгоритма)
findfind_iffind_if_not (C++11)	находит первый элемент, удовлетворяющий заданным критериям (шаблон функции и функциональный объект алгоритма)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
lexicographical_compare	лексикографически сравнивает два диапазона (шаблон функции и функциональный объект алгоритма)
ranges::lexicographical_compare (C++20)
mismatch	находит первую позицию, в которой два диапазона различаются (шаблон функции и функциональный объект алгоритма)
ranges::mismatch (C++20)
search	ищет первое вхождение диапазона элементов (шаблон функции и функциональный объект алгоритма)
ranges::search (C++20)
equal_range	находит диапазон элементов, соответствующих заданному значению, с помощью двоичного поиска (шаблон функции и функциональный объект алгоритма)
ranges::equal_range (C++20)
equal_to	функциональный объект, реализующий `x == y` (шаблон класса)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/equal