<algorithm>: std::partial_sort_copy performs an unconstrained operation

[CaseyCarter]

In:

STL/stl/inc/algorithm

Lines 6946 to 6972 in c10ae01

	template <class _InIt, class _RanIt, class _Pr>
	_CONSTEXPR20 _RanIt partial_sort_copy(_InIt _First1, _InIt _Last1, _RanIt _First2, _RanIt _Last2, _Pr _Pred) {
	// copy [_First1, _Last1) into [_First2, _Last2)
	_Adl_verify_range(_First1, _Last1);
	_Adl_verify_range(_First2, _Last2);
	auto _UFirst1 = _Get_unwrapped(_First1);
	const auto _ULast1 = _Get_unwrapped(_Last1);
	auto _UFirst2 = _Get_unwrapped(_First2);
	const auto _ULast2 = _Get_unwrapped(_Last2);
	auto _UMid2 = _UFirst2;
	if (_UFirst1 != _ULast1 && _UFirst2 != _ULast2) {
	for (; _UFirst1 != _ULast1 && _UMid2 != _ULast2; ++_UFirst1, (void) ++_UMid2) {
	*_UMid2 = *_UFirst1; // copy min(_ULast1 - _UFirst1, _ULast2 - _UFirst2)
	}
	_Make_heap_unchecked(_UFirst2, _UMid2, _Pass_fn(_Pred));
	for (; _UFirst1 != _ULast1; ++_UFirst1) {
	if (_DEBUG_LT_PRED(_Pred, *_UFirst1, *_UFirst2)) {
	// replace top with new largest:
	using _Diff = _Iter_diff_t<_RanIt>;
	_Pop_heap_hole_by_index(_UFirst2, static_cast<_Diff>(0), static_cast<_Diff>(_UMid2 - _UFirst2),
	static_cast<_Iter_value_t<_InIt>>(*_UFirst1), _Pass_fn(_Pred));
	}
	}
	_Sort_heap_unchecked(_UFirst2, _UMid2, _Pass_fn(_Pred));
	}

on line 6967:

STL/stl/inc/algorithm

Line 6967 in c10ae01

static_cast<_Iter_value_t<_InIt>>(*_UFirst1), _Pass_fn(_Pred));

we construct an object of _InIt's value type from an element reference. The type requirements of the algorithm from [partial.sort.copy] are:

1. Let N be min(last - first, result_last - result_first). Let comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names.
2. Mandates: For the overloads in namespace std, the expression *first is writable ([iterator.requirements.general]) to result_first.
3. Preconditions: For the overloads in namespace std, RandomAccessIterator meets the Cpp17ValueSwappable requirements ([swappable.requirements]), the type of *result_­first meets the Cpp17MoveConstructible (Table 28) and Cpp17MoveAssignable (Table 30) requirements.

There are requirements that allow the algorithm to construct an object of the random access iterator's value type, but not the input iterator's value type.

To my understanding, this program should compile and run successfully:

#include <algorithm>
#include <cassert>
#include <compare>

struct wrapper {
    wrapper() = default;
    constexpr explicit wrapper(int i) : x{i} {}

    auto operator<=>(const wrapper&) const = default;

    int x;
};

struct source : wrapper {
    using wrapper::wrapper;

    source(const source&) = delete;
    source& operator=(const source&) = delete;
};

struct target : wrapper {
    using wrapper::wrapper;

    target(target&&) = default;
    target& operator=(target&&) = default;

    target& operator=(const source& w) {
        x = w.x;
        return *this;
    }
};

int main() {
    source src[] = {source{5}, source{4}, source{3}, source{2}, source{1}, source{0}};
    target dst[2];

    using std::begin, std::end;
    std::partial_sort_copy(begin(src), end(src), begin(dst), end(dst));
    assert(dst[0].x == 0);
    assert(dst[1].x == 1);
}

but it does not (https://godbolt.org/z/1xq7ah). Interestingly, libstdc++ has the same bug, but libc++ does not. This repro triggers a different partial_sort_copy bug in libc++: it uses a default comparator other than std::less{} which fails for this test case.