Extract key to avoid preemptive mallocs in insert/emplace in associative containers

[EricWF]

Summary

This patch applies Duncan's work on hash_table to tree.

[dexonsmith]

LGTM. Thanks for picking this up (and sorry for getting distracted)!

[mclow.lists]

This looks good to me, except for the noisy tests.

test/std/containers/associative/set/insert_and_emplace_allocator_requirements.pass.cpp

29

In general, we want tests to be silent on success.

[EricWF]

test/std/containers/associative/set/insert_and_emplace_allocator_requirements.pass.cpp

29

I'll see what I can do. The reason these tests are so noisy is because almost all of the assertions are in "container_test_types.h". Meaning that when the tests fail the diagnostic points into the header with no information about what code actually triggered the assertion. Hence why these tests manually print what they are testing.

I'll try and come up with something better.

[EricWF]

I've silenced the tests when they pass as suggested. I added a 'assert_checkpoint.h' support header that stores the last checkpoint a test has passed and prints that information when std::abort is called.

I also moved the allocator requirement test templates into generic headers so the same version can be used by both the associative and unordered containers. Previously each test was duplicated.

include/__hash_table

     return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
 }
 
-#ifndef _LIBCPP_CXX03_LANG
-struct __extract_key_fail_tag {};
-struct __extract_key_self_tag {};
-struct __extract_key_first_tag {};
-
-template <class _ValTy, class _Key,
-          class _RawValTy = typename __unconstref<_ValTy>::type>
-struct __can_extract_key
-    : conditional<is_same<_RawValTy, _Key>::value, __extract_key_self_tag,
-                  __extract_key_fail_tag>::type {};
-
-template <class _Pair, class _Key, class _First, class _Second>
-struct __can_extract_key<_Pair, _Key, pair<_First, _Second>>
-    : conditional<is_same<typename remove_const<_First>::type, _Key>::value,
-                  __extract_key_first_tag, __extract_key_fail_tag>::type {};
-#endif
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
 

include/__tree

     __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
 
     template <class... _Args>
-    pair<iterator, bool> __emplace_unique(_Args&&... __args);
+    pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
 
     template <class... _Args>
-    iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args);
+    iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
 
     template <class... _Args>
     iterator __emplace_multi(_Args&&... __args);
 
     template <class... _Args>
     iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __emplace_unique(_Pp&& __x) {
+        return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
+                                            __can_extract_key<_Pp, key_type>());
+    }
+
+    template <class... _Args>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __emplace_unique(_Args&&... __args) {
+        return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
+    }
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool>
+    __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
+      return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
+    }
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool>
+    __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
+      return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
+    }
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool>
+    __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
+      return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
+    }
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
+        return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x),
+                                            __can_extract_key<_Pp, key_type>());
+    }
+
+    template <class... _Args>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
+        return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...);
+    }
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator
+    __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
+      return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
+    }
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator
+    __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
+      return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x));
+    }
+
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator
+    __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
+      return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x));
+    }
+
 #else
     template <class _Key, class _Args>
     _LIBCPP_INLINE_VISIBILITY

 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args)
