16.3.2. equal, mismatch and lexicographical_compare
Figure 16.2 demonstrates comparing sequences of values for equality using algorithms equal, mismatch and lexicographical_compare.
1 // Fig. 16.2: fig16_02.cpp
2 // Algorithms equal, mismatch and lexicographical_compare.
3 #include <iostream>
4 #include <algorithm> // algorithm definitions
5 #include <array> // array class-template definition
6 #include <iterator> // ostream_iterator
7 using namespace std;
8
9 int main()
10 {
11 const size_t SIZE = 10;
12 array< int, SIZE > a1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
13 array< int, SIZE > a2( a1 ); // initializes a2 with copy of a1
14 array< int, SIZE > a3 = { 1, 2, 3, 4, 1000, 6, 7, 8, 9, 10 };
15 ostream_iterator< int > output( cout, " " );
16
17 cout << "a1 contains: ";
18 copy( a1.cbegin(), a1.cend(), output );
19 cout << "
a2 contains: ";
20 copy( a2.cbegin(), a2.cend(), output );
21 cout << "
a3 contains: ";
22 copy( a3.cbegin(), a3.cend(), output );
23
24 // compare a1 and a2 for equality
25 bool result = equal( a1.cbegin(), a1.cend(), a2.cbegin() );
26 cout << "
a1 " << ( result ? "is" : "is not" )
27 << " equal to a2.
";
28
29 // compare a1 and a3 for equality
30 result = equal( a1.cbegin(), a1.cend(), a3.cbegin() );
31 cout << "a1 " << ( result ? "is" : "is not" ) << " equal to a3.
";
32
33 // check for mismatch between a1 and a3
34 auto location = mismatch( a1.cbegin(), a1.cend(), a3.cbegin() );
35 cout << "
There is a mismatch between a1 and a3 at location "
36 << ( location.first - a1.begin() ) << "
where a1 contains "
37 << *location.first << " and a3 contains " << *location.second
38 << "
";
39
40 char c1[ SIZE ] = "HELLO";
41 char c2[ SIZE ] = "BYE BYE";
42
43 // perform lexicographical comparison of c1 and c2
44 result = lexicographical_compare(
45 begin( c1 ), end( c1 ), begin( c2 ), end( c2 ) );
46 cout << c1 << ( result ? " is less than " :
47 " is greater than or equal to " ) << c2 << endl;
48 } // end main
a1 contains: 1 2 3 4 5 6 7 8 9 10
a2 contains: 1 2 3 4 5 6 7 8 9 10
a3 contains: 1 2 3 4 1000 6 7 8 9 10
a1 is equal to a2.
a1 is not equal to a3.
There is a mismatch between a1 and a3 at location 4
where a1 contains 5 and a3 contains 1000
HELLO is greater than or equal to BYE BYE
Fig. 16.2. Algorithms equal, mismatch and lexicographical_compare.
equal Algorithm
Line 25 uses the equal algorithm to compare two sequences of values for equality. The second sequence must contain at least as many elements as the first—equal returns false if the sequences are not of the same length. The == operator (whether built-in or overloaded) performs the element comparisons. In this example, the elements in a1 from a1.cbegin() up to, but not including, a1.cend() are compared to the elements in a2 starting from a2.cbegin(). In this example, a1 and a2 are equal. The three iterator arguments must be at least input iterators (i.e., they can be used for input from a sequence in the forward direction). Line 30 uses function equal to compare a1 and a3, which are not equal.
equal Algorithm with Binary Predicate Function
Another version of equal takes a binary predicate function as a fourth parameter. The binary predicate function receives the two elements being compared and returns a bool value indicating whether the elements are equal. This can be useful in sequences that store objects or pointers to values rather than actual values, because you can define one or more comparisons. For example, you can compare Employee objects for age, social security number, or location rather than comparing entire objects. You can compare what pointers refer to rather than comparing the pointer values (i.e., the addresses stored in the pointers).
mismatch Algorithm
Lines 34 calls the mismatch algorithm to compare two sequences of values. The algorithm returns a pair of iterators indicating the location in each sequence of the mismatched elements. If all the elements match, the two iterators in the pair are equal to the end iterator for each sequence. The three iterator arguments must be at least input iterators. We infer the type of the pair object location with C++11’s auto keyword (line 34). Line 36 determines the actual location of the mismatch in the arrays with the expression location.first - a1.begin(), which evaluates to the number of elements between the iterators (this is analogous to pointer arithmetic; Chapter 8). This corresponds to the element number in this example, because the comparison is performed from the beginning of each array. As with equal, there is another version of mismatch that takes a binary predicate function as a fourth parameter.
lexicographical_compare Algorithm
Lines 44–45 use the lexicographical_compare algorithm to compare the contents of two char built-in arrays. This algorithm’s four iterator arguments must be at least input iterators. As you know, pointers into built-in arrays are random-access iterators. The first two iterator arguments specify the range of locations in the first sequence. The last two specify the range of locations in the second sequence. Once again, we use the C++11 begin and end functions to determine the range of elements for each built-in array. While iterating through the sequences, the lexicographical_compare checks if the element in the first sequence is less than the corresponding element in the second sequence. If so, the algorithm returns true. If the element in the first sequence is greater than or equal to the element in the second sequence, the algorithm returns false. This algorithm can be used to arrange sequences lexicographically. Typically, such sequences contain strings.