关于VS2008/2010中SORT，stable_sort的比较函数中strict weak ordering

在VS2008/2010中SORT，stable_sort的比较函数是strict weak ordering。当比较的时候出现元素相等的情况是编译器默认必须返回false，而如果在自定义比较函数时，将相等返回true。将会出现invalid operator<的异常。

注意：这种异常在DEVCPP中时不会出现的。

如：

bool cmp(datatype x,datatype y)
{if(x>y)
 return true;
if(x==y)
return true;//x==y,返回true,将出现invalid operator<异常
return false;
}

 

所以当比较出现相等的时候必须返回false;

 

即：

bool cmp(datatype x,datatype y)
{
if(x>y)
return true;
if(x<y)
return false;

return false;//当x==y时，返回false;
}

微软官方说明：http://support.microsoft.com/kb/949171

Assertion Failure When Sorting STL Vector using Custom Predicate

Article ID: 949171 - View products that this article applies to.

Expand all | Collapse all

Source: Microsoft Support

 

RAPID PUBLISHING

RAPID PUBLISHING ARTICLES PROVIDE INFORMATION DIRECTLY FROM WITHIN THE MICROSOFT SUPPORT ORGANIZATION. THE INFORMATION CONTAINED HEREIN IS CREATED IN RESPONSE TO EMERGING OR UNIQUE TOPICS, OR IS INTENDED SUPPLEMENT OTHER KNOWLEDGE BASE INFORMATION.

 

Action

 Sort any STL collection using stable_sort() or sort() with duplicate items using the following custom predicate

bool CustPredicate (int elem1, int elem2 )
{
    if(elem1 > elem2)
        return true;

    if (elem1 < elem2)
        return false;
    return true;
}

 

 

Result

It works fine in Visual C++ 2002 and Visual C++ 2003.
It throws and assertion failed error, "Expression: invalid operator < " in Visual C++  2005 and Visual C++ /2008.

 

Cause

The STL algorithms for stable_sort() and sort() require the binary predicate to be strict weak ordering.

For example:

· Strict: pred(X, X) is always false.

· Weak: If !pred(X, Y) && !pred(Y, X), X==Y.

· Ordering: If pred(X, Y) && pred(Y, Z), then pred(X, Z).

Resolution

Below either of the options will resolve the issue

First Option:-

bool CustPredicate (int elem1, int elem2 )
{
    if(elem1 > elem2)
        return true;

    if (elem1 < elem2)
        return false;

    return false; //Should return false if both the vaules are same
}

 

Second Option:-

bool CustPredicate (int elem1, int elem2 )
{
    return elem1 > elem2;
}

 

 

DISCLAIMER

MICROSOFT AND/OR ITS SUPPLIERS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY, RELIABILITY OR ACCURACY OF THE INFORMATION CONTAINED IN THE DOCUMENTS AND RELATED GRAPHICS PUBLISHED ON THIS WEBSITE (THE “MATERIALS”) FOR ANY PURPOSE. THE MATERIALS MAY INCLUDE TECHNICAL INACCURACIES OR TYPOGRAPHICAL ERRORS AND MAY BE REVISED AT ANY TIME WITHOUT NOTICE.

TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, MICROSOFT AND/OR ITS SUPPLIERS DISCLAIM AND EXCLUDE ALL REPRESENTATIONS, WARRANTIES, AND CONDITIONS WHETHER EXPRESS, IMPLIED OR STATUTORY, INCLUDING BUT NOT LIMITED TO REPRESENTATIONS, WARRANTIES, OR CONDITIONS OF TITLE, NON INFRINGEMENT, SATISFACTORY CONDITION OR QUALITY, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, WITH RESPECT TO THE MATERIALS.

 

Properties

Article ID: 949171 - Last Review: February 13, 2008 - Revision: 1.0

APPLIES TO

• Microsoft Visual Studio 2005 Express Edition
• Microsoft Visual Studio 2005 Professional Edition
• Microsoft Visual Studio 2005 Service Pack 1
• Microsoft Visual Studio 2005 Standard Edition
• Microsoft Visual Studio 2005 Team Suite
• Microsoft Visual Studio 2008 Academic Edition
• Microsoft Visual Studio 2008 Professional Edition
• Microsoft Visual Studio 2008 Standard Edition
• Microsoft Visual Studio Team System 2008 Team Suite