+__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
 {
     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
     __node_base_pointer __parent;

 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
-__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args)
+__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
 {
     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
     __node_base_pointer __parent;

include/__tuple

 
 // pair specializations
 
-template <class _T1, class _T2> struct _LIBCPP_TYPE_VIS_ONLY pair;
-
 template <class _T1, class _T2> struct __tuple_like<pair<_T1, _T2> > : true_type {};
 
 template <size_t _Ip, class _T1, class _T2>

include/type_traits

 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _T1, class _T2> struct _LIBCPP_TYPE_VIS_ONLY pair;
+
 template <class>
 struct __void_t { typedef void type; };
 

 # endif // _LIBCPP_HAS_NO_VARIADICS
 #endif  // _LIBCPP_STD_VER > 14
 
+// These traits are used in __tree and __hash_table
+#ifndef _LIBCPP_CXX03_LANG
+struct __extract_key_fail_tag {};
+struct __extract_key_self_tag {};
+struct __extract_key_first_tag {};
+
+template <class _ValTy, class _Key,
+          class _RawValTy = typename __unconstref<_ValTy>::type>
+struct __can_extract_key
+    : conditional<is_same<_RawValTy, _Key>::value, __extract_key_self_tag,
+                  __extract_key_fail_tag>::type {};
+
+template <class _Pair, class _Key, class _First, class _Second>
+struct __can_extract_key<_Pair, _Key, pair<_First, _Second>>
+    : conditional<is_same<typename remove_const<_First>::type, _Key>::value,
+                  __extract_key_first_tag, __extract_key_fail_tag>::type {};
+#endif
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif  // _LIBCPP_TYPE_TRAITS

test/std/containers/associative/map/map.modifiers/insert_allocator_requirements.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is dual licensed under the MIT and the University of Illinois Open
-// Source Licenses. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-// <map>
-
-// class map
-
-// insert(...);
-
-// UNSUPPORTED: c++98, c++03
-
-#include <map>
-#include <iostream>
-#include <cassert>
-
-#include "test_macros.h"
-#include "count_new.hpp"
-#include "container_test_types.h"
-
-template <class Arg>
-void PrintInfo(int line, Arg&& arg)
-{
-  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
-}
-#define PRINT(msg) PrintInfo(__LINE__, msg)
-
-template <class Container>
-void testContainerInsert()
-{
-  typedef typename Container::value_type ValueTp;
-  typedef Container C;
-  typedef std::pair<typename C::iterator, bool> R;
-  ConstructController* cc = getConstructController();
-  cc->reset();
-  {
-    PRINT("Testing C::insert(const value_type&)");
-    Container c;
-    const ValueTp v(42, 1);
-    cc->expect<const ValueTp&>();
-    assert(c.insert(v).second);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      const ValueTp v2(42, 1);
-      assert(c.insert(v2).second == false);
-    }
-  }
-  {
-    PRINT("Testing C::insert(value_type&)");
-    Container c;
-    ValueTp v(42, 1);
-    cc->expect<const ValueTp&>();
-    assert(c.insert(v).second);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      ValueTp v2(42, 1);
-      assert(c.insert(v2).second == false);
-    }
-  }
-  {
-    PRINT("Testing C::insert(value_type&&)");
-    Container c;
-    ValueTp v(42, 1);
-    cc->expect<ValueTp&&>();
-    assert(c.insert(std::move(v)).second);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      ValueTp v2(42, 1);
-      assert(c.insert(std::move(v2)).second == false);
-    }
-  }
-  {
-    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
-    Container c;
-    std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
-    cc->expect<ValueTp const&>(2);
-    c.insert(il);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      c.insert(il);
-    }
-  }
-  {
-    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
-    Container c;
-    const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
-    cc->expect<ValueTp const&>(3);
-    c.insert(std::begin(ValueList), std::end(ValueList));
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      c.insert(std::begin(ValueList), std::end(ValueList));
-    }
-  }
-  {
-    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
-    Container c;
-    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
-    cc->expect<ValueTp&&>(3);
-    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
-             std::move_iterator<ValueTp*>(std::end(ValueList)));
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      ValueTp ValueList2[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
-      c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
-               std::move_iterator<ValueTp*>(std::end(ValueList2)));
-    }
-  }
-  {
-    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
-    Container c;
-    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
-    cc->expect<ValueTp const&>(3);
-    c.insert(std::begin(ValueList), std::end(ValueList));
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      c.insert(std::begin(ValueList), std::end(ValueList));
-    }
-  }
-}
-
-
-int main()
-{
-  testContainerInsert<TCT::map<> >();
-}

