Should C++20 std::ranges::sort not need to support std::vector<bool>?

Question

I noticed that std::ranges::sort cannot sort std::vector<bool>:

<source>:6:51: error: no match for call to '(const std::ranges::__sort_fn) (std::vector<bool, std::allocator<bool> >)'
6 |   std::ranges::sort(std::vector{false, true, true});
  |   

Is this allowed? Should we need a specialization of std::ranges::sort for std::vector<bool>? Is there any information about how the committee consider this?

Answer 1

As an update, now that zip was adopted for c++23, part of that paper added const-assignment to vector<bool>::reference, which allows that that type to satisfy indirectly_writable, and thus std::ranges::sort on a vector<bool> works in C++23.

---

Correct.

More generally, std::ranges::sort cannot sort proxy references. The direct reason is that sort requires sortable (surprising, right) which if we follow that chain up requires permutable which requires indirectly_movable_storable which requires indirectly_movable which requires indirectly_writable.

And indirectly_writeable is a very peculiar looking concept.

template<class Out, class T>
  concept indirectly_writable =
    requires(Out&& o, T&& t) {
      *o = std::forward<T>(t);  // not required to be equality-preserving
      *std::forward<Out>(o) = std::forward<T>(t);   // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*o) =
        std::forward<T>(t);     // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) =
        std::forward<T>(t);     // not required to be equality-preserving
    };

I want to specifically draw your attention to:

const_cast<const iter_reference_t<Out>&&>(*o) = std::forward<T>(t);

Wait, we require const assignability?

---

This particular issue has a long history. You can start with #573, in which a user demonstrated this problem:

struct C
{
    explicit C(std::string a) : bar(a) {}    
    std::string bar;
};

int main()
{
    std::vector<C> cs = { C("z"), C("d"), C("b"), C("c") };

    ranges::sort(cs | ranges::view::transform([](const C& x) {return x.bar;}));

    for (const auto& c : cs) {
        std::cout << c.bar << std::endl;
    }
}

The expectation of course was that it would print b, c, d, z in that order. But it didn't. It printed z, d, b, c. The order didn't change. The reason here is that because this is a range of prvalues, the elements we're swapping as part of the sort. Well, they're temporaries. This has no effect on cs whatsoever.

This obviously can't work. The user has a bug - they intended to sort the Cs by the bars (i.e. use a projection) but instead they're just sorting the bars (even if the lambda returned a reference, they'd be sorting just the bars and not the Cs anyway -- in this case there is only one member of C anyway but in the general case this is clearly not the intended behavior).

But the goal then is really: how do we make this bug not compile? That's the dream. The problem is that C++ added ref-qualifications in C++11, but implicit assignment has always existed. And implicit operator= has no ref-qualifier, you can assign to an rvalue just fine, even if that makes no sense whatsoever:

std::string("hello") = "goodbye"; // fine, but pointless, probably indicative of a bug

Assigning to an rvalue is really only okay if the ravlue itself handles this correctly. Ideally, we could just check to make sure a type has an rvalue-qualified operator=. Proxy types (such as vector<bool>::reference) would then qualify their assignment operators, that's what we would check, and everybody's happy.

But we can't do that - because basically every type is rvalue-assignable, even if very few types actually meaningfully are. So what Eric and Casey came up with is morally equivalent to adding a type trait to a type that says "I am, legitimately, for real, rvalue-assignable." And unlike most type traits where you would do something like:

template <>
inline constexpr bool for_real_rvalue_assignable<T> = true;

This one is just spelled:

T& operator=(Whatever) const;

Even though the const equality operator will not actually be invoked as part of the algorithm. It just has to be there.

You might ask at this point - wait, what about references? For "normal" ranges (say, vector<int>, the iter_reference_t<Out> gives you int&, and const iter_reference_t<Out>&& is... still just int&. That's why this just works. For ranges that yield glvalues, these const-assignment requirements basically duplicate the normal assignment requirements. The const-assignability issue is _only_for prvalues.

---

This issue was also the driver of why views::zip isn't in C++20. Because zip also yields a prvalue range and a tuple<T&...> is precisely the kind of proxy reference that we would need to handle here. And to handle that, we would have to make a change to std::tuple to allow this kind of const-assignability.

As far as I'm aware, this is still the direction that it's intended (given that we have already enshrined that requirement into a concept, a requirement that no standard library proxy types actually satisfy). So when views::zip is added, tuple<T&...> will be made const-assignable as well as vector<bool>::reference.

The end result of that work is that:

std::ranges::sort(std::vector{false, true, true});

will actually both compile and work correctly.