Comparing Ranges | Algorithms

Problem

You have two ranges, and you need to compare them for equality or you need to see which one comes first based on some ordering on the elements.

Solution

Depending on what kind of comparison you want to do, use one of the standard algorithms equal, lexicographical_compare, or mismatch, defined in . Example 7-4 shows several of them in action.

Example 7-4. Different kinds of comparisons

#include 
#include 
#include 
#include 
#include "utils.h"

using namespace std;
using namespace utils;

int main( ) {

 vector vec1, vec2;

 vec1.push_back("Charles");
 vec1.push_back("in");
 vec1.push_back("Charge");

 vec2.push_back("Charles");
 vec2.push_back("in");
 vec2.push_back("charge"); // Note the small "c"

 if (equal(vec1.begin( ), vec1.end( ), vec2.begin( ))) {
 cout << "The two ranges are equal!" << endl;
 } else {
 cout << "The two ranges are NOT equal!" << endl;
 }

 string s1 = "abcde";
 string s2 = "abcdf";
 string s3 = "abc";

 cout << boolalpha // Show bools as "true" or "false"
 << lexicographical_compare(s1.begin( ), s1.end( ),
 s1.begin( ), s1.end( )) << endl;
 cout << lexicographical_compare(s1.begin( ), s1.end( ),
 s2.begin( ), s2.end( )) << endl;
 cout << lexicographical_compare(s2.begin( ), s2.end( ),
 s1.begin( ), s1.end( )) << endl;
 cout << lexicographical_compare(s1.begin( ), s1.end( ),
 s3.begin( ), s3.end( )) << endl;
 cout << lexicographical_compare(s3.begin( ), s3.end( ),
 s1.begin( ), s1.end( )) << endl;

 pair iters =
 mismatch(s1.begin( ), s1.end( ), s2.begin( ));

 cout << "first mismatch = " << *(iters.first) << endl;
 cout << "second mismatch = " << *(iters.second) << endl;
}

The output of Example 7-4 looks like this:

The two sequences are NOT equal!
false
true
false
false
true
first mismatch = e
second mismatch = f

Discussion

Use equal to compare two sequences for equality. It takes three or four arguments, depending on the version you use. Here's how equal is declared:

bool equal(In1 first1, In1 last1, In2 first2);
bool equal(In1 first1, In1 last1, In2 first2, BinPred pred);

equal compares each element between first1 and last1 with each element starting at first2 using operator==. If you supply pred, equal uses that to test equality instead. Ensure that the sequences each have the same length before calling equal; it assumes the second range is at least as long as the first, and if it isn't, the behavior is undefined.

If you want to know more about how or where two sequences differ, you can use lexicographical_compare or mismatch. lexicographical_compare compares two sequences and returns true if the first is lexicographically less than the second, which means that each pair of elements in the two sequences is compared using the < operator. The declaration of lexicographical_compare looks like this:

bool lexicographical_compare(In1 first1, In1 last1,
 In2 first2, In2 last2);
bool lexicographical_compare(In1 first1, In1 last1,
 In2 first2, In2 last2,
 Compare comp);

As soon as operator< returns true, or the first sequence ends before the second, true is returned. Otherwise, false is returned. Consider the character sequences in Example 7-4:

string s1 = "abcde";
string s2 = "abcdf";
string s3 = "abc";

lexicographical_compare(s1.begin( ), s1.end( ), // abcde < abcde
 s1.begin( ), s1.end( )); // = false
lexicographical_compare(s1.begin( ), s1.end( ), // abcde < abcdf
 s2.begin( ), s2.end( )); // = true
lexicographical_compare(s2.begin( ), s2.end( ), // abcdf < abcde
 s1.begin( ), s1.end( )); // = false
lexicographical_compare(s1.begin( ), s1.end( ), // abcde < abc
 s3.begin( ), s3.end( )); // = false
lexicographical_compare(s3.begin( ), s3.end( ), // abc < abcde
 s1.begin( ), s1.end( )); // = true

The complexity of lexicographical_compare is linear and will do a number of comparisons equal to the minimum of the two sequence lengths, or until the first time an element in one of the sequences is less than the corresponding element in the other. The comparisons are implemented entirely using operator<, so if iter1 and iter2 are iterators into the two sequences, the comparison stops as soon as *iter1 < *iter2 or *iter2 < *iter1.

mismatch will tell you where two sequences differ. Its declaration is a little different than equal and lexicographical_compare, though, because it returns a pair<> of iterators instead of a bool. Here it is:

pair mismatch(In1 first1, In1 last1, In2 first2);
pair mismatch(In1 first1, In1 last1, In2 first2, BinPred);

The two iterators returned point to the differing elements in each of the sequences. Consider Example 7-4:

string s1 = "abcde";
string s2 = "abcdf";
pair iters =
 mismatch(s1.begin( ), s1.end( ), s2.begin( ));

cout << "first mismatch = " << *(iters.first) << '
'; // 'e'
cout << "second mismatch = " << *(iters.second) << '
';// 'f'

You have to ensure that the second range is at least as long as the first. If the second sequence is shorter than the first, mismatch has no way to know it and will continue making comparisons to elements past the end of the second sequence, which has undefined behavior if it extends past the end of the second sequence. Additionally, if there is no mismatch, the first iterator will be pointing to last1, which may not be valid (e.g., if you passed in end( ) as last1).

You may have noticed from the declarations of each of these algorithms that the types of the iterators for each of the two sequences are different. This means that the two sequences can be containers of different types, so long as the type of the element those iterators refer to have operator< defined for them. For example, you may want to compare a string to a vector:

string s = "Coke";
vector v;

v.push_back('c');
v.push_back('o');
v.push_back('k');
v.push_back('e');

std::cout << std::lexicographical_compare(s.begin( ), s.end( ),
 v.begin( ), v.end( )) << '
';

This compares each of the characters in the two sequences without regard for the type of container that holds them.

The C++ standard library provides several different ways to compare sequences. If none of these suits your needs, look at the source code for them; it will provide a good example of how you can write your own efficient, generic algorithm.