test/std/containers/associative/map/map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <map>
+
+// class map
+
+// insert(...);
+// emplace(...);
+// emplace_hint(...);
+
+// UNSUPPORTED: c++98, c++03
+
+#include <map>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+{
+  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
+}
+#define PRINT(msg) PrintInfo(__LINE__, msg)
+
+template <class Container>
+void testContainerInsert()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef Container C;
+  typedef std::pair<typename C::iterator, bool> R;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::insert(const value_type&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42, 1);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&&>();
+    assert(c.insert(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      assert(c.insert(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(const value_type&&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42, 1);
+      assert(c.insert(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+    Container c;
+    std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
+    cc->expect<ValueTp const&>(2);
+    c.insert(il);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(il);
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+    Container c;
+    const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+    cc->expect<ValueTp&&>(3);
+    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+             std::move_iterator<ValueTp*>(std::end(ValueList)));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp ValueList2[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+      c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
+               std::move_iterator<ValueTp*>(std::end(ValueList2)));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+}
+
+template <class Container>
+void testContainerEmplace()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef typename Container::key_type Key;
+  typedef typename Container::mapped_type Mapped;
+  typedef typename std::pair<Key, Mapped> NonConstKeyPair;
+  typedef Container C;
+  typedef std::pair<typename C::iterator, bool> R;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::emplace(const value_type&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    assert(c.emplace(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42, 1);
+      assert(c.emplace(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(value_type&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&>();
+    assert(c.emplace(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      assert(c.emplace(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(value_type&&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&&>();
+    assert(c.emplace(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      assert(c.emplace(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(const value_type&&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&&>();
+    assert(c.emplace(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42, 1);
+      assert(c.emplace(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(pair<Key, Mapped> const&)");
+    Container c;
+    const NonConstKeyPair v(42, 1);
+    cc->expect<const NonConstKeyPair&>();
+    assert(c.emplace(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const NonConstKeyPair v2(42, 1);
+      assert(c.emplace(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(pair<Key, Mapped> &&)");
+    Container c;
+    NonConstKeyPair v(42, 1);
+    cc->expect<NonConstKeyPair&&>();
+    assert(c.emplace(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      NonConstKeyPair v2(42, 1);
+      assert(c.emplace(std::move(v2)).second == false);
+    }
+  }
+}
+
+
+template <class Container>
+void testContainerEmplaceHint()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef typename Container::key_type Key;
+  typedef typename Container::mapped_type Mapped;
+  typedef typename std::pair<Key, Mapped> NonConstKeyPair;
+  typedef Container C;
+  typedef typename C::iterator It;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::emplace_hint(p, const value_type&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    It ret = c.emplace_hint(c.end(), v);
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42, 1);
+      It ret2 = c.emplace_hint(c.begin(), v2);
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, value_type&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&>();
+    It ret = c.emplace_hint(c.end(), v);
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      It ret2 = c.emplace_hint(c.begin(), v2);
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, value_type&&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&&>();
+    It ret = c.emplace_hint(c.end(), std::move(v));
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      It ret2 = c.emplace_hint(c.begin(), std::move(v2));
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, const value_type&&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&&>();
+    It ret = c.emplace_hint(c.end(), std::move(v));
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42, 1);
+      It ret2 = c.emplace_hint(c.begin(), std::move(v2));
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, pair<Key, Mapped> const&)");
+    Container c;
+    const NonConstKeyPair v(42, 1);
+    cc->expect<const NonConstKeyPair&>();
+    It ret = c.emplace_hint(c.end(), v);
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const NonConstKeyPair v2(42, 1);
+      It ret2 = c.emplace_hint(c.begin(), v2);
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, pair<Key, Mapped>&&)");
+    Container c;
+    NonConstKeyPair v(42, 1);
+    cc->expect<NonConstKeyPair&&>();
+    It ret = c.emplace_hint(c.end(), std::move(v));
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      NonConstKeyPair v2(42, 1);
+      It ret2 = c.emplace_hint(c.begin(), std::move(v2));
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+}
+
+int main()
+{
+  testContainerInsert<TCT::map<> >();
+  testContainerEmplace<TCT::map<> >();
+  testContainerEmplaceHint<TCT::map<> >();
+}

test/std/containers/associative/set/insert_allocator_requirements.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is dual licensed under the MIT and the University of Illinois Open
-// Source Licenses. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-// <set>
-
-// class set
-
-// insert(...)
-
-// UNSUPPORTED: c++98, c++03
-
-#include <set>
-#include <iostream>
-#include <cassert>
-
-#include "test_macros.h"
-#include "count_new.hpp"
-#include "container_test_types.h"
-
-template <class Arg>
-void PrintInfo(int line, Arg&& arg)
-{
-  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
-}
-#define PRINT(msg) PrintInfo(__LINE__, msg)
-
-template <class Container>
-void testContainerInsert()
-{
-  typedef typename Container::value_type ValueTp;
-  typedef Container C;
-  typedef std::pair<typename C::iterator, bool> R;
-  ConstructController* cc = getConstructController();
-  cc->reset();
-  {
-    PRINT("Testing C::insert(const value_type&)");
-    Container c;
-    const ValueTp v(42);
-    cc->expect<const ValueTp&>();
-    assert(c.insert(v).second);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      const ValueTp v2(42);
-      assert(c.insert(v2).second == false);
-    }
-  }
-  {
-    PRINT("Testing C::insert(value_type&)");
-    Container c;
-    ValueTp v(42);
-    cc->expect<const ValueTp&>();
-    assert(c.insert(v).second);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      ValueTp v2(42);
-      assert(c.insert(v2).second == false);
-    }
-  }
-  {
-    PRINT("Testing C::insert(value_type&&)");
-    Container c;
-    ValueTp v(42);
-    cc->expect<ValueTp&&>();
-    assert(c.insert(std::move(v)).second);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      ValueTp v2(42);
-      assert(c.insert(std::move(v2)).second == false);
-    }
-  }
-  {
-    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
-    Container c;
-    std::initializer_list<ValueTp> il = { ValueTp(1), ValueTp(2) };
-    cc->expect<ValueTp const&>(2);
-    c.insert(il);
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      c.insert(il);
-    }
-  }
-  {
-    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
-    Container c;
-    const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) };
-    cc->expect<ValueTp const&>(3);
-    c.insert(std::begin(ValueList), std::end(ValueList));
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      c.insert(std::begin(ValueList), std::end(ValueList));
-    }
-  }
-  {
-    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
-    Container c;
-    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
-    cc->expect<ValueTp&&>(3);
-    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
-             std::move_iterator<ValueTp*>(std::end(ValueList)));
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      ValueTp ValueList2[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
-      c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
-               std::move_iterator<ValueTp*>(std::end(ValueList2)));
-    }
-  }
-  {
-    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
-    Container c;
-    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
-    cc->expect<ValueTp const&>(3);
-    c.insert(std::begin(ValueList), std::end(ValueList));
-    assert(!cc->unchecked());
-    {
-      DisableAllocationGuard g;
-      c.insert(std::begin(ValueList), std::end(ValueList));
-    }
-  }
-}
-
-
-int main()
-{
-  testContainerInsert<TCT::set<> >();
-}

test/std/containers/associative/set/insert_and_emplace_allocator_requirements.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <set>
+
+// class set
+
+// insert(...)
+// emplace(...)
+// emplace_hint(...)
+
+// UNSUPPORTED: c++98, c++03
+
+#include <set>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+{
+  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
+}
+#define PRINT(msg) PrintInfo(__LINE__, msg)
+
+template <class Container>
+void testContainerInsert()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef Container C;
+  typedef std::pair<typename C::iterator, bool> R;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::insert(const value_type&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<ValueTp&&>();
+    assert(c.insert(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      assert(c.insert(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(const value_type&&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42);
+      assert(c.insert(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+    Container c;
+    std::initializer_list<ValueTp> il = { ValueTp(1), ValueTp(2) };
+    cc->expect<ValueTp const&>(2);
+    c.insert(il);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(il);
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+    Container c;
+    const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+    cc->expect<ValueTp&&>(3);
+    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+             std::move_iterator<ValueTp*>(std::end(ValueList)));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp ValueList2[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+      c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
+               std::move_iterator<ValueTp*>(std::end(ValueList2)));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+}
+
+
+template <class Container>
+void testContainerEmplace()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef Container C;
+  typedef std::pair<typename C::iterator, bool> R;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::emplace(const value_type&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    assert(c.emplace(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42);
+      assert(c.emplace(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(value_type&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<ValueTp&>();
+    assert(c.emplace(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      assert(c.emplace(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(value_type&&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<ValueTp&&>();
+    assert(c.emplace(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      assert(c.emplace(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::emplace(const value_type&&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&&>();
+    assert(c.emplace(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42);
+      assert(c.emplace(std::move(v2)).second == false);
+    }
+  }
+}
+
+
+template <class Container>
+void testContainerEmplaceHint()
+{
+  typedef typename Container::value_type ValueTp;
+
+  typedef Container C;
+  typedef typename C::iterator It;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::emplace_hint(p, const value_type&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    It ret = c.emplace_hint(c.end(), v);
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42);
+      It ret2 = c.emplace_hint(c.begin(), v2);
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, value_type&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<ValueTp&>();
+    It ret = c.emplace_hint(c.end(), v);
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      It ret2 = c.emplace_hint(c.begin(), v2);
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, value_type&&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<ValueTp&&>();
+    It ret = c.emplace_hint(c.end(), std::move(v));
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      It ret2 = c.emplace_hint(c.begin(), std::move(v2));
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+  {
+    PRINT("Testing C::emplace_hint(p, const value_type&&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&&>();
+    It ret = c.emplace_hint(c.end(), std::move(v));
+    assert(ret != c.end());
+    assert(c.size() == 1);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42);
+      It ret2 = c.emplace_hint(c.begin(), std::move(v2));
+      assert(&(*ret2) == &(*ret));
+      assert(c.size() == 1);
+    }
+  }
+}
+
+
+int main()
+{
+  testContainerInsert<TCT::set<> >();
+  testContainerEmplace<TCT::set<> >();
+  testContainerEmplaceHint<TCT::set<> >();
+}