我可以阻止 std::sort 复制传递的比较对象吗

Question

我们使用比较器对象对向量进行排序：

std::vector<Data> v = ....
Comparator c = ....
std::sort(v.begin(), v,end(), c);

但是，这会在排序期间复制 c，并导致性能问题，因为 Comparator 对象存储一个大映射（在调用比较函数时会在其中完成查找）。 我想我可以强制使用参考文献：

const Comparator &ref = c;
std::sort(v.begin(), v.end(), ref);

但是副本仍然会发生。 有没有办法防止复制，或者我是否必须使比较器仅存储指向大量数据的指针？ （我认为我们不能在我们的编译器版本中使用 lambda/closures）。

Answer 1

首先要注意的是，该标准对于函数对象将完成多少副本提供了很少的保证。 如果您需要使用全状态函数，您应该使用引用语义（让函子指向状态，而不是保存在内部）。

话虽这么说，第一个选择是重构函子或包装它：

struct Wrapper {
   Comparator *cmp;
   Wrapper(Comparator *cmp) : cmp(cmp) {}
   bool operator()(T const & lhs, T const & rhs) const {
      return (*cmp)(lhs,rhs);
   }
};
Comparator cmp(...);
Wrapper w(&cmp);
sort(v.begin(), v.end(), w);

这实际上与直接使用

std::ref

(C++11) 得到的结果相同：

Comparator cmp(...);
sort(v.begin(), v.end(), std::ref(cmp));

Answer 2

我想知道这些实现是否复制了通过递归传递给 sort() 的函数对象。我用这段代码测试了这一点：

#include <iostream>
#include <random>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;

int main(int argc, char** argv)
{
    mt19937_64 mt;
    uniform_int_distribution<int> uid( INT_MAX, INT_MAX );
    vector<int> vi;
    vi.reserve( 1'000 );
    for( size_t i = vi.capacity(); i--; )
        vi.emplace_back(uid( mt ));
    using map_t = map<void *, size_t>;
    map_t
        fnAdresses,
        localAddresses;
    bool invert = argc > 1;
    sort( vi.begin(), vi.end(),
        [&, invert = invert]( int lhs, int rhs )
        {
            ++fnAdresses[(void *)&invert];
            char c;
            ++localAddresses[&c];
            if( !invert )
                return lhs < rhs;
            else
                return rhs < lhs;
        } );
    auto print = []( char const *prefix, map_t const &map )
    {
        if( !map.size() )
            return;
        cout << prefix << endl;
        char const *min = (char *)map.begin()->first;
        size_t i = 0;
        for( auto &kv : map )
            cout << "\t" << i++ << ":\t" << (void *)kv.first << ", " << (char*)kv.first - (char*)min << ", " << kv.second << endl;
    };
    print( "fn:", fnAdresses );
    print( "local:", localAddresses );
}

MSVC prints:

fn:
        0:      00000079FC8FE780, 0, 2006
local:
        0:      00000079FC8FE578, 0, 8
        1:      00000079FC8FE610, 152, 999
        2:      00000079FC8FE611, 153, 999

clang++-19 prints:

fn:
        0:      0x7ffccf1f7c40, 0, 35
        1:      0x7ffccf1f7d10, 208, 240
        2:      0x7ffccf1f7de0, 416, 741
        3:      0x7ffccf1f7eb0, 624, 1386
        4:      0x7ffccf1f7f80, 832, 1837
        5:      0x7ffccf1f8050, 1040, 1990
        6:      0x7ffccf1f8080, 1088, 15
        7:      0x7ffccf1f80e0, 1184, 15
        8:      0x7ffccf1f8150, 1296, 984
local:
        0:      0x7ffccf1f7c6f, 0, 35
        1:      0x7ffccf1f7d3f, 208, 240
        2:      0x7ffccf1f7e0f, 416, 741
        3:      0x7ffccf1f7edf, 624, 1386
        4:      0x7ffccf1f7faf, 832, 1837
        5:      0x7ffccf1f801f, 944, 15
        6:      0x7ffccf1f806f, 1024, 15
        7:      0x7ffccf1f807f, 1040, 1990
        8:      0x7ffccf1f811f, 1200, 984

g++-12 prints:

fn:
        0:      0x7ffef7fb1f90, 0, 35
        1:      0x7ffef7fb20d0, 320, 240
        2:      0x7ffef7fb2210, 640, 741
        3:      0x7ffef7fb2350, 960, 1386
        4:      0x7ffef7fb2490, 1280, 1837
        5:      0x7ffef7fb25d0, 1600, 2005
        6:      0x7ffef7fb2630, 1696, 15
        7:      0x7ffef7fb2720, 1936, 984
local:
        0:      0x7ffef7fb1f5f, 0, 35
        1:      0x7ffef7fb209f, 320, 240
        2:      0x7ffef7fb21df, 640, 741
        3:      0x7ffef7fb231f, 960, 1386
        4:      0x7ffef7fb245f, 1280, 1837
        5:      0x7ffef7fb259f, 1600, 1990
        6:      0x7ffef7fb25be, 1631, 15
        7:      0x7ffef7fb25bf, 1632, 15
        8:      0x7ffef7fb26b0, 1873, 984`

因此，MSVC 是唯一一个在所有递归级别引用同一函数对象的编译器。因此，为了实现可移植性能，最好将外部对象引用为 thread_local 变量。如果比较函数对象可以用 shl 来处理。像scope_exit一样清理引用的线程本地对象。