forward_list::sort is not stable

[Nilay Vaish]

Hello

I went through the code for forward_list::sort().  I think it is not
stable.  The following code illustrates the problem.  With GCC version
5.4.0, I get the output: "(1, 2), (1, 1), ", where as if the sort was
stable, we should get the output: "(1, 1), (1, 2), ".

----------------------------------------------------------------------------------------------
#include <forward_list>
#include <iterator>
#include <iostream>
#include <algorithm>

struct Compare
{
  public:
    bool operator()(const std::pair<int, int> &l,
            const std::pair<int, int> &r) const
    {
      if (l.first < r.first)
          return true;
      return false;
    }
};

int main()
{
  std::forward_list<std::pair<int, int>> F = { std::make_pair(1, 1),
      std::make_pair(1, 2) };
  F.sort(Compare());

  for (auto v: F)
  {
    std::cout << "(" << v.first << ", " << v.second << "), ";
  }

  std::cout << "\n";
  return 0;
}
----------------------------------------------------------------------------------------------

I went through the current code in the file:
libstdc++-v3/include/bits/forward_list.tcc.   The problem is that the
comparison is carried out in an incorrect order.  The attached patch
should fix the problem.


Thanks
Nilay
-------------- next part --------------
Index: libstdc++-v3/include/bits/forward_list.tcc
===================================================================
--- libstdc++-v3/include/bits/forward_list.tcc	(revision 245686)
+++ libstdc++-v3/include/bits/forward_list.tcc	(working copy)
@@ -451,20 +451,20 @@
                         __p = static_cast<_Node*>(__p->_M_next);
                         --__psize;
                       }
-                    else if (__comp(*__p->_M_valptr(), *__q->_M_valptr()))
+                    else if (__comp(*__q->_M_valptr(), *__p->_M_valptr()))
                       {
+                        // First node of q is lower; e must come from q.
+                        __e = __q;
+                        __q = static_cast<_Node*>(__q->_M_next);
+                        --__qsize;
+                      }
+                    else
+                      {
                         // First node of p is lower; e must come from p.
                         __e = __p;
                         __p = static_cast<_Node*>(__p->_M_next);
                         --__psize;
                       }
-                    else
-                      {
-                        // First node of q is lower; e must come from q.
-                        __e = __q;
-                        __q = static_cast<_Node*>(__q->_M_next);
-                        --__qsize;
-                      }
 
                     // Add the next node to the merged list.
                     if (__tail)