[libc++][spaceship] Implement `operator<=>` for `map` and `multimap`

[H-G-Hristov]

Summary

Implements parts of P1614R2: operator<=> for map and multimap

[H-G-Hristov]

• Updated links

[philnik]

LGTM % nit.

libcxx/test/libcxx/containers/associative/map/compare.three_way.pass.cpp

27

Most of the tests don't have a constexpr path. There is no need to call it out here.

[H-G-Hristov]

libcxx/test/libcxx/containers/associative/map/compare.three_way.pass.cpp

27

I kept this pattern from the original patch here: https://reviews.llvm.org/D132312
Shall I delete it now or create a new patch later to delete this line from all patches at once?

[H-G-Hristov]

libcxx/test/libcxx/containers/associative/map/compare.three_way.pass.cpp

27

What I mean it is already present in patches that have landed but also in all that are waiting for a review.

[philnik]

libcxx/test/libcxx/containers/associative/map/compare.three_way.pass.cpp

27

Ah OK. I missed that this already exists in other operator<=> patches. Then I'm fine with it as-is.

[H-G-Hristov]

@philnik Thank you for the review. The CI error appears to be unrelated. Is anything else necessary to do before landing this? Could you do that for me again, please.

[philnik]

In D145976#4196433, @H-G-Hristov wrote:

@philnik Thank you for the review. The CI error appears to be unrelated. Is anything else necessary to do before landing this? Could you do that for me again, please.

You might want to consider getting commit access if you plan to continue contributing. See https://www.llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access for details.

[H-G-Hristov]

In D145976#4196453, @philnik wrote:

In D145976#4196433, @H-G-Hristov wrote:

@philnik Thank you for the review. The CI error appears to be unrelated. Is anything else necessary to do before landing this? Could you do that for me again, please.

You might want to consider getting commit access if you plan to continue contributing. See https://www.llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access for details.

Thank you for committing!!! I requested commit access.

libcxx/docs/Status/SpaceshipProjects.csv

 | `[stacktrace.basic.cmp] <https://wg21.link/stacktrace.basic.cmp>`_,| basic_stacktrace,[alg.three.way],Unassigned,|Not Started|
 | `[string.cmp] <https://wg21.link/string.cmp>`_,| `basic_string <https://reviews.llvm.org/D131421>`_,None,Mark de Wever,|Complete|
 | `[string.view.comparison] <https://wg21.link/string.view.comparison>`_,| `basic_string_view <https://reviews.llvm.org/D130295>`_,None,Mark de Wever,|Complete|
 | `[array.syn] <https://wg21.link/array.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `array <https://reviews.llvm.org/D132265>`_,[expos.only.func],Adrian Vogelsgesang,|In Progress|
 | `[deque.syn] <https://wg21.link/deque.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `deque <https://reviews.llvm.org/D144821>`_,[expos.only.func],Hristo Hristov,|Complete|
 | `[forward.list.syn] <https://wg21.link/forward.list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `forward_list <https://reviews.llvm.org/D145172>`_,[expos.only.func],Hristo Hristov,|Complete|
 | `[list.syn] <https://wg21.link/list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `list <https://reviews.llvm.org/D132312>`_,[expos.only.func],Adrian Vogelsgesang,|Complete|
 | `[vector.syn] <https://wg21.link/vector.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `vector <https://reviews.llvm.org/D132268>`_,[expos.only.func],Adrian Vogelsgesang,|In Progress|
-| `[associative.map.syn] <https://wg21.link/associative.map.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| map
-| multimap",[expos.only.func],Unassigned,|Not Started|
+| `[associative.map.syn] <https://wg21.link/associative.map.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| `map <https://reviews.llvm.org/D145976>`_
+| `multimap <https://reviews.llvm.org/D145976>`_",[expos.only.func],Hristo Hristov,|Complete|
 | `[associative.set.syn] <https://wg21.link/associative.set.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| multiset
 | set",[expos.only.func],Unassigned,|Not Started|
 | `[queue.ops] <https://wg21.link/queue.ops>`_,| queue,None,Unassigned,|Not Started|
 | `[stack.ops] <https://wg21.link/stack.ops>`_,| stack,None,Unassigned,|Not Started|
 | `[reverse.iter.cmp] <https://wg21.link/reverse.iter.cmp>`_,| `reverse_iterator <https://reviews.llvm.org/D113695>`_,None,Mikhail Maltsev,|Complete|
 | `[move.iter.op.comp] <https://wg21.link/move.iter.op.comp>`_,| `move_iterator <https://reviews.llvm.org/D117656>`_,None,Arthur O'Dwyer,|Complete|
 | `[counted.iter.cmp] <https://wg21.link/counted.iter.cmp>`_,| `counted_iterator <https://reviews.llvm.org/D106205>`_,None,Zoe Carver,|Complete|
 | `[range.iota.iterator] <https://wg21.link/range.iota.iterator>`_,| `ranges::iota_view::iterator <https://reviews.llvm.org/D110774>`_,[concepts.cmp],Arthur O'Dwyer,|Complete|

