Why isn't `std::compare_three_way` a `std::strict_weak_order`?

user_12442419 0
Viewed 96

With C++20 concepts and three-way-comparison, I have made my own Map like this:

template<
    typename TKey,
    typename TValue,
    std::strict_weak_order<TKey, TKey> KeyComparer = std::compare_three_way, // Error: template constraint not satisfied
    typename PairAllocator = std::allocator<KeyValuePair<TKey, TValue>>
>class SortedMap

When SortedMap initializes, it failed with error template constraint not satisfied.

Modify std::strict_weak_order to typename then it's ok. (Error comes here certainly.)

Why doesn't std::compare_three_way satisfy std::strict_weak_order?

c++20 c++
1 Answers

std::strict_weak_order<R, T, U> requires R to be a predicate - that invoking R on objects of types T and U gives you bool. But std::compare_three_way does not return bool, it returns one of the comparison categories that are the result of <=> (e.g. std::strong_ordering).

There is currently no concept in the standard library for if something is an invocable that returns a comparison category (in the same way that strict_weak_order is the the concept generalization of using <).

So either:

  1. You build your map on top of three-way comparisons and do everything accordingly. This means writing your own concept for a three-way comparing object. Something like this would do:
template <typename T, typename Cat>
concept compares_as = std::same_as<std::common_comparison_category_t<T, Cat>, Cat>;

template <typename R, typename T, typename U>
concept three_way_order = std::regular_invocable<R, T, U>
  && compares_as<std::invoke_result_t<R, T, U>, std::weak_ordering>;

This would reject partial orders - which means you can't have double as a key (or rather couldn't use <=> as the comparison directly, users would have to provide a custom comparison function to reject NaNs or some such). If you want to to handle partial orders in your container directly, change std::weak_ordering to std::partial_ordering above.

Or

  1. You build your map on top of < as std::map does, and so you would use std::less<> or std::less<Key> as your default comparison type. Since x < y can rewrite to (x <=> y) < 0 anyway, this would still use <=> if that is the way that < is implemented. But in your container implementation, you would just get a two-way comparison result (i.e. bool) instead of a three-way comparison result (e.g. std::strong_ordering).
user_20690640
Related