Q265109: BUG: The STL list::sort() Function Doesn’t Sort List of Pointers

Article: Q265109
Product(s): Microsoft C Compiler
Version(s): 
Operating System(s): 
Keyword(s): kbtemplate kbSTL kbVC600bug kbDSupport kbGrpDSVCCompiler
Last Modified: 03-MAY-2001

-------------------------------------------------------------------------------
The information in this article applies to:

- The C/C++ Compiler (CL.EXE) 
-------------------------------------------------------------------------------

SYMPTOMS
========

The Standard Template Library (STL) list::sort function doesn't sort a list of
pointers when a predicate function is defined for sorting.

CAUSE
=====

The Microsoft Developer Network (MSDN) documentation for the list::sort function
states that, if a translator doesn't support member function templates, the
following template

  template <class Pred>;
     void sort(Pred pr);

is replaced by:

  void sort(greater<T> pr);

You can specify the predicate function for sorting, but it will always call the
greater function.

RESOLUTION
==========

Override struct greater<T> and specify your comparison function for
sorting. See the workaround in the "More Information" section for details.


STATUS
======

Microsoft has confirmed this to be a bug in the Microsoft products listed at the
beginning of this article.

MORE INFORMATION
================

The following sample code demonstrates the bug and the workaround:

  //sort.cpp
  //compiler options cl /GX sort.cpp
  #include <iostream>
  #include <algorithm>
  #include <list>
  using namespace std;

  //#define WORKAROUND //Uncomment this line to work around the bug.

  class CSort 
  {
  public:
      CSort(int i) : m_i(i) { }
      int m_i;
  };

  struct PrintElements 
  {
     void operator()(CSort* pfi) const
     {
        cout << pfi->m_i << "\n";
     }
  };

  #ifdef WORKAROUND
  template<>
  struct std::greater<CSort*>  : public binary_function<CSort* ,CSort*, bool> 
  {
      bool operator()(const CSort* &x, const CSort* &y) const
      { 
  	return (x->m_i < y->m_i); 
      };
  };
  #endif

  // User-defined predicate function for sorting.
  struct lessThan : public greater<CSort*> 
  {
      bool operator()(const CSort* &pfi1, const CSort* &pfi2) const
      { 
  	return pfi1->m_i < pfi2->m_i; 
      }
  };

  void SortTest()
  {
      list<CSort*> l3;
      l3.push_back(new CSort(11));
      l3.push_back(new CSort(01));
      l3.push_back(new CSort(21));
      l3.push_back(new CSort(14));
      l3.push_back(new CSort(41));
      list<CSort*>::iterator lfii = l3.begin();
      l3.sort(lessThan());
      for_each(l3.begin(), l3.end(), PrintElements());
      cout.flush();
  }

  int main(int argc, char* argv[])
  {
      SortTest();
      return 0;
  }

The program produces the following output, which is incorrect:

  41
  14
  21
  1
  11

The expected output is a sorted result:

  1
  11
  14
  21
  41

Additional query words:

======================================================================
Keywords          : kbtemplate kbSTL kbVC600bug kbDSupport kbGrpDSVCCompiler 
Technology        : kbVCsearch kbAudDeveloper kbCVCComp
Version           : :
Issue type        : kbbug
Solution Type     : kbfix

=============================================================================

THE INFORMATION PROVIDED IN THE MICROSOFT KNOWLEDGE BASE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND. MICROSOFT DISCLAIMS ALL WARRANTIES, EITHER EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL MICROSOFT CORPORATION OR ITS SUPPLIERS BE LIABLE FOR ANY DAMAGES WHATSOEVER INCLUDING DIRECT, INDIRECT, INCIDENTAL, CONSEQUENTIAL, LOSS OF BUSINESS PROFITS OR SPECIAL DAMAGES, EVEN IF MICROSOFT CORPORATION OR ITS SUPPLIERS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. SOME STATES DO NOT ALLOW THE EXCLUSION OR LIMITATION OF LIABILITY FOR CONSEQUENTIAL OR INCIDENTAL DAMAGES SO THE FOREGOING LIMITATION MAY NOT APPLY.

Copyright Microsoft Corporation 1986-2002.