std::equal - cppreference.com (original) (raw)

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 all following conditions are satisfied:

Contents

• 1 Parameters
• 2 Return value
• 3 Complexity
• 4 Exceptions
• 5 Possible implementation
• 6 Notes
• 7 Example
• 8 See also

[edit] Parameters

[edit] 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.

[edit] Complexity

Given \(\scriptsize N_1\)N1 as std::distance(first1, last1) and \(\scriptsize N_2\)N2 as std::distance(first2, last2):

1. At most \(\scriptsize N_1\)N1 comparisons using operator==.

2. \(\scriptsize O(N_1)\)O(N1) comparisons using operator==.

3. At most \(\scriptsize N_1\)N1 applications of the predicate p.

4. \(\scriptsize O(N_1)\)O(N1) applications of the predicate p.

5-8) If InputIt1 and InputIt2 are both LegacyRandomAccessIterator, and last1 - first1 != last2 - first2 is true, no comparison will be made.

Otherwise, given \(\scriptsize N\)N as \(\scriptsize \min(N_1,N_2)\)min(N1,N2):

1. At most \(\scriptsize N\)N comparisons using operator==.

2. \(\scriptsize O(N)\)O(N) comparisons using operator==.

3. At most \(\scriptsize N\)N applications of the predicate p.

4. \(\scriptsize O(N)\)O(N) applications of the predicate p.

[edit] 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.

[edit] Possible implementation

[edit] 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 or string views(since C++17) for equality, operator== for the corresponding type are usually preferred.

Sequential std::equal is not guaranteed to be short-circuit. E.g. if the first pair elements of both ranges do not compare equal, the rest of elements may also be compared. Non-short-circuit comparison may happen when the ranges are compared with std::memcmp or implementation-specific vectorized algorithms.

[edit] Example

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

#include #include #include #include   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

[edit] See also