Index: include/iterator =================================================================== --- include/iterator +++ include/iterator @@ -538,6 +538,22 @@ __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 +using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; + +template +using __iter_key_type = remove_const_t::value_type::first_type>; + +template +using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; + +template +using __iter_to_alloc_type = pair< + add_const_t::value_type::first_type>, + typename iterator_traits<_InputIterator>::value_type::second_type>; +#endif + template struct _LIBCPP_TEMPLATE_VIS iterator Index: include/map =================================================================== --- include/map +++ include/map @@ -903,7 +903,7 @@ typedef _Tp mapped_type; typedef pair 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; @@ -1461,6 +1461,32 @@ #endif }; +#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES +template>, + class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, + class = typename enable_if::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 _Allocator = allocator>, + class = typename enable_if::value, void>::type, + class = typename enable_if<__is_allocator<_Allocator>::value, void>::type> +map(initializer_list>, _Compare = _Compare(), _Allocator = _Allocator()) + -> map<_Key, _Tp, _Compare, _Allocator>; + +template::value, void>::type> +map(_InputIterator, _InputIterator, _Allocator) + -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, + less<__iter_key_type<_InputIterator>>, _Allocator>; + +template::value, void>::type> +map(initializer_list>, _Allocator) + -> map<_Key, _Tp, less<_Key>, _Allocator>; +#endif #ifndef _LIBCPP_CXX03_LANG template @@ -1634,7 +1660,7 @@ typedef _Tp mapped_type; typedef pair 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; @@ -2082,6 +2108,33 @@ typedef unique_ptr<__node, _Dp> __node_holder; }; +#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES +template>, + class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, + class = typename enable_if::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 _Allocator = allocator>, + class = typename enable_if::value, void>::type, + class = typename enable_if<__is_allocator<_Allocator>::value, void>::type> +multimap(initializer_list>, _Compare = _Compare(), _Allocator = _Allocator()) + -> multimap<_Key, _Tp, _Compare, _Allocator>; + +template::value, void>::type> +multimap(_InputIterator, _InputIterator, _Allocator) + -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, + less<__iter_key_type<_InputIterator>>, _Allocator>; + +template::value, void>::type> +multimap(initializer_list>, _Allocator) + -> multimap<_Key, _Tp, less<_Key>, _Allocator>; +#endif + #ifndef _LIBCPP_CXX03_LANG template multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) Index: test/std/containers/associative/map/map.cons/deduct.fail.cpp =================================================================== --- /dev/null +++ test/std/containers/associative/map/map.cons/deduct.fail.cpp @@ -0,0 +1,97 @@ +//===----------------------------------------------------------------------===// +// +// 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++98, c++03, c++11, c++14 +// UNSUPPORTED: libcpp-no-deduction-guides + +// template>, +// class Allocator = allocator>> +// map(InputIterator, InputIterator, +// Compare = Compare(), Allocator = Allocator()) +// -> map, Compare, Allocator>; +// template, class Allocator = allocator> +// map(initializer_list, Compare = Compare(), Allocator = Allocator()) +// -> map; +// template +// map(InputIterator, InputIterator, Allocator) +// -> map, less>, Allocator>; +// template +// map(initializer_list, Allocator) +// -> map, Allocator>; + +#include // INT_MAX +#include +#include +#include + +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{}); + // 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{}, std::allocator>{}); + // 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>{}); + // 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 arr[] = { {1,1}, {2,2}, {3,3} }; + // std::map m(arr, arr + 3, std::allocator>()); + } + { + 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()); + // 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; + std::map m({ {1,1}, {2,2}, {3,3} }, std::less(), std::allocator

()); + // 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; + std::map m({ {1,1}, {2,2}, {3,3} }, std::allocator

()); + // 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; +} Index: test/std/containers/associative/map/map.cons/deduct.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/associative/map/map.cons/deduct.pass.cpp @@ -0,0 +1,138 @@ +//===----------------------------------------------------------------------===// +// +// 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++98, c++03, c++11, c++14 +// UNSUPPORTED: libcpp-no-deduction-guides + +// template>, +// class Allocator = allocator>> +// map(InputIterator, InputIterator, +// Compare = Compare(), Allocator = Allocator()) +// -> map, Compare, Allocator>; +// template, class Allocator = allocator> +// map(initializer_list, Compare = Compare(), Allocator = Allocator()) +// -> map; +// template +// map(InputIterator, InputIterator, Allocator) +// -> map, less>, Allocator>; +// template +// map(initializer_list, Allocator) +// -> map, Allocator>; + +#include // std::equal +#include +#include // INT_MAX +#include +#include +#include + +#include "test_allocator.h" + +int main(int, char**) +{ + { + const std::pair 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); + std::pair 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 arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} }; + std::map m(std::begin(arr), std::end(arr), std::greater()); + + ASSERT_SAME_TYPE(decltype(m), std::map>); + std::pair 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 std::pair arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} }; + std::map m(std::begin(arr), std::end(arr), std::greater(), test_allocator

