forward_list::sort is not stable

[Nilay Vaish <nilayvaish at gmail dot com>]

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

Attachment: forward_list.patch
Description: Text document