关于std::sort递归过程中是否会复制传入的函数对象的疑问

Great question! Let's break this down step by step.

What the C++ Standard Says #

The C++ standard does not explicitly specify whether std::sort must copy or avoid copying the provided comparison function object during its execution (including recursive steps). Instead, it only enforces that the comparison type meets the Compare concept requirements:

• The type must be CopyConstructible and/or MoveConstructible (so implementations are allowed to make copies if it benefits performance or logic).
• The comparison function must enforce a strict weak ordering, and repeated calls with identical inputs must return the same result (stateful comparisons are allowed but risky for std::sort unless intentional and carefully managed).

In short: STL implementers have full flexibility here—they can choose to copy the function object, pass it by reference, or use any other strategy that preserves the core sorting semantics.

What Your Code Reveals #

Your test uses a C23 lambda with this auto& self to track each instance's address, and the multiple distinct addresses in your output directly confirm that your current STL implementation (e.g., libstdc, libc++, or MSVC STL) is copying the lambda during the sort's recursive execution.

This is a common choice for many std::sort implementations, which typically use divide-and-conquer strategies like introsort (a hybrid of quicksort, heapsort, and insertion sort). Different recursive branches or optimization steps may receive their own copy of the comparison object—for example, to avoid the tiny overhead of reference indirection in tight recursive loops, or to isolate state in parallelized variants (though standard std::sort isn't parallel unless you use an execution policy).

Your Theoretical Optimization Idea #

You mentioned that std::sort could theoretically use a thread-local copy and pass only its address across recursion levels. That's a perfectly valid optimization strategy! However, the standard doesn't mandate this behavior—implementers balance factors like performance, code complexity, and generality. For small, cheap-to-copy objects like your lambda (with just a reference capture), copying is often faster than managing thread-local storage or reference wrappers in recursive hot paths.

How to Force a Single Instance (If Needed) #

If you want to ensure only one instance of your comparison object is used (e.g., if it holds expensive state), wrap it in std::ref to pass a reference wrapper instead of the object itself:

sort(vi.begin(), vi.end(), std::ref([&](this auto& self, int lhs, int rhs) {
    ++fnAdresses[&self];
    return lhs < rhs;
}));

With std::ref, all recursive calls will use the same underlying lambda instance, so your fnAdresses map will only contain one entry.

Summary #

• Observed behavior: Your STL implementation copies the lambda during std::sort recursion, hence the multiple distinct addresses.
• Standard rule: No strict requirement—implementations can copy or avoid copying as they see fit.
• Control copies: Use std::ref to enforce a single instance if copying is undesirable.

内容来源于Stack Exchange