(0, 42)); + + ASSERT_SAME_TYPE(decltype(m), std::map, test_allocator

>); + std::pair 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 source; + std::map m(source); + ASSERT_SAME_TYPE(decltype(m), decltype(source)); + assert(m.size() == 0); + } + + { + std::map source; + std::map m{source}; + ASSERT_SAME_TYPE(decltype(m), decltype(source)); + assert(m.size() == 0); + } + + { + std::map source; + std::map m(source, std::allocator()); + 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); + std::pair 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()); + + ASSERT_SAME_TYPE(decltype(m), std::map>); + std::pair 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; + 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(), test_allocator

(0, 43)); + + ASSERT_SAME_TYPE(decltype(m), std::map, test_allocator

>); + std::pair 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 std::pair arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} }; + std::map m(std::begin(arr), std::end(arr), test_allocator

(0, 44)); + + ASSERT_SAME_TYPE(decltype(m), std::map, test_allocator

>); + std::pair 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; + 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

(0, 45)); + + ASSERT_SAME_TYPE(decltype(m), std::map, test_allocator

>); + std::pair 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; +} Index: test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp =================================================================== --- /dev/null +++ test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp @@ -0,0 +1,97 @@ +//===----------------------------------------------------------------------===// +// +// 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++98, c++03, c++11, c++14 +// UNSUPPORTED: libcpp-no-deduction-guides + +// template>, +// class Allocator = allocator>> +// multimap(InputIterator, InputIterator, +// Compare = Compare(), Allocator = Allocator()) +// -> multimap, Compare, Allocator>; +// template, class Allocator = allocator> +// multimap(initializer_list, Compare = Compare(), Allocator = Allocator()) +// -> multimap; +// template +// multimap(InputIterator, InputIterator, Allocator) +// -> multimap, less>, Allocator>; +// template +// multimap(initializer_list, Allocator) +// -> multimap, Allocator>; + +#include // INT_MAX +#include +#include +#include + +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{}); + // 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{}, std::allocator>{}); + // 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>{}); + // 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 arr[] = { {1,1}, {2,2}, {3,3} }; + // std::multimap m(arr, arr + 3, std::allocator>()); + } + { + 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()); + // 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; + std::multimap m({ {1,1}, {2,2}, {3,3} }, std::less(), std::allocator

()); + // 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; + std::multimap m({ {1,1}, {2,2}, {3,3} }, std::allocator

()); + // 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; +} Index: test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp =================================================================== --- /dev/null +++ test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp @@ -0,0 +1,138 @@ +//===----------------------------------------------------------------------===// +// +// 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++98, c++03, c++11, c++14 +// UNSUPPORTED: libcpp-no-deduction-guides + +// template>, +// class Allocator = allocator>> +// multimap(InputIterator, InputIterator, +// Compare = Compare(), Allocator = Allocator()) +// -> multimap, Compare, Allocator>; +// template, class Allocator = allocator> +// multimap(initializer_list, Compare = Compare(), Allocator = Allocator()) +// -> multimap; +// template +// multimap(InputIterator, InputIterator, Allocator) +// -> multimap, less>, Allocator>; +// template +// multimap(initializer_list, Allocator) +// -> multimap, Allocator>; + +#include // std::equal +#include +#include // INT_MAX +#include +#include +#include + +#include "test_allocator.h" + +int main(int, char**) +{ + { + const std::pair 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); + std::pair 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 arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} }; + std::multimap m(std::begin(arr), std::end(arr), std::greater()); + + ASSERT_SAME_TYPE(decltype(m), std::multimap>); + std::pair 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 std::pair arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} }; + std::multimap m(std::begin(arr), std::end(arr), std::greater(), test_allocator

(0, 42)); + + ASSERT_SAME_TYPE(decltype(m), std::multimap, test_allocator

>); + std::pair 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 source; + std::multimap m(source); + ASSERT_SAME_TYPE(decltype(m), decltype(source)); + assert(m.size() == 0); + } + + { + std::multimap source; + std::multimap m{source}; + ASSERT_SAME_TYPE(decltype(m), decltype(source)); + assert(m.size() == 0); + } + + { + std::multimap source; + std::multimap m(source, std::allocator()); + 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); + std::pair 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()); + + ASSERT_SAME_TYPE(decltype(m), std::multimap>); + std::pair 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; + 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(), test_allocator

(0, 43)); + + ASSERT_SAME_TYPE(decltype(m), std::multimap, test_allocator

>); + std::pair 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 std::pair arr[] = { {1,1L}, {2,2L}, {1,1L}, {INT_MAX,1L}, {3,1L} }; + std::multimap m(std::begin(arr), std::end(arr), test_allocator

(0, 44)); + + ASSERT_SAME_TYPE(decltype(m), std::multimap, test_allocator

>); + std::pair 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; + 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

(0, 45)); + + ASSERT_SAME_TYPE(decltype(m), std::multimap, test_allocator

>); + std::pair 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; +}