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
#include
#include
#include
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 v;
};
std::vector s(500);
std::iota(s.begin(), s.end(), 0);
std::random_shuffle(s.begin(), s.end());
std::sort(s.begin(), s.end(), comp(200));
return 0;
}
