Implement P0433: deduction guides for <map>

[• Quuxplusone]

Summary

(AFAIK, P0433 was adopted into C++17 at Kona 2017.)
This patch incorporates the resolution of LWG 3025.

See also D58582, D58617.

[mclow.lists]

test/std/containers/associative/map/map.cons/deduct.pass.cpp

47

We have a macro called ASSERT_SAME_TYPE. You get it by including test_macros.h. Easier to read than std::is_same_v<...

[mclow.lists]

test/std/containers/associative/map/map.cons/deduct.fail.cpp

40

It would be good if there were comments here explaining why this should fail.
Alternately, you could rename A -> NotAnAllocator

[mclow.lists]

test/std/containers/associative/map/map.cons/deduct.fail.cpp

45

Please say why you expect these tests to fail.
Don't make a reader dig through the requirements to see if they're correct.
Take a look at "queue/queue.cons/deduct.fail.cpp", for example.

[• Quuxplusone]

Use ASSERT_SAME_TYPE.
Better comments in .fail.cpp.
Fix some whitespace in my comments.

@mclow.lists ping!

[• Quuxplusone]

include/iterator

541

Incidentally, I have no opinion on whether this #ifndef is appropriate. It shouldn't break anything to define these aliases unconditionally, except that then I'd probably have to switch the usings to typedefs.

[• Quuxplusone]

Remove an unused struct NotAnAllocator from the tests. NFC.

[ldionne]

include/map

1474

So those enable_ifs are required to avoid colliding with the map(initializer_list<pair<_Key, _Tp>>, _Allocator) deduction guide, correct?

[• Quuxplusone]

include/map

1474

Yes, that's right. They correspond directly with the SFINAE requirements in
http://eel.is/c++draft/container.adaptors.general#4

[mclow.lists]

Here's a bunch of minor stylistic and comment nits.

I'm irked by the bit typedef typename __identity<_Allocator>::type allocator_type; in the definition of map/multimap.
What problem is that solving?

test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp

60

What's going on here?
Does this test need to be uncommented? or removed?

65

Missing motivation for this bit.

test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp

39

All though this test, you have a mixture of pair<int, long> and pair<const int, long>. Are these changes relevant? If you need them for the equals calls, you can define a custom comparison:

template <class T1, class T2>
struct pair_eq
{
	bool operator()(const std::pair<      T1,       T2> &rhs, const std::pair<      T1,       T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }

	bool operator()(const std::pair<const T1, const T2> &rhs, const std::pair<const T1, const T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }

	bool operator()(const std::pair<      T1, const T2> &rhs, const std::pair<const T1, const T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }

	bool operator()(const std::pair<const T1, const T2> &rhs, const std::pair<      T1, const T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }
};

and then call
assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m, pair_eq<int, long>{})));

I'm not 100% sure that this is a win, but it might be.

40

Alternately, you could define a couple of typedefs:

using P = std::pair<int, long>;
using PC = std::pair<const int, long>;

45