libcxx/include/map

 template <class Key, class T, class Compare, class Allocator>
 bool
 operator==(const map<Key, T, Compare, Allocator>& x,
            const map<Key, T, Compare, Allocator>& y);
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator< (const map<Key, T, Compare, Allocator>& x,
-           const map<Key, T, Compare, Allocator>& y);
+           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator!=(const map<Key, T, Compare, Allocator>& x,
-           const map<Key, T, Compare, Allocator>& y);
+           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator> (const map<Key, T, Compare, Allocator>& x,
-           const map<Key, T, Compare, Allocator>& y);
+           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator>=(const map<Key, T, Compare, Allocator>& x,
-           const map<Key, T, Compare, Allocator>& y);
+           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator<=(const map<Key, T, Compare, Allocator>& x,
-           const map<Key, T, Compare, Allocator>& y);
+           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
+
+template<class Key, class T, class Compare, class Allocator>
+  synth-three-way-result<pair<const Key, T>>
+    operator<=>(const map<Key, T, Compare, Allocator>& x,
+                const map<Key, T, Compare, Allocator>& y); // since C++20
 
 // specialized algorithms:
 template <class Key, class T, class Compare, class Allocator>
 void
 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
     noexcept(noexcept(x.swap(y)));
 
 template <class Key, class T, class Compare, class Allocator, class Predicate>

 template <class Key, class T, class Compare, class Allocator>
 bool
 operator==(const multimap<Key, T, Compare, Allocator>& x,
            const multimap<Key, T, Compare, Allocator>& y);
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator< (const multimap<Key, T, Compare, Allocator>& x,
-           const multimap<Key, T, Compare, Allocator>& y);
+           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator!=(const multimap<Key, T, Compare, Allocator>& x,
-           const multimap<Key, T, Compare, Allocator>& y);
+           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator> (const multimap<Key, T, Compare, Allocator>& x,
-           const multimap<Key, T, Compare, Allocator>& y);
+           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator>=(const multimap<Key, T, Compare, Allocator>& x,
-           const multimap<Key, T, Compare, Allocator>& y);
+           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
 
 template <class Key, class T, class Compare, class Allocator>
 bool
 operator<=(const multimap<Key, T, Compare, Allocator>& x,
-           const multimap<Key, T, Compare, Allocator>& y);
+           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
+
+template<class Key, class T, class Compare, class Allocator>
+  synth-three-way-result<pair<const Key, T>>
+    operator<=>(const multimap<Key, T, Compare, Allocator>& x,
+                const multimap<Key, T, Compare, Allocator>& y); // since c++20
 
 // specialized algorithms:
 template <class Key, class T, class Compare, class Allocator>
 void
 swap(multimap<Key, T, Compare, Allocator>& x,
      multimap<Key, T, Compare, Allocator>& y)
     noexcept(noexcept(x.swap(y)));
 
 template <class Key, class T, class Compare, class Allocator, class Predicate>
 typename multimap<Key, T, Compare, Allocator>::size_type
 erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20
 
 }  // std
 
 */
 
 #include <__algorithm/equal.h>
 #include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/lexicographical_compare_three_way.h>
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__config>
 #include <__functional/binary_function.h>
 #include <__functional/is_transparent.h>
 #include <__functional/operations.h>
 #include <__iterator/erase_if_container.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>

 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
            const map<_Key, _Tp, _Compare, _Allocator>& __y)
 {
     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
 }
 
+#if _LIBCPP_STD_VER <= 17
+
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
            const map<_Key, _Tp, _Compare, _Allocator>& __y)
 {
     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 }

 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
            const map<_Key, _Tp, _Compare, _Allocator>& __y)
 {
     return !(__y < __x);
 }
 
