Thinking In C++. Volume 2: Practical Programming

  // 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 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.

Removing elements

Because of the genericity of the STL, the concept of removal is a bit constrained. Since elements can only be "removed" via iterators, and iterators can point to arrays, vectors, lists, and so on, it is not safe or reasonable to actually try to destroy the elements that are being removed and to change the size of the input range [first, last). (An array, for example, cannot have its size changed.) So instead, what the STL "remove" functions do is rearrange the sequence so that the "removed" elements are at the end of the sequence, and the "un-removed" elements are at the beginning of the sequence (in the same order that they were before, minus the removed elements—that is, this is a stable operation). Then the function will return an iterator to the "new last" element of the sequence, which is the end of the sequence without the removed elements and the beginning of the sequence of the removed elements. In other words, if new_last is the iterator that is returned from the "remove" function, [first, new_last) is the sequence without any of the removed elements, and [new_last, last) is the sequence of removed elements.

If you are simply using your sequence, including the removed elements, with more STL algorithms, you can just use new_last as the new past-the-end iterator. However, if you’re using a resizable container c (not an array) and you actually want to eliminate the removed elements from the container, you can use erase( ) to do so, for example:^.

c.erase(remove(c.begin(), c.end(), value), c.end());