Difference between revisions of "cpp/algorithm/equal"

Revision as of 19:01, 25 March 2024

Defined in header `<algorithm>`
template< class InputIt1, class InputIt2 > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2 );	(1)	(constexpr since C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );	(2)	(since C++17)
template< class InputIt1, class InputIt2, class BinaryPred > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPred p );	(3)	(constexpr since C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPred p );	(4)	(since C++17)
template< class InputIt1, class InputIt2 > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );	(5)	(since C++14) (constexpr since C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(6)	(since C++17)
template< class InputIt1, class InputIt2, class BinaryPred > bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryPred p );	(7)	(since C++14) (constexpr since C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(8)	(since C++17)

Checks whether [first1, last1) and a range starting from first2 are equal:

For overloads (1-4), the second range has std::distance(first1, last1) elements.
For overloads (5-8), the second range is [first2, last2).

1,5) Elements are compared using operator==.

3,7) Elements are compared using the given binary predicate p.

2,4,6,8) Same as (1,3,5,7), but executed according to policy.

These overloads participate in overload resolution only if

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true.	(until C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true.	(since C++20)

first1, last1	-	the first range of the elements to compare
first2, last2	-	the second range of the elements to compare
policy	-	the execution policy to use. See execution policy for details.
p	-	binary predicate which returns true if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following: bool pred(const Type1 &a, const Type2 &b); While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for `Type1` a move is equivalent to a copy(since C++11)). The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to Type1 and Type2 respectively.
Type requirements
- `InputIt1, InputIt2` must meet the requirements of LegacyInputIterator.
- `ForwardIt1, ForwardIt2` must meet the requirements of LegacyForwardIterator.
- `BinaryPred` must meet the requirements of BinaryPredicate.

Return value

1-4) If each corresponding elements in the two ranges are equal, returns true. Otherwise returns false.

5-8) If std::distance(first1, last1) and std::distance(first2, last2) are equal, and each corresponding elements in the two ranges are equal, returns true. Otherwise returns false.

Complexity

Given $\scriptsize N_1$ $N 1$ as std::distance(first1, last1) and $\scriptsize N_2$ $N 2$ as std::distance(first2, last2):

1) At most

N 1

comparisons using operator==.

2)

O(N 1)

comparisons using operator==.

3) At most

N 1

applications of the predicate p.

4)

O(N 1)

applications of the predicate p.

5-8) If the types of first1, last1, first2, and last2 meet the LegacyRandomAccessIterator requirements, and last1 - first1 != last2 - first2 is true, no comparison will be made.

Otherwise, given

N

as

min(N 1,N 2)

:

5) At most

N

comparisons using operator==.

6)

O(N)

comparisons using operator==.

7) At most

N

applications of the predicate p.

8)

O(N)

applications of the predicate p.

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

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 (3)
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 (5)
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 (7)
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()); }

Notes

std::equal should not be used to compare the ranges formed by the iterators from std::unordered_set, std::unordered_multiset, std::unordered_map, or std::unordered_multimap because the order in which the elements are stored in those containers may be different even if the two containers store the same elements.

When comparing entire containers for equality, operator== for the corresponding container are usually preferred.

Example

The following code uses std::equal to test if a string is a palindrome.

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) ? " is" : " is not")
              << " a palindrome\n";
}
 
int main()
{
    test("radar");
    test("hello");
}

Output:

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

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

findfind_iffind_if_not (C++11)	finds the first element satisfying specific criteria (function template) [edit]
lexicographical_compare	returns true if one range is lexicographically less than another (function template) [edit]
mismatch	finds the first position where two ranges differ (function template) [edit]
search	searches for the first occurrence of a range of elements (function template) [edit]
ranges::equal (C++20)	determines if two sets of elements are the same (niebloid)[edit]
equal_to	function object implementing x == y (class template) [edit]
equal_range	returns range of elements matching a specific key (function template) [edit]

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/equal"

Revision as of 19:01, 25 March 2024

Contents

Parameters

Return value

Complexity

Exceptions

Possible implementation

Notes

Example

See also

Navigation

Toolbox

@@ Line 3: / Line 3: @@
 {{dcl begin}}
 {{dcl header|algorithm}}