+#else // #if _LIBCPP_STD_VER <= 17
+
+template<class _Key, class _Tp, class _Compare, class _Allocator>
+inline _LIBCPP_HIDE_FROM_ABI
+__synth_three_way_result<pair<const _Key, _Tp>>
+operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x,
+            const map<_Key, _Tp, _Compare, _Allocator>& __y)
+{
+    return std::lexicographical_compare_three_way(
+        __x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
+}
+
+#endif // #if _LIBCPP_STD_VER <= 17
+
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
      map<_Key, _Tp, _Compare, _Allocator>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 {
     __x.swap(__y);

 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
 {
     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
 }
 
+#if _LIBCPP_STD_VER <= 17
+
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
 {
     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 }

 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
 {
     return !(__y < __x);
 }
 
+#else // #if _LIBCPP_STD_VER <= 17
+
+template<class _Key, class _Tp, class _Compare, class _Allocator>
+inline _LIBCPP_HIDE_FROM_ABI
+__synth_three_way_result<pair<const _Key, _Tp>>
+operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
+            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
+{
+    return std::lexicographical_compare_three_way(
+        __x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
+}
+
+#endif // #if _LIBCPP_STD_VER <= 17
+
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
      multimap<_Key, _Tp, _Compare, _Allocator>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 {
     __x.swap(__y);

libcxx/test/libcxx/containers/associative/map/compare.three_way.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <map>
+
+// class map
+
+// template<class Key, class T, class Compare, class Allocator>
+//   synth-three-way-result<pair<const Key, T>>
+//     operator<=>(const map<Key, T, Compare, Allocator>& x,
+//                 const map<Key, T, Compare, Allocator>& y);
+
+#include <cassert>
+#include <map>
+
+#include "test_container_comparisons.h"
+
+int main(int, char**) {
+  assert(test_ordered_map_container_spaceship<std::map>());
+  // `std::map` is not constexpr, so no `static_assert` test here.
+  return 0;
+}

libcxx/test/libcxx/containers/associative/multimap/compare.three_way.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <map>
+
+// class multimap
+
+// template<class Key, class T, class Compare, class Allocator>
+//   synth-three-way-result<pair<const Key, T>>
+//     operator<=>(const multimap<Key, T, Compare, Allocator>& x,
+//                 const multimap<Key, T, Compare, Allocator>& y);
+
+#include <cassert>
+#include <map>
+
+#include "test_container_comparisons.h"
+
+int main(int, char**) {
+  assert(test_ordered_map_container_spaceship<std::multimap>());
+  // `std::multimap` is not constexpr, so no `static_assert` test here.
+  return 0;
+}

libcxx/test/support/test_container_comparisons.h

constexpr bool test_ordered_container_spaceship() {
 
   // Thanks to SFINAE, the following is not a compiler error but returns `false`
   struct NonComparable {};
   static_assert(!std::three_way_comparable<Container<NonComparable>>);
 
   return true;
 }
 
+// Implementation detail of `test_ordered_map_container_spaceship`
+template <template <typename...> typename Container, typename Key, typename Val, typename Order>
+constexpr void test_ordered_map_container_spaceship_with_type() {
+  // Empty containers
+  {
+    Container<Key, Val> l1;
+    Container<Key, Val> l2;
+    assert(testOrder(l1, l2, Order::equivalent));
+  }
+  // Identical contents
+  {
+    Container<Key, Val> l1{{1, 1}, {2, 1}};
+    Container<Key, Val> l2{{1, 1}, {2, 1}};
+    assert(testOrder(l1, l2, Order::equivalent));
+  }
+  // Less, due to contained values
+  {
+    Container<Key, Val> l1{{1, 1}, {2, 1}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}};
+    assert(testOrder(l1, l2, Order::less));
+  }
+  // Greater, due to contained values
+  {
+    Container<Key, Val> l1{{1, 1}, {2, 3}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}};
+    assert(testOrder(l1, l2, Order::greater));
+  }
+  // Shorter list
+  {
+    Container<Key, Val> l1{{1, 1}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}};
+    assert(testOrder(l1, l2, Order::less));
+  }
+  // Longer list
+  {
+    Container<Key, Val> l1{{1, 2}, {2, 2}};
+    Container<Key, Val> l2{{1, 1}};
+    assert(testOrder(l1, l2, Order::greater));
+  }
+  // Unordered
+  if constexpr (std::is_same_v<Val, PartialOrder>) {
+    Container<Key, Val> l1{{1, 1}, {2, std::numeric_limits<int>::min()}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}};
+    assert(testOrder(l1, l2, Order::unordered));
+  }
+
+  // Identical contents
+  {
+    Container<Key, Val> l1{{1, 1}, {2, 1}, {2, 2}};
+    Container<Key, Val> l2{{1, 1}, {2, 1}, {2, 2}};
+    assert(testOrder(l1, l2, Order::equivalent));
+    Container<Key, Val> l3{{1, 1}, {2, 1}, {2, 2}};
+    Container<Key, Val> l4{{2, 1}, {2, 2}, {1, 1}};
+    assert(testOrder(l3, l4, Order::equivalent));
+  }
+  // Less, due to contained values
+  {
+    Container<Key, Val> l1{{1, 1}, {2, 1}, {2, 1}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 2}};
+    assert(testOrder(l1, l2, Order::less));
+    Container<Key, Val> l3{{1, 1}, {2, 1}, {2, 1}};
+    Container<Key, Val> l4{{2, 2}, {2, 2}, {1, 1}};
+    assert(testOrder(l3, l4, Order::less));
+  }
+  // Greater, due to contained values
+  {
+    Container<Key, Val> l1{{1, 1}, {2, 3}, {2, 3}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 2}};
+    assert(testOrder(l1, l2, Order::greater));
+    Container<Key, Val> l3{{1, 1}, {2, 3}, {2, 3}};
+    Container<Key, Val> l4{{2, 2}, {2, 2}, {1, 1}};
+    assert(testOrder(l3, l4, Order::greater));
+  }
+  // Shorter list
+  {
+    Container<Key, Val> l1{{1, 1}, {2, 2}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 2}, {3, 1}};
+    assert(testOrder(l1, l2, Order::less));
+    Container<Key, Val> l3{{1, 1}, {2, 2}};
+    Container<Key, Val> l4{{3, 1}, {2, 2}, {2, 2}, {1, 1}};
+    assert(testOrder(l3, l4, Order::less));
+  }
+  // Longer list
+  {
+    Container<Key, Val> l1{{1, 2}, {2, 2}, {2, 2}, {3, 1}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}};
+    assert(testOrder(l1, l2, Order::greater));
+    Container<Key, Val> l3{{1, 2}, {2, 2}, {2, 2}, {3, 1}};
+    Container<Key, Val> l4{{2, 2}, {1, 1}};
+    assert(testOrder(l3, l4, Order::greater));
+  }
+  // Unordered
+  if constexpr (std::is_same_v<Val, PartialOrder>) {
+    Container<Key, Val> l1{{1, 1}, {2, std::numeric_limits<int>::min()}, {2, 3}};
+    Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 3}};
+    assert(testOrder(l1, l2, Order::unordered));
+    Container<Key, Val> l3{{1, 1}, {2, std::numeric_limits<int>::min()}, {2, 3}};
+    Container<Key, Val> l4{{2, 3}, {2, 2}, {1, 1}};
+    assert(testOrder(l3, l4, Order::unordered));
+  }
+}
+
+// Tests the `operator<=>` on ordered containers
+template <template <typename...> typename Container>
+constexpr bool test_ordered_map_container_spaceship() {
+  // The container should fulfil `std::three_way_comparable`
+  static_assert(std::three_way_comparable<Container<int, int>>);
+
+  // Test different comparison categories
+  test_ordered_map_container_spaceship_with_type<Container, int, int, std::strong_ordering>();
+  test_ordered_map_container_spaceship_with_type<Container, int, StrongOrder, std::strong_ordering>();
+  test_ordered_map_container_spaceship_with_type<Container, int, WeakOrder, std::weak_ordering>();
+  test_ordered_map_container_spaceship_with_type<Container, int, PartialOrder, std::partial_ordering>();
+
+  // `LessAndEqComp` does not have `operator<=>`. ordering is sythesized based on `operator<`
+  test_ordered_map_container_spaceship_with_type<Container, int, LessAndEqComp, std::weak_ordering>();
+
+  // Thanks to SFINAE, the following is not a compiler error but returns `false`
+  struct NonComparable {};
+  static_assert(!std::three_way_comparable<Container<int, NonComparable>>);
+
+  return true;
+}
+
 #endif