Thinking in C++ Vol 2 - Practical Programming |

Prev |
Home |
Next |

These algorithms provide ways to compare two ranges. At
first glance, the operations they perform seem similar to the **search( )**
function. However, **search( )** tells you where the second sequence
appears within the first, and **equal( )** and **lexicographical_compare( )
**simply tell you how two sequences compare. On the other hand, **mismatch( )**
does tell you where the two sequences go out of sync, but those sequences must
be exactly the same length.

bool **equal**(InputIterator first1, InputIterator last1,

InputIterator first2);

bool **equal**(InputIterator first1, InputIterator last1,

InputIterator first2 BinaryPredicate binary_pred);

In both these functions, the first range is the typical one,
**[first1, last1)**. The second range starts at **first2**, but there is
no last2 because its length is determined by the length of the first range.
The **equal( )** function returns true if both ranges are exactly the
same (the same elements in the same order). In the first case, the **operator==**
performs the comparison, and in the second case **binary_pred** decides if
two elements are the same.

bool **lexicographical_compare**(InputIterator1 first1,

InputIterator1 last1, InputIterator2 first2,

InputIterator2 last2);

bool **lexicographical_compare**(InputIterator1 first1,

InputIterator1 last1, InputIterator2 first2,

InputIterator2 last2, BinaryPredicate binary_pred);

These two functions determine if the first range is
lexicographically less than the second. (They return **true** if range 1
is less than range 2, and false otherwise.) *Lexicographical comparison*,
or dictionary comparison, means that the comparison is done in the same way that
we establish the order of strings in a dictionary: one element at a time. The
first elements determine the result if these elements are different, but if
they re equal, the algorithm moves on to the next elements and looks at those,
and so on until it finds a mismatch. At that point, it looks at the elements,
and if the element from range 1 is less than the element from range two, **lexicographical_compare( )**
returns **true**; otherwise, it returns **false**. If it gets all the way
through one range or the other (the ranges may be different lengths for this
algorithm) without finding an inequality, range 1 is *not *less than range
2, so the function returns **false**.

If the two ranges are different lengths, a missing element
in one range acts as one that precedes an element that exists in the other
range, so abc precedes abcd. If the algorithm reaches the end of one of the
ranges without a mismatch, then the shorter range comes first. In that case, if
the shorter range is the first range, the result is **true**, otherwise it
is **false**.

In the first version of the function, **operator<**
performs the comparisons, and in the second version, **binary_pred** is used.

pair<InputIterator1,
InputIterator2>

**mismatch**(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2);

pair<InputIterator1, InputIterator2>

**mismatch**(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, BinaryPredicate binary_pred);

As in **equal( )**, the length of both ranges is
exactly the same, so only the first iterator in the second range is necessary,
and the length of the first range is used as the length of the second range.
Whereas **equal( )** just tells you whether the two ranges are the
same, **mismatch( )** tells you where they begin to differ. To
accomplish this, you must be told (1) the element in the first range where the
mismatch occurred and (2) the element in the second range where the mismatch
occurred. These two iterators are packaged together into a **pair** object
and returned. If no mismatch occurs, the return value is **last1** combined
with the past-the-end iterator of the second range. The **pair** template
class is a **struct** with two elements denoted by the member names **first**
and **second** and is defined in the **<utility>** header.

As in **equal( )**, the first function tests for
equality using **operator==** while the second one uses **binary_pred**.

#### Example

Because the Standard C++ **string** class is built like a
container (it has **begin( )** and **end( )** member functions
that produce objects of type **string::iterator**), it can be used to
conveniently create ranges of characters to test with the STL comparison
algorithms. However, note that **string **has a fairly complete set of
native operations, so look at the **string** class before using the STL
algorithms to perform operations.

//: C06:Comparison.cpp

// The STL range comparison algorithms.

#include <algorithm>

#include <functional>

#include <string>

#include <vector>

#include "PrintSequence.h"

using namespace std;

int main() {

// Strings provide a convenient way to create

// ranges of characters, but you should

// normally look for native string operations:

string s1("This is a test");

string s2("This is a Test");

cout << "s1: " << s1 <<
endl << "s2: " << s2 << endl;

cout << "compare s1 & s1: "

<< equal(s1.begin(), s1.end(), s1.begin())
<< endl;

cout << "compare s1 & s2: "

<< equal(s1.begin(), s1.end(), s2.begin())
<< endl;

cout << "lexicographical_compare s1 &
s1: "

<< lexicographical_compare(s1.begin(),
s1.end(),

s1.begin(), s1.end()) << endl;

cout << "lexicographical_compare s1 &
s2: "

<< lexicographical_compare(s1.begin(),
s1.end(),

s2.begin(), s2.end()) << endl;

cout << "lexicographical_compare s2 &
s1: "

<< lexicographical_compare(s2.begin(),
s2.end(),

s1.begin(), s1.end()) << endl;

cout << "lexicographical_compare shortened
"

"s1 & full-length s2: "
<< endl;

string s3(s1);

while(s3.length() != 0) {

bool result = lexicographical_compare(

s3.begin(), s3.end(), s2.begin(),s2.end());

cout << s3 << endl << s2 <<
", result = "

<< result << endl;

if(result == true) break;

s3 = s3.substr(0, s3.length() - 1);

}

pair<string::iterator, string::iterator> p =

mismatch(s1.begin(), s1.end(), s2.begin());

print(p.first, s1.end(), "p.first",
"");

print(p.second, s2.end(),
"p.second","");

} ///:~

Note that the only difference between **s1** and **s2**
is the capital T in **s2** s Test. Comparing **s1** and **s1** for
equality yields **true**, as expected, while **s1** and **s2** are not
equal because of the capital T .

To understand the output of the **lexicographical_compare( )**
tests, remember two things: first, the comparison is performed
character-by-character, and second, on our platform capital letters precede
lowercase letters. In the first test, **s1** is compared to **s1**. These
are exactly equivalent. One is *not* lexicographically less than the other
(which is what the comparison is looking for), and thus the result is **false**.
The second test is asking does **s1** precede **s2**? When the
comparison gets to the t in test , it discovers that the lowercase t in **s1**
is greater than the uppercase T in **s2**, so the answer is again **false**.
However, if we test to see whether **s2** precedes **s1**, the answer is **true**.

To further examine lexicographical comparison, the next test
in this example compares **s1** with **s2** again (which returned **false**
before). But this time it repeats the comparison, trimming one character off
the end of **s1** (which is first copied into **s3**) each time through
the loop until the test evaluates to **true**. What you ll see is that, as
soon as the uppercase T is trimmed off **s3** (the copy of **s1**), the
characters, which are exactly equal up to that point, no longer count. Because **s3**
is shorter than **s2**, it lexicographically precedes **s2**.

The final test uses** mismatch( )**. To capture the
return value, create the appropriate **pair p**, constructing the template
using the iterator type from the first range and the iterator type from the
second range (in this case, both **string::iterator**s). To print the
results, the iterator for the mismatch in the first range is **p.first**,
and for the second range is **p.second**. In both cases, the range is
printed from the mismatch iterator to the end of the range so you can see
exactly where the iterator points.

Thinking in C++ Vol 2 - Practical Programming |

Prev |
Home |
Next |