-{{dcl rev multi|num=1|anchor=1|since1=|until1=c++20|dcl1=
+{{dcla|num=1|notes={{mark constexpr since c++20}}|
 template< class InputIt1, class InputIt2 >
 bool equal( InputIt1 first1, InputIt1 last1,
              InputIt2 first2 );
-|dcl2=
-template< class InputIt1, class InputIt2 >
-constexpr bool equal( InputIt1 first1, InputIt1 last1,
-                      InputIt2 first2 );
 }}
-{{dcl|since=c++17|until=|num=2|1=
+{{dcl|num=2|since=c++17|
 template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
 bool equal( ExecutionPolicy&& policy,
@@ Line 18: / Line 14: @@
              ForwardIt2 first2 );
 }}
-{{dcl rev multi|num=3|anchor=3|since1=|until1=c++20|dcl1=
+{{dcla|num=3|notes={{mark constexpr since c++20}}|
-template< class InputIt1, class InputIt2, class BinaryPredicate >
+template< class InputIt1, class InputIt2, class BinaryPred >
 bool equal( InputIt1 first1, InputIt1 last1,
-             InputIt2 first2,
+             InputIt2 first2, BinaryPred p );
-            BinaryPredicate p );
-|dcl2=
-template< class InputIt1, class InputIt2, class BinaryPredicate >
-constexpr bool equal( InputIt1 first1, InputIt1 last1,
-                      InputIt2 first2,
-                      BinaryPredicate p );
 }}
-{{dcl|since=c++17|num=4|1=
+{{dcl|num=4|since=c++17|
 template< class ExecutionPolicy,
-           class ForwardIt1, class ForwardIt2, class BinaryPredicate >
+           class ForwardIt1, class ForwardIt2, class BinaryPred >
 bool equal( ExecutionPolicy&& policy,
              ForwardIt1 first1, ForwardIt1 last1,
-             ForwardIt2 first2,
+             ForwardIt2 first2, BinaryPred p );
-            BinaryPredicate p );
 }}
-{{dcl rev multi|num=5|since1=c++14|until1=c++20|dcl1=
+{{dcla|num=5|since=c++14|notes={{mark constexpr since c++20}}|
 template< class InputIt1, class InputIt2 >
 bool equal( InputIt1 first1, InputIt1 last1,
              InputIt2 first2, InputIt2 last2 );
-|dcl2=
-template< class InputIt1, class InputIt2 >
-constexpr bool equal( InputIt1 first1, InputIt1 last1,
-                      InputIt2 first2, InputIt2 last2 );
 }}
-{{dcl|since=c++17|num=6|1=
+{{dcl|num=6|since=c++17|
 template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
 bool equal( ExecutionPolicy&& policy,
@@ Line 52: / Line 37: @@
              ForwardIt2 first2, ForwardIt2 last2 );
 }}
-{{dcl rev multi|num=7|since1=c++14|until1=c++20|dcl1=
+{{dcla|num=7|since=c++14|notes={{mark constexpr since c++20}}|
-template< class InputIt1, class InputIt2, class BinaryPredicate >
+template< class InputIt1, class InputIt2, class BinaryPred >
 bool equal( InputIt1 first1, InputIt1 last1,
-             InputIt2 first2, InputIt2 last2,
+             InputIt2 first2, InputIt2 last2, BinaryPred p );
-            BinaryPredicate p );
-|dcl2=
-template< class InputIt1, class InputIt2, class BinaryPredicate >
-constexpr bool equal( InputIt1 first1, InputIt1 last1,
-                      InputIt2 first2, InputIt2 last2,
-                      BinaryPredicate p );
 }}
-{{dcl|since=c++17|num=8|1=
+{{dcl|num=8|since=c++17|
 template< class ExecutionPolicy,
-           class ForwardIt1, class ForwardIt2, class BinaryPredicate >
+           class ForwardIt1, class ForwardIt2, class BinaryPred >
 bool equal( ExecutionPolicy&& policy,
              ForwardIt1 first1, ForwardIt1 last1,
-             ForwardIt2 first2, ForwardIt2 last2,
+             ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );
-            BinaryPredicate p );
 }}
 {{dcl end}}
-@1,3@ Returns {{c|true}} if the range {{range|first1|last1}} is equal to the range {{range|first2|first2 + (last1 - first1)}}, and {{c|false}} otherwise.
+Checks whether {{range|first1|last1}} and a range starting from {{c|first2}} are equal:
-@5,7@ Returns {{c|true}} if the range {{range|first1|last1}} is equal to the range {{range|first2|last2}}, and {{c|false}} otherwise.
+* For overloads {{v|1-4}}, the second range has {{c|std::distance(first1, last1)}} elements.
+* For overloads {{v|5-8}}, the second range is {{range|first2|last2}}.
-@2,4,6,8@ Same as {{v|1,3,5,7}}, but executed according to {{c|policy}}. {{cpp/algorithm/parallel overload precondition|plural=true}}
+@1,5@ Elements are compared using {{c/core|1=operator==}}.
-Two ranges are considered equal if they have the same number of elements and, for every iterator {{tt|i}} in the range {{range|first1|last1}}, {{c|*i}} equals {{c|*(first2 + (i - first1))}}. The overloads {{v|1,2,5,6}} use {{c|1=operator==}} to determine if two elements are equal, whereas overloads {{v|3,4,7,8}} use the given binary predicate {{c|p}}.
+@3,7@ Elements are compared using the given binary predicate {{c|p}}.
+@2,4,6,8@ Same as {{v|1,3,5,7}}, but executed according to {{c|policy}}.
+@@{{cpp/algorithm/parallel overload precondition|plural=yes}}
 ===Parameters===
@@ Line 89: / Line 71: @@
 {{par req named|InputIt1, InputIt2|InputIterator}}
 {{par req named|ForwardIt1, ForwardIt2|ForwardIterator}}
+{{par req named|BinaryPred|BinaryPredicate}}
 {{par end}}
 ===Return value===
-@5-8@ If the length of the range {{range|first1|last1}} does not equal the length of the range {{range|first2|last2}}, returns {{c|false}}.
+@1-4@ If each corresponding elements in the two ranges are equal, returns {{c|true}}. Otherwise returns {{c|false}}.
-If the elements in the two ranges are equal, returns {{c|true}}.
+@5-8@ If {{c|std::distance(first1, last1)}} and {{c|std::distance(first2, last2)}} are equal, and each corresponding elements in the two ranges are equal, returns {{c|true}}. Otherwise returns {{c|false}}.
-Otherwise returns {{c|false}}.
+===Complexity===
+Given {{mathjax-or|\(\scriptsize N_1\)|N{{su|b=1}}}} as {{c|std::distance(first1, last1)}} and {{mathjax-or|\(\scriptsize N_2\)|N{{su|b=2}}}} as {{c|std::distance(first2, last2)}}:
-===Notes===
+@1@ At most {{mathjax-or|\(\scriptsize N_1\)|N{{su|b=1}}}} comparisons using {{c/core|1=operator==}}.
-{{tt|std::equal}} should not be used to compare the ranges formed by the iterators from {{lc|std::unordered_set}}, {{lc|std::unordered_multiset}}, {{lc|std::unordered_map}}, or {{lc|std::unordered_multimap}} because the order in which the elements are stored in those containers may be different even if the two containers store the same elements.
+@2@ {{mathjax-or|\(\scriptsize O(N_1)\)|O(N{{su|b=1}})}} comparisons using {{c/core|1=operator==}}.
+@3@ At most {{mathjax-or|\(\scriptsize N_1\)|N{{su|b=1}}}} applications of the predicate {{c|p}}.
+@4@ {{mathjax-or|\(\scriptsize O(N_1)\)|O(N{{su|b=1}})}} applications of the predicate {{c|p}}.
-When comparing entire containers for equality, {{tt|1=operator==}} for the corresponding container are usually preferred.
+@5-8@ If the types of {{c|first1}}, {{c|last1}}, {{c|first2}}, and {{c|last2}} meet the {{named req|RandomAccessIterator}} requirements, and {{c|1=last1 - first1 != last2 - first2}} is {{c|true}}, no comparison will be made.
+@@ Otherwise, given {{mathjax-or|\(\scriptsize N\)|N}} as {{mathjax-or|\(\scriptsize min(N_1,N_2)\)|min(N{{su|b=1}},N{{su|b=2}})}}:
-===Complexity===
+:@5@ At most {{mathjax-or|\(\scriptsize N\)|N}} comparisons using {{c/core|1=operator==}}.
-@1,3@ At most {{c|last1}} - {{c|first1}} applications of the predicate.
+:@6@ {{mathjax-or|\(\scriptsize O(N)\)|O(N)}} comparisons using {{c/core|1=operator==}}.
-@5,7@ At most min({{c|last1}} - {{c|first1}}, {{c|last2}} - {{c|first2}}) applications of the predicate.<br>
+:@7@ At most {{mathjax-or|\(\scriptsize N\)|N}} applications of the predicate {{c|p}}.
-However, if {{tt|InputIt1}} and {{tt|InputIt2}} meet the requirements of {{named req|RandomAccessIterator}} and {{c|1=last1 - first1 != last2 - first2}} then no applications of the predicate are made (size mismatch is detected without looking at any elements).
+:@8@ {{mathjax-or|\(\scriptsize O(N)\)|O(N)}} applications of the predicate {{c|p}}.
-@2,4,6,8@ Same, but the complexity is specified as O(x), rather than "at most x".
 ===Exceptions===
-{{cpp/algorithm/parallel_exceptions_reporting_behavior|singular=no}}
+{{cpp/algorithm/parallel exceptions reporting behavior|singular=no}}
 ===Possible implementation===
@@ Line 122: / Line 106: @@
          if (!(*first1 == *first2))
              return false;
      return true;
 }
 |title2=equal (3)|ver2=3|2=
-template<class InputIt1, class InputIt2, class BinaryPredicate>
+template<class InputIt1, class InputIt2, class BinaryPred>
 constexpr //< since C++20
 bool equal(InputIt1 first1, InputIt1 last1,
-            InputIt2 first2, BinaryPredicate p)
+            InputIt2 first2, BinaryPred p)
 {
      for (; first1 != last1; ++first1, ++first2)
          if (!p(*first1, *first2))
              return false;
      return true;
+}
+|title3=equal (5)|ver3=5|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());
+}
+|title4=equal (7)|ver4=7|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());
 }
 }}
+===Notes===
+{{tt|std::equal}} should not be used to compare the ranges formed by the iterators from {{lc|std::unordered_set}}, {{lc|std::unordered_multiset}}, {{lc|std::unordered_map}}, or {{lc|std::unordered_multimap}} because the order in which the elements are stored in those containers may be different even if the two containers store the same elements.
+When comparing entire containers for equality, {{c/core|1=operator==}} for the corresponding container are usually preferred.
 ===Example===