This should be const, too. (I know that you don't ever change this, but ...)

77

A comment here "braces instead of parens" would help a lot.

91

typedef using P = std::pair<int, long>; would make this clearer.
Along with std::multimap m{ P{1,1L}, P{2,2L}, P{1,1L}, P{INT_MAX,1L}, P{3,1L} };

111

Why is this not P expected_m[] = ...?

[• Quuxplusone]

I'm irked by the typedef typename __identity<_Allocator>::type allocator_type; in the definition of map/multimap. What problem is that solving?

Unfortunately, if you don't place a "deduction firewall" between allocator_type and _Allocator, then the deduction guides implicitly generated from the unconstrained constructors of map/multimap that take an allocator_type parameter will happily match and deduce e.g. _Allocator=std::less<int>, which then blows up with a hard error trying to instantiate allocator_traits<std::less<int>>. We need to place that firewall in order to nerf the implicitly generated deduction guides, so that our explicit deduction guides can take priority.

Easy experiment: remove the firewall and compile the new test files. If I'm not mistaken, you'll see horrible error messages.

test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp

40

This sounds good.
Yes, I believe I needed to use exactly value_type so that the equals would work.
Will change to use those two typedefs and const PC expected_m[] = ....

91

Hmm. I seem to recall that I specifically didn't want to nail down what kind of pair was being CTAD'ed — the idea was to keep this specific code (a CTAD multimap of pair{x,y}s) working even if the CTAD guides on either multimap or pair are changed in the future. Other tests would handle "a CTAD multimap of pair<A,B>(x,y)s" and "a CTAD multimap of {x,y}s."
Except that I don't see those tests here! So I guess using the concrete type pair<A,B> (or just P) would be okay.

I am unsure whether multimap{ pair{a,b}, pair{c,d} } can ever produce a different type from multimap{ pair<A,B>{a,b}, pair<A,B>{c,d} }. I am pretty sure that those can produce a different type from multimap{ {a,b}, {c,d} }.

111

Will change to const PC expected_m[] = ....
(I think originally I introduced typedef P only for use in allocator<P>, because those lines were getting too long. So it wasn't used consistently everywhere — just in the allocator types.)

[• Quuxplusone]

test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp

60

The reason it's commented out is that the error message that's actually printed is a hard error from inside include/map and I don't know how to write an expected-error line for that. Is that possible? Here's the error as printed:

File $ROOT/llvm/projects/libcxx/include/map Line 1671: static_assert failed due to requirement 'is_same<std::__1::pair<int, long>, std::__1::pair<const int, long> >::value' "Allocator::value_type must be same type as value_type"

test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp

91

I found the "CTAD multimap of {x,y}s" in deduct.fail.cpp. :)

[• Quuxplusone]

Review comments on the unit tests.
Also, it looks like my initial upload didn't actually include the LWG3025 fix? The fix involves the remove_const that's now in most of the deduction guides (and a new test file to test the change).

[• Quuxplusone]

test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp

123 ↗

(On Diff #198084)

BTW, if you told me to remove these last two tests (which test std::multimap<const int&, long>), I would do so.
I don't know whether libc++ is supporting reference types here by unhappy accident (i.e. you should just add static_assert(is_object_v<_Key> && is_object_v<_Tp>) and be done with it), or by happy accident (i.e. you would be scared to add that static_assert at this point but I should remove these two tests anyway), or on purpose (i.e. I should keep these two tests).

Note that std::map cannot support a reference-typed _Key because then try_emplace would give multiple declaration errors: const _Key& and _Key&& would be the same type.

[• Quuxplusone]

@mclow.lists Ping!

[ldionne]

include/map

1474

Those requirements are for container adapters -- do we have similar requirements for map and set?

[• Quuxplusone]

include/map

1474

Oops, you're absolutely right. Yes we do; the requirements for map and set are in
http://eel.is/c++draft/associative.reqmts#15 (which is what I should have said above instead of http://eel.is/c++draft/container.adaptors.general#4).

[mclow.lists]

This looks good to me, with a few nits.

include/map

2124

You're very consistent here with qualifying remove_const, and nothing else. Why?

test/std/containers/associative/map/map.cons/deduct.fail.cpp

63

Why is this test commented out?

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

This works? I would think that it should not. We rebind the allocator internally into something else, but we should probably reject this. [But not in this patch]

test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp

60

See test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.fail.cpp for an example.
Basically, you would write:

// expected-error-re@ map:* {{static_assert failed{{( due to requirement '.*')?}} "Allocator::value_type must be same type as value_type"}}

[mclow.lists]

test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp

123 ↗

(On Diff #198084)

I'll look into this.

[ldionne]

I remember looking at this and I was fine with it. LGTM if @mclow.lists is fine with it.

[• Quuxplusone]

include/map

2124

No reason. Removed.

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

This is me getting a jump start on P1518 Stop overconstraining allocators in container deduction guides.

Since

std::map<int, long> m(source, std::allocator<int>());

works (without CTAD), Mike Spertus (as of February) and I believe that

std::map m(source, std::allocator<int>());

should work with CTAD as well.

[• Quuxplusone]

Addressed the latest review comments.

[mclow.lists]

Almost there - and I'm on the hook for comments on the reference stuff.

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

I don't believe that either should work.

std::vector<long, std::allocator<int>> m;
doesn't work, nor does:

long l[] = {1L };
std::vector v(std::begin(l), std::end(l), std::allocator<int>());

The fact that it works today for map and set is due to insufficient checking in libc++

[mclow.lists]

test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp

123 ↗

(On Diff #198084)

I would say drop these two tests. We don't have any other map tests that use reference keys.

[• Quuxplusone]

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

std::vector<long, std::allocator<int>> m; is not expected to work, because it avoids CTAD and explicitly instantiates vector with bad template parameters.

std::vector v(std::begin(l), std::end(l), std::allocator<int>()) is not expected to work either (although there's a slightly stronger case for allowing it to work), because the value type of the iterator is different from the value type of the-allocator-which-is-deduced-by-CTAD. (Since the allocator is deduced, there's arguably a case for CTAD to trust the allocator's value_type and ignore the irrelevant value type of the iterator. That is, arguably, CTAD could do the same thing that std::vector<int, std::allocator<int>> v(std::begin(l), std::end(l), std::allocator<int>()) does.)

But in std::vector w(source, std::allocator<int>()), CTAD knows we're using the allocator-aware copy constructor of vector. That constructor deduces the allocator type from the first parameter — the vector it's making a copy of — not from the second parameter. The only requirement is that the passed-in allocator argument should be implicitly convertible to the deduced allocator type. Which in this case, it is.

I'm willing to #if 0 out this test for now, but I am also willing to keep debating it until you see the P1518 light. ;)

test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp

123 ↗

(On Diff #198084)

Will do.

[• Quuxplusone]

Address review comments. (Remove the two tests involving a multimap-of-reference-type.)

[mclow.lists]

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

I think we're discussing different things here.

I'm talking about the general container requirements, the very first line in Table 62, which says:

Mandates: allocator_­type::value_­type is the same as X::value_­type.

As far as I can tell, P1518 doesn't change that at all.

[• Quuxplusone]

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

I think you think we're discussing different things, but we're not. ;)
Here's the test in question:

std::map<int, long> source;
std::map m(source, std::allocator<int>());
ASSERT_SAME_TYPE(decltype(m), decltype(source));

I claim (equivalently, P1518 claims) that the variable definition on line 2 creates a variable m of type std::map<int, long>. This is "obvious" because it is calling the allocator-aware constructor map(const map&, allocator). We're using CTAD here, but we could just as well put the deduced template arguments back in place:

std::map<int, long> m(source, std::allocator<int>());

This is fine. The second constructor argument, the one that provides a "value" for the new map's allocator, is implicitly converted from std::allocator<int> to std::map<int, long>::allocator_type.

You might say "Shouldn't the second parameter's type be forced to exactly match std::map<int, long>::allocator_type?" but no, that's not how it works without CTAD, so it's not how it should work with CTAD either. In particular, we would like the following to work:

std::pmr::map<int, long> source;
std::map m(source, std::pmr::new_delete_resource());
ASSERT_SAME_TYPE(decltype(m), decltype(source));

    // C++2a only: requires CTAD to see through typedefs
std::pmr::map m2(source, std::pmr::new_delete_resource());
ASSERT_SAME_TYPE(decltype(m2), decltype(source));

That can only work (AFAIK) if you don't allow CTAD to "get confused" by the actual argument type of that second argument. All we require is that the actual argument should be something convertible to allocator_type (which would be the requirement in the absence of CTAD).

[mclow.lists]

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

I'm willing to #if 0 out this test for now, but I am also willing to keep debating it until you see the P1518 light. ;)

I think that we should remove this test, commit the rest of this patch, and then continue this debate if/when P1518 lands. Tests that are commented out are always a question for the reader: "Why is this test commented out?"

[• Quuxplusone]

Use the original decltype(source)::allocator_type instead of std::allocator<int> in the allocator-aware-copy-constructor test. So we don't insist on P1518R0 support (yet).

[• Quuxplusone]

@mclow.lists: I think everything's resolved and this is ready for you (or someone; not me) to land. Once it's landed, I assume the next step will be to resume review on D58582 (set) and/or D58590 (unordered_map).

test/std/containers/associative/map/map.cons/deduct.pass.cpp

88

Okay. Not removed, but modified to use the exact allocator_type, which we both agree should work regardless.

[mclow.lists]

Committed as revision 362986

[mgorny]

Marshall, std/containers/associative/map/map.cons/deduct_const.pass.cpp test seems to be reliably failing from commit one on both Gentoo Linux and NetBSD. Could you please look at the classical example of totally cryptic C++ error? ;-)

http://lab.llvm.org:8011/builders/netbsd-amd64/builds/20/steps/run%20unit%20tests/logs/FAIL%3A%20libc%2B%2B%3A%3Adeduct_const.pass.cpp

[• Quuxplusone]

• Add an __identity<T>::type "firewall" on the comparator type as well as on the allocator type. (This fixes the Gentoo/NetBSD test failure. Essentially, my patch had been accidentally relying on a clang bug which caused the implicit deduction guides to be totally ignored in this case. When the clang bug got fixed, my patch broke. Adding the "firewall" fixes my patch AFAICT.)

• Use enable_if_t and remove_const_t instead of the longer C++11-friendly names. I assume that since the deduction guides are compiled only in C++17 library mode, they are allowed to rely on C++14-and-later library features. However, I can put it back the way it was if someone disagrees with my assumption.

include/iterator

 struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 
 template <class _Tp>
 struct __is_exactly_input_iterator
     : public integral_constant<bool, 
          __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && 
         !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
 
+#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
+template<class _InputIterator>
+using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
+
+template<class _InputIterator>
+using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
+
+template<class _InputIterator>
+using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
+
+template<class _InputIterator>
+using __iter_to_alloc_type = pair<
+    add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>,
+    typename iterator_traits<_InputIterator>::value_type::second_type>;
+#endif
+
 template<class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
 struct _LIBCPP_TEMPLATE_VIS iterator
 {
     typedef _Tp        value_type;
     typedef _Distance  difference_type;
     typedef _Pointer   pointer;
     typedef _Reference reference;

include/map

 class _LIBCPP_TEMPLATE_VIS map
 {
 public:
     // types:
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
     typedef _Compare                                 key_compare;
-    typedef _Allocator                               allocator_type;
+    typedef typename __identity<_Allocator>::type    allocator_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
 
     static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                   "Allocator::value_type must be same type as value_type");
 
     class _LIBCPP_TEMPLATE_VIS value_compare
private:
     typedef __map_node_destructor<__node_allocator> _Dp;
     typedef unique_ptr<__node, _Dp> __node_holder;
 
 #ifdef _LIBCPP_CXX03_LANG
     __node_holder __construct_node_with_key(const key_type& __k);
 #endif
 };
 
+#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
+template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
+         class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
+  -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
+
+template<class _Key, class _Tp, class _Compare = less<_Key>,
+         class _Allocator = allocator<pair<const _Key, _Tp>>,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
+  -> map<_Key, _Tp, _Compare, _Allocator>;
+
+template<class _InputIterator, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+map(_InputIterator, _InputIterator, _Allocator)
+  -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
+         less<__iter_key_type<_InputIterator>>, _Allocator>;
+
+template<class _Key, class _Tp, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+map(initializer_list<pair<_Key, _Tp>>, _Allocator)
+  -> map<_Key, _Tp, less<_Key>, _Allocator>;
+#endif
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
 {
     if (__a != __m.get_allocator())
     {

 class _LIBCPP_TEMPLATE_VIS multimap
 {
 public:
     // types:
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
     typedef _Compare                                 key_compare;
-    typedef _Allocator                               allocator_type;
+    typedef typename __identity<_Allocator>::type    allocator_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
 
     static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                   "Allocator::value_type must be same type as value_type");
 
     class _LIBCPP_TEMPLATE_VIS value_compare
private:
     typedef typename __base::__node                    __node;
     typedef typename __base::__node_allocator          __node_allocator;
     typedef typename __base::__node_pointer            __node_pointer;
 
     typedef __map_node_destructor<__node_allocator> _Dp;
     typedef unique_ptr<__node, _Dp> __node_holder;
 };
 
+#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
+template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
+         class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
+  -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
+
+template<class _Key, class _Tp, class _Compare = less<_Key>,
+         class _Allocator = allocator<pair<const _Key, _Tp>>,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
+  -> multimap<_Key, _Tp, _Compare, _Allocator>;
+
+template<class _InputIterator, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+multimap(_InputIterator, _InputIterator, _Allocator)
+  -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
+         less<__iter_key_type<_InputIterator>>, _Allocator>;
+
+template<class _Key, class _Tp, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
+  -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
+#endif
+
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
 {
     if (__a != __m.get_allocator())
     {
         const_iterator __e = cend();

test/std/containers/associative/map/map.cons/deduct.fail.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
+//
+//===----------------------------------------------------------------------===//
+
+// <map>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// map(InputIterator, InputIterator,
+//          Compare = Compare(), Allocator = Allocator())
+//   -> map<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// map(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> map<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// map(InputIterator, InputIterator, Allocator)
+//   -> map<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// map(initializer_list<Key>, Allocator)
+//   -> map<Key, less<Key>, Allocator>;
+
+#include <climits> // INT_MAX
+#include <functional>
+#include <map>
+#include <type_traits>
+
+struct NotAnAllocator {
+    friend bool operator<(NotAnAllocator, NotAnAllocator) { return false; }
+};
+
+int main(int, char**)
+{
+    {
+        // cannot deduce Key and T from nothing
+        std::map m; // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // cannot deduce Key and T from just (Compare)
+        std::map m(std::less<int>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // cannot deduce Key and T from just (Compare, Allocator)
+        std::map m(std::less<int>{}, std::allocator<std::pair<const int, int>>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // cannot deduce Key and T from just (Allocator)
+        std::map m(std::allocator<std::pair<const int, int>>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // refuse to rebind the allocator if Allocator::value_type is not exactly what we expect
+        // std::pair<int, int> arr[] = { {1,1}, {2,2}, {3,3} };
+        // std::map m(arr, arr + 3, std::allocator<std::pair<int, int>>());
+    }
+    {
+        NotAnAllocator a;
+        std::map m(a); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        std::map m{ {1,1}, {2,2}, {3,3} };
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        std::map m({ {1,1}, {2,2}, {3,3} }, std::less<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        using P = std::pair<const int, int>;
+        std::map m({ {1,1}, {2,2}, {3,3} }, std::less<int>(), std::allocator<P>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        using P = std::pair<const int, int>;
+        std::map m({ {1,1}, {2,2}, {3,3} }, std::allocator<P>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+    {
+        // since we have parens, not braces, this deliberately does not find the initializer_list constructor
+        std::map m(std::pair{1,1});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'map'}}
+    }
+
+  return 0;
+}

test/std/containers/associative/map/map.cons/deduct.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
+//
+//===----------------------------------------------------------------------===//
+
+// <map>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// map(InputIterator, InputIterator,
+//          Compare = Compare(), Allocator = Allocator())
+//   -> map<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// map(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> map<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// map(InputIterator, InputIterator, Allocator)
+//   -> map<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// map(initializer_list<Key>, Allocator)
+//   -> map<Key, less<Key>, Allocator>;
+
+#include <algorithm> // std::equal
+#include <cassert>
+#include <climits> // INT_MAX
+#include <functional>
+#include <map>
+#include <type_traits>
+
+#include "test_allocator.h"
+
+int main(int, char**)
+{
+    {
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::map m(std::begin(arr), std::end(arr));
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::map m(std::begin(arr), std::end(arr), std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long, std::greater<int>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::map m(std::begin(arr), std::end(arr), std::greater<int>(), test_allocator<P>(0, 42));
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long, std::greater<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 42);
+    }
+
+    {
+    std::map<int, long> source;
+    std::map m(source);
+    ASSERT_SAME_TYPE(decltype(m), decltype(source));
+    assert(m.size() == 0);
+    }
+
+    {
+    std::map<int, long> source;
+    std::map m{source};
+    ASSERT_SAME_TYPE(decltype(m), decltype(source));
+    assert(m.size() == 0);
+    }
+
+    {
+    std::map<int, long> source;
+    std::map m(source, std::allocator<int>());
+    ASSERT_SAME_TYPE(decltype(m), decltype(source));
+    assert(m.size() == 0);
+    }
+
+    {
+    std::map m{ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} };
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    std::map m({ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} }, std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long, std::greater<int>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    std::map m({ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} }, std::greater<int>(), test_allocator<P>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long, std::greater<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 43);
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::map m(std::begin(arr), std::end(arr), test_allocator<P>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long, std::less<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 44);
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    std::map m({ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} }, test_allocator<P>(0, 45));
+
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, long, std::less<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 45);
+    }
+
+  return 0;
+}

test/std/containers/associative/multimap/multimap.cons/deduct.fail.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
+//
+//===----------------------------------------------------------------------===//
+
+// <map>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// multimap(InputIterator, InputIterator,
+//          Compare = Compare(), Allocator = Allocator())
+//   -> multimap<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// multimap(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> multimap<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// multimap(InputIterator, InputIterator, Allocator)
+//   -> multimap<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// multimap(initializer_list<Key>, Allocator)
+//   -> multimap<Key, less<Key>, Allocator>;
+
+#include <climits> // INT_MAX
+#include <functional>
+#include <map>
+#include <type_traits>
+
+struct NotAnAllocator {
+    friend bool operator<(NotAnAllocator, NotAnAllocator) { return false; }
+};
+
+int main(int, char**)
+{
+    {
+        // cannot deduce Key and T from nothing
+        std::multimap m; // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // cannot deduce Key and T from just (Compare)
+        std::multimap m(std::less<int>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // cannot deduce Key and T from just (Compare, Allocator)
+        std::multimap m(std::less<int>{}, std::allocator<std::pair<const int, int>>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // cannot deduce Key and T from just (Allocator)
+        std::multimap m(std::allocator<std::pair<const int, int>>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // refuse to rebind the allocator if Allocator::value_type is not exactly what we expect
+        // std::pair<int, int> arr[] = { {1,1}, {2,2}, {3,3} };
+        // std::multimap m(arr, arr + 3, std::allocator<std::pair<int, int>>());
+    }
+    {
+        NotAnAllocator a;
+        std::multimap m(a); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        std::multimap m{ {1,1}, {2,2}, {3,3} };
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        std::multimap m({ {1,1}, {2,2}, {3,3} }, std::less<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        using P = std::pair<const int, int>;
+        std::multimap m({ {1,1}, {2,2}, {3,3} }, std::less<int>(), std::allocator<P>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // cannot deduce that the inner braced things should be std::pair and not something else
+        using P = std::pair<const int, int>;
+        std::multimap m({ {1,1}, {2,2}, {3,3} }, std::allocator<P>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+    {
+        // since we have parens, not braces, this deliberately does not find the initializer_list constructor
+        std::multimap m(std::pair{1,1});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'multimap'}}
+    }
+
+  return 0;
+}

test/std/containers/associative/multimap/multimap.cons/deduct.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
+//
+//===----------------------------------------------------------------------===//
+
+// <map>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// multimap(InputIterator, InputIterator,
+//          Compare = Compare(), Allocator = Allocator())
+//   -> multimap<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// multimap(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> multimap<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// multimap(InputIterator, InputIterator, Allocator)
+//   -> multimap<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// multimap(initializer_list<Key>, Allocator)
+//   -> multimap<Key, less<Key>, Allocator>;
+
+#include <algorithm> // std::equal
+#include <cassert>
+#include <climits> // INT_MAX
+#include <functional>
+#include <map>
+#include <type_traits>
+
+#include "test_allocator.h"
+
+int main(int, char**)
+{
+    {
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::multimap m(std::begin(arr), std::end(arr));
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::multimap m(std::begin(arr), std::end(arr), std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long, std::greater<int>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::multimap m(std::begin(arr), std::end(arr), std::greater<int>(), test_allocator<P>(0, 42));
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long, std::greater<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 42);
+    }
+
+    {
+    std::multimap<int, long> source;
+    std::multimap m(source);
+    ASSERT_SAME_TYPE(decltype(m), decltype(source));
+    assert(m.size() == 0);
+    }
+
+    {
+    std::multimap<int, long> source;
+    std::multimap m{source};
+    ASSERT_SAME_TYPE(decltype(m), decltype(source));
+    assert(m.size() == 0);
+    }
+
+    {
+    std::multimap<int, long> source;
+    std::multimap m(source, std::allocator<int>());
+    ASSERT_SAME_TYPE(decltype(m), decltype(source));
+    assert(m.size() == 0);
+    }
+
+    {
+    std::multimap m{ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} };
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    std::multimap m({ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} }, std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long, std::greater<int>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    std::multimap m({ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} }, std::greater<int>(), test_allocator<P>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long, std::greater<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {INT_MAX,1L}, {3,1L}, {2,2L}, {1,1L}, {1,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 43);
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    const std::pair<int, long> arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} };
+    std::multimap m(std::begin(arr), std::end(arr), test_allocator<P>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long, std::less<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 44);
+    }
+
+    {
+    using P = std::pair<const int, long>;
+    std::multimap m({ std::pair{1,1L}, std::pair{2,2L}, std::pair{1,1L}, std::pair{INT_MAX,1L}, std::pair{3,1L} }, test_allocator<P>(0, 45));
+
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long, std::less<int>, test_allocator<P>>);
+    std::pair<const int, long> expected_m[] = { {1,1L}, {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
+    assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
+    assert(m.get_allocator().get_id() == 45);
+    }
+
+  return 0;
+}