forward_list::sort is not stable

[Jonathan Wakely]

On 23/02/17 12:48 -0600, Nilay Vaish wrote:
>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 for the patch. It's small enough that we don't need a copyright
assignment, and it looks correct. However GCC trunk is currently in
"Stage 4" meaning we're getting ready for the next release. I don't
want to make a change like this at this point, so asa soon as GCC 7 is
released I'll revisit this and apply it.

Thanks again for the analysis and patch.