Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

Comparing ranges

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.


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::iterators). 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

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire