[Bug libstdc++/95245] New: std::sort copies custom comparator

[andrew.bell.ia at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95245

            Bug ID: 95245
           Summary: std::sort copies custom comparator
           Product: gcc
           Version: 7.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: andrew.bell.ia at gmail dot com
  Target Milestone: ---

std::sort copies a custom comparator numerous times.  If the comparator copy is
expensive, it makes the sort very slow.  Of course, making the comparator cheap
to copy is an easy fix, but it took me by surprise that the algorithm copied my
comparator at all.  Other c++ library implementations don't have this
limitation.  I found this on version 7.5, but I believe the same behavior is in
GCC 10.1.  The following program exhibits the issue:

#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>

int main()
{
    struct comp
    {
        comp(int i)
        {
            v.resize(i);
            std::iota(v.begin(), v.end(), 0);
        }

        comp(const comp& c) : v(c.v)
        {
            std::cerr << "Copy ctor!\n";
        }

        comp(comp&& c) : v(std::move(c.v))
        {
            std::cerr << "Move ctor!\n";
        }

        bool operator()(size_t p1, size_t p2)
        {
            return p1 < p2;
        }

        // Vector is just here to cause an expensive copy and slow the sort,
        // but it could,
        // for example, be a cache that is used in the comparison.
        std::vector<int> v;
    };

    std::vector<size_t> s(5000000);
    std::iota(s.begin(), s.end(), 0);
    std::random_shuffle(s.begin(), s.end());
    std::sort(s.begin(), s.end(), comp(2000000));

    return 0;
}