lexicographical_compare() problem.

[cpjust]

While reading Scott Meyers "Effective STL", I decided to try out the case insensitive string compare in Item 35. I can't seem to get the lexicographical_compare() version to work right even though it's identical to the book. Here's my code:

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

char
ToLower( char c )
{
	if ( (c >= 'A') && (c <= 'Z') )
	{
		return c + 32;
	}

	return c;
}

bool
LessNoCase( char c1, char c2 )
{
//	return (_tolower( static_cast<int>( c1 ) ) <
//			_tolower( static_cast<int>( c2 ) ));
	char c3 = ToLower( c1 );
	char c4 = ToLower( c2 );
	return (c3 < c4);
}

bool
CompareNoCase( const string&  first,
			   const string&  second )
{
//	return (stricmp( first.c_str(), second.c_str() ) == 0);

	return lexicographical_compare( first.begin(),  first.end(),
									second.begin(), second.end(),
									LessNoCase );
}

int main()
{
	string lower( "chris" );
	string upper( "CHRIS" );
	string mixed( "ChRiS" );
	string other( "Hello" );

	if ( CompareNoCase( lower, upper ) == false )
	{
		cout << "1. lower and upper don't match!" << endl;
	}

	if ( CompareNoCase( upper, mixed ) == false )
	{
		cout << "2. upper and mixed don't match!" << endl;
	}

	if ( CompareNoCase( mixed, other ) == true )
	{
		cout << "3. mixed and other mated!" << endl;
	}

	cout << endl << "DONE" << endl;

	return 0;
}

I'm using Visual C++ 6.0, and I even tried using STL Port instead of the default VC 6.0 STL and got the same result.
Any ideas?

 

[xwb]

1) You're assuming ASCII. ToLower should actually be

char
ToLower( char c )
{
    if ( (c >= 'A') && (c <= 'Z') )
    {
        return (c - 'A') + 'a';
    }

    return c;
}

2) if 2 things are equal, less than returns false. ComprareNoCase will return false as long as lhs >= rhs

 

[cpjust]

I was using _tolower() but added my own ToLower() for debugging.

lexicographical_compare() doesn't test for equality, it tests for equivalence. i.e.
X and Y have an equivalent ordering if !pr(X, Y) && !pr(Y, X)
and the default predicate for lexicographical_compare() is std::less().

http://msdn.microsoft.com/library/d...lang98/HTML/lib_stl_Algorithm_Conventions.asp

http://msdn.microsoft.com/library/d...html/vclrfAlgorithmLexicographicalcompare.asp

 

[xwb]

I don't think it tests for equivalence. I've just checked Lippman's book. If std::less is provided, then lexicographical_compare returns true if the first pair is lexically less than the second pair. In the first two cases, it is equivalent so the result is false. In the last case "chris" is less than "hello" so it returns true.

I think it does what it says on the box. If you look at your second link, it says

* It finds two corresponding elements unequal, and the result of their comparison is taken as the result of the comparison between sequences.
* No inequalities are found, but one sequence has more elements than the other, and the shorter sequence is considered less than the longer sequence.
* No inequalities are found and the sequences have the same number of elements, and so the sequences are equal and the result of the comparison is false.

Comparing Chris and CHRIS is the 3rd case.
Comparint ChRis and Hello is the 1st case.

 

[cpjust]

Hmmm... That's strange.
What I'm getting is that all 3 of my tests are failing, i.e. It thinks that "chris" != "CHRIS", and "CHRIS" != "ChRiS", and the strangest of all, "ChRiS" == "Hello"!

When I put a breakpoint in my ToLower() function and step through the code I can see that ToLower() is called twice for each element. i.e. For the first test it calls: ToLower( 'c', 'C' ); ToLower( 'C', 'c' ); and so on for each letter, which would make sense if it was testing for equivalence using:
!less( A, B ) && !less( B, A )

I guess I'll write to Scott Meyers and see if he knows what's going on.

 

[xwb]

He does say at the bottom of pg 153 and at the top of pg 154

Like strcmp, lexicographical_compare considers two ranges of equal values to be equal, hence it returns false for such ranges...

 

[cpjust]

Doh! I guess I missed that tiny sentence. You'd think he'd make that a little more prominent...

His code example on 153 is still wrong though since it'll always return the opposite of what it should.

 

[cpjust]

Well no wonder nothing makes sense when using lexicographical_compare()... It has crazy code like this!

const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
return __result != 0 ? (__result < 0) : (__len1 < __len2);

So lexicographical_compare() is obviously a BAD choice for string comparisons. I can't think of anything you actually WOULD use it for though?