[libc++] Fix PR34898 - vector iterator constructors and assign method perform push_back instead of emplace_back.

[EricWF]

Summary

The constructors vector(Iter, Iter, Alloc = Alloc{}) and assign(Iter, Iter) don't correctly perform EmplaceConstruction from the result of dereferencing the iterator. This results in them performing an additional and unneeded copy.

This patch addresses the issue by correctly using emplace_back in C++11 and newer.

There are also some bugs in our insert implementation, but those will be handled separately.

@mclow.lists We should probably merge this into 5.1, agreed?

[EricWF]

• Add additional fixes for vector, deque, and list.

[mclow.lists]

LGTM - thanks!

[dlj]

Hmm, looking more at this change... while it does make the behaviour consistent for Forward and Input iterators, I think it's just making them both do the wrong thing.

Specifically, based on this:

"... i and j denote iterators satisfying input iterator requirements and refer to elements implicitly convertible to value_­type..."

https://timsong-cpp.github.io/cppwp/n4659/container.requirements#sequence.reqmts-3

So, for example, in test_emplacable_concept, the vector constructor should be diagnosed, because there is no way to *implicitly* convert from the dereferenced iterator type to the inserted type. The selected constructor is explicit. Using emplacement just omits a *second* potentially-expensive conversion: the explicit constructor behaviour (invoked through forwarding) may still be undesired.

[EricWF]

In D38757#897536, @dlj wrote:

Hmm, looking more at this change... while it does make the behaviour consistent for Forward and Input iterators, I think it's just making them both do the wrong thing.

Specifically, based on this:

"... i and j denote iterators satisfying input iterator requirements and refer to elements implicitly convertible to value_­type..."

https://timsong-cpp.github.io/cppwp/n4659/container.requirements#sequence.reqmts-3

So, for example, in test_emplacable_concept, the vector constructor should be diagnosed, because there is no way to *implicitly* convert from the dereferenced iterator type to the inserted type. The selected constructor is explicit. Using emplacement just omits a *second* potentially-expensive conversion: the explicit constructor behaviour (invoked through forwarding) may still be undesired.

No, these types should be EmplaceConstructed if construction is supposed to occur when we are constructing a new element in the container, which is what this test does. These elements *need* to be constructed using the Allocator. The implicit construction is useful in PR34906, which we implicitly construct a value and then assign it to an already existing container.

This patch is correct to forward to emplace instead of push_back.

test/std/containers/sequences/vector/vector.cons/construct_iter_iter_alloc.pass.cpp

56

Sorry, this is all just re-formatting.

test/support/emplace_constructible.h

7

THis file needs re-formatting.

[EricWF]

• Update whitespace.

include/deque

     void push_front(value_type&& __v);
     void push_back(value_type&& __v);
     iterator insert(const_iterator __p, value_type&& __v);
 
     _LIBCPP_INLINE_VISIBILITY
     iterator insert(const_iterator __p, initializer_list<value_type> __il)
         {return insert(__p, __il.begin(), __il.end());}
 #endif  // _LIBCPP_CXX03_LANG
-
     iterator insert(const_iterator __p, const value_type& __v);
     iterator insert(const_iterator __p, size_type __n, const value_type& __v);
     template <class _InputIter>
         iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
                          typename enable_if<__is_input_iterator<_InputIter>::value
                                          &&!__is_forward_iterator<_InputIter>::value>::type* = 0);
     template <class _ForwardIterator>
         iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,

 template <class _Tp, class _Allocator>
 template <class _InpIter>
 void
 deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
                                  typename enable_if<__is_input_iterator<_InpIter>::value &&
                                                    !__is_forward_iterator<_InpIter>::value>::type*)
 {
     for (; __f != __l; ++__f)
+#ifdef _LIBCPP_CXX03_LANG
         push_back(*__f);
+#else
+        emplace_back(*__f);
+#endif
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForIter>
 void
 deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
                                  typename enable_if<__is_forward_iterator<_ForIter>::value>::type*)
 {

include/list

#endif
     _LIBCPP_INLINE_VISIBILITY
     iterator insert(const_iterator __p, initializer_list<value_type> __il)
         {return insert(__p, __il.begin(), __il.end());}
 #endif  // _LIBCPP_CXX03_LANG
 
     void push_front(const value_type& __x);
     void push_back(const value_type& __x);
 
+#ifndef _LIBCPP_CXX03_LANG
+    template <class _Arg>
+    _LIBCPP_INLINE_VISIBILITY
+    void __emplace_back(_Arg&& __arg) { emplace_back(_VSTD::forward<_Arg>(__arg)); }
+#else
+    _LIBCPP_INLINE_VISIBILITY
+    void __emplace_back(value_type const& __arg) { push_back(__arg); }
+#endif
+
     iterator insert(const_iterator __p, const value_type& __x);
     iterator insert(const_iterator __p, size_type __n, const value_type& __x);
     template <class _InpIter>
         iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
              typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(list& __c)

 template <class _InpIter>
 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
                         typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
     for (; __f != __l; ++__f)
-        push_back(*__f);
+        __emplace_back(*__f);
 }
 
 template <class _Tp, class _Alloc>
 template <class _InpIter>
 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
                         typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
     : base(__a)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
     for (; __f != __l; ++__f)
-        push_back(*__f);
+        __emplace_back(*__f);
 }
 
 template <class _Tp, class _Alloc>
 list<_Tp, _Alloc>::list(const list& __c)
     : base(allocator_type(
            __node_alloc_traits::select_on_container_copy_construction(
                 __c.__node_alloc())))
 {

include/vector

#endif
 
     _LIBCPP_INLINE_VISIBILITY
     value_type*       data() _NOEXCEPT
         {return _VSTD::__to_raw_pointer(this->__begin_);}
     _LIBCPP_INLINE_VISIBILITY
     const value_type* data() const _NOEXCEPT
         {return _VSTD::__to_raw_pointer(this->__begin_);}
 
+#ifdef _LIBCPP_CXX03_LANG
+    _LIBCPP_INLINE_VISIBILITY
+    void __emplace_back(const value_type& __x) { push_back(__x); }
+#else
+    template <class _Arg>
+    _LIBCPP_INLINE_VISIBILITY
+    void __emplace_back(_Arg&& __arg) {
+      emplace_back(_VSTD::forward<_Arg>(__arg));
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
 
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
 #if _LIBCPP_STD_VER > 14
vector<_Tp, _Allocator>::vector(_InputIterator __first,
                             value_type,
                             typename iterator_traits<_InputIterator>::reference>::value,
                           _InputIterator>::type __last)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
     for (; __first != __last; ++__first)
-        push_back(*__first);
+        __emplace_back(*__first);
 }
 
 template <class _Tp, class _Allocator>
 template <class _InputIterator>
 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
        typename enable_if<__is_input_iterator  <_InputIterator>::value &&
                          !__is_forward_iterator<_InputIterator>::value &&
                          is_constructible<
                             value_type,
                             typename iterator_traits<_InputIterator>::reference>::value>::type*)
     : __base(__a)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
     for (; __first != __last; ++__first)
-        push_back(*__first);
+        __emplace_back(*__first);
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForwardIterator>
 vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
                                 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
                                 is_constructible<
                                    value_type,
is_constructible<
        _Tp,
        typename iterator_traits<_InputIterator>::reference>::value,
     void
 >::type
 vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
 {
     clear();
     for (; __first != __last; ++__first)
-        push_back(*__first);
+        __emplace_back(*__first);
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForwardIterator>
 typename enable_if
 <
     __is_forward_iterator<_ForwardIterator>::value &&
     is_constructible<

test/std/containers/sequences/deque/deque.cons/assign_iter_iter.pass.cpp

 
 #include <deque>
 #include <cassert>
 #include <cstddef>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 #include "min_allocator.h"
+#if TEST_STD_VER >= 11
+#include "emplace_constructible.h"
+#endif
 
 template <class C>
 C
 make(int size, int start = 0 )
 {
     const int b = 4096 / sizeof(int);
     int init = 0;
     if (start > 0)

 void
 testNI(int start, int N, int M)
 {
     C c1 = make<C>(N, start);
     C c2 = make<C>(M);
     testI(c1, c2);
 }
 
-int main()
+void basic_test()
 {
     {
     int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
     const int N = sizeof(rng)/sizeof(rng[0]);
     for (int i = 0; i < N; ++i)
         for (int j = 0; j < N; ++j)
             for (int k = 0; k < N; ++k)
                 testN<std::deque<int> >(rng[i], rng[j], rng[k]);
     testNI<std::deque<int> >(1500, 2000, 1000);
     }
 #if TEST_STD_VER >= 11
     {
     int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
     const int N = sizeof(rng)/sizeof(rng[0]);
     for (int i = 0; i < N; ++i)
         for (int j = 0; j < N; ++j)
             for (int k = 0; k < N; ++k)
                 testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]);
     testNI<std::deque<int, min_allocator<int>> >(1500, 2000, 1000);
     }
 #endif
 }
+
+void test_emplacable_concept() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructibleMoveableAndAssignable<int>;
+    using It = random_access_iterator<int*>;
+    {
+      std::deque<T> v;
+      v.assign(It(arr1), It(std::end(arr1)));
+      assert(v[0].value == 42);
+    }
+    {
+      std::deque<T> v;
+      v.assign(It(arr2), It(std::end(arr2)));
+      assert(v[0].value == 1);
+      assert(v[1].value == 101);
+      assert(v[2].value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructibleMoveableAndAssignable<int>;
+    using It = input_iterator<int*>;
+    {
+      std::deque<T> v;
+      v.assign(It(arr1), It(std::end(arr1)));
+      assert(v[0].copied == 0);
+      assert(v[0].value == 42);
+    }
+    {
+      std::deque<T> v;
+      v.assign(It(arr2), It(std::end(arr2)));
+      //assert(v[0].copied == 0);
+      assert(v[0].value == 1);
+      //assert(v[1].copied == 0);
+      assert(v[1].value == 101);
+      assert(v[2].copied == 0);
+      assert(v[2].value == 42);
+    }
+  }
+#endif
+}
+
+int main() {
+  basic_test();
+  test_emplacable_concept();
+}

test/std/containers/sequences/deque/deque.cons/iter_iter.pass.cpp

 // <deque>
 
 // template <class InputIterator> deque(InputIterator f, InputIterator l);
 
 #include <deque>
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_allocator.h"
 #include "test_iterators.h"
 #include "min_allocator.h"
+#if TEST_STD_VER >= 11
+#include "emplace_constructible.h"
+#endif
 
 template <class InputIterator>
 void
 test(InputIterator f, InputIterator l)
 {
     typedef typename std::iterator_traits<InputIterator>::value_type T;
     typedef std::allocator<T> Allocator;
     typedef std::deque<T, Allocator> C;
test(InputIterator f, InputIterator l)
     typedef typename C::const_iterator const_iterator;
     C d(f, l);
     assert(d.size() == static_cast<std::size_t>(std::distance(f, l)));
     assert(static_cast<std::size_t>(distance(d.begin(), d.end())) == d.size());
     for (const_iterator i = d.begin(), e = d.end(); i != e; ++i, ++f)
         assert(*i == *f);
 }
 
-int main()
+void basic_test()
 {
     int ab[] = {3, 4, 2, 8, 0, 1, 44, 34, 45, 96, 80, 1, 13, 31, 45};
     int* an = ab + sizeof(ab)/sizeof(ab[0]);
     test(input_iterator<const int*>(ab), input_iterator<const int*>(an));
     test(forward_iterator<const int*>(ab), forward_iterator<const int*>(an));
     test(bidirectional_iterator<const int*>(ab), bidirectional_iterator<const int*>(an));
     test(random_access_iterator<const int*>(ab), random_access_iterator<const int*>(an));
     test<limited_allocator<int, 4096> >(ab, an);
 #if TEST_STD_VER >= 11
     test<min_allocator<int> >(ab, an);
 #endif
 }
+
+
+void test_emplacable_concept() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructibleAndMoveable<int>;
+    using It = random_access_iterator<int*>;
+    {
+      std::deque<T> v(It(arr1), It(std::end(arr1)));
+      assert(v[0].value == 42);
+    }
+    {
+      std::deque<T> v(It(arr2), It(std::end(arr2)));
+      assert(v[0].value == 1);
+      assert(v[1].value == 101);
+      assert(v[2].value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructibleAndMoveable<int>;
+    using It = input_iterator<int*>;
+    {
+      std::deque<T> v(It(arr1), It(std::end(arr1)));
+      assert(v[0].copied == 0);
+      assert(v[0].value == 42);
+    }
+    {
+      std::deque<T> v(It(arr2), It(std::end(arr2)));
+      //assert(v[0].copied == 0);
+      assert(v[0].value == 1);
+      //assert(v[1].copied == 0);
+      assert(v[1].value == 101);
+      assert(v[2].copied == 0);
+      assert(v[2].value == 42);
+    }
+  }
+#endif
+}
+
+int main() {
+  basic_test();
+  test_emplacable_concept();
+}

test/std/containers/sequences/deque/deque.cons/iter_iter_alloc.pass.cpp

 
 // template <class InputIterator>
 //   deque(InputIterator f, InputIterator l, const allocator_type& a);
 
 #include <deque>
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
+#if TEST_STD_VER >= 11
+#include "emplace_constructible.h"
+#endif
 
 template <class InputIterator, class Allocator>
 void
 test(InputIterator f, InputIterator l, const Allocator& a)
 {
     typedef typename std::iterator_traits<InputIterator>::value_type T;
     typedef std::deque<T, Allocator> C;
     typedef typename C::const_iterator const_iterator;
     C d(f, l, a);
     assert(d.get_allocator() == a);
     assert(d.size() == static_cast<std::size_t>(std::distance(f, l)));
     assert(static_cast<std::size_t>(distance(d.begin(), d.end())) == d.size());
     for (const_iterator i = d.begin(), e = d.end(); i != e; ++i, ++f)
         assert(*i == *f);
 }
 
-int main()
+void basic_test()
 {
     int ab[] = {3, 4, 2, 8, 0, 1, 44, 34, 45, 96, 80, 1, 13, 31, 45};
     int* an = ab + sizeof(ab)/sizeof(ab[0]);
     test(input_iterator<const int*>(ab), input_iterator<const int*>(an), test_allocator<int>(3));
     test(forward_iterator<const int*>(ab), forward_iterator<const int*>(an), test_allocator<int>(4));
     test(bidirectional_iterator<const int*>(ab), bidirectional_iterator<const int*>(an), test_allocator<int>(5));
     test(random_access_iterator<const int*>(ab), random_access_iterator<const int*>(an), test_allocator<int>(6));
 #if TEST_STD_VER >= 11
     test(input_iterator<const int*>(ab), input_iterator<const int*>(an), min_allocator<int>());
     test(forward_iterator<const int*>(ab), forward_iterator<const int*>(an), min_allocator<int>());
     test(bidirectional_iterator<const int*>(ab), bidirectional_iterator<const int*>(an), min_allocator<int>());
     test(random_access_iterator<const int*>(ab), random_access_iterator<const int*>(an), min_allocator<int>());
 #endif
 }
+
+
+void test_emplacable_concept() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructibleAndMoveable<int>;
+    using It = random_access_iterator<int*>;
+    std::allocator<T> a;
+    {
+      std::deque<T> v(It(arr1), It(std::end(arr1)), a);
+      assert(v[0].value == 42);
+    }
+    {
+      std::deque<T> v(It(arr2), It(std::end(arr2)), a);
+      assert(v[0].value == 1);
+      assert(v[1].value == 101);
+      assert(v[2].value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructibleAndMoveable<int>;
+    using It = input_iterator<int*>;
+    std::allocator<T> a;
+    {
+      std::deque<T> v(It(arr1), It(std::end(arr1)), a);
+      assert(v[0].copied == 0);
+      assert(v[0].value == 42);
+    }
+    {
+      std::deque<T> v(It(arr2), It(std::end(arr2)), a);
+      //assert(v[0].copied == 0);
+      assert(v[0].value == 1);
+      //assert(v[1].copied == 0);
+      assert(v[1].value == 101);
+      assert(v[2].copied == 0);
+      assert(v[2].value == 42);
+    }
+  }
+#endif
+}
+
+int main() {
+  basic_test();
+  test_emplacable_concept();
+}

test/std/containers/sequences/list/list.cons/input_iterator.pass.cpp

 // template <class InputIterator>
 //   list(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 #include <list>
 #include <cassert>
 #include "test_iterators.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
+#if TEST_STD_VER >= 11
+#include "emplace_constructible.h"
+#include "container_test_types.h"
+#endif
 
-int main()
+void basic_test()
 {
     {
         int a[] = {0, 1, 2, 3};
         std::list<int> l(input_iterator<const int*>(a),
                          input_iterator<const int*>(a + sizeof(a)/sizeof(a[0])));
         assert(l.size() == sizeof(a)/sizeof(a[0]));
         assert(std::distance(l.begin(), l.end()) == sizeof(a)/sizeof(a[0]));
         int j = 0;
#if TEST_STD_VER >= 11
         assert(l.size() == sizeof(a)/sizeof(a[0]));
         assert(std::distance(l.begin(), l.end()) == sizeof(a)/sizeof(a[0]));
         int j = 0;
         for (std::list<int, min_allocator<int>>::const_iterator i = l.begin(), e = l.end(); i != e; ++i, ++j)
             assert(*i == j);
     }
 #endif
 }
+
+
+
+void test_emplacable_concept() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructible<int>;
+    using It = random_access_iterator<int*>;
+    {
+      std::list<T> v(It(arr1), It(std::end(arr1)));
+      auto I = v.begin();
+      assert(I->value == 42);
+    }
+    {
+      std::list<T> v(It(arr2), It(std::end(arr2)));
+      auto I = v.begin();
+      assert(I->value == 1);
+      ++I;
+      assert(I->value == 101);
+      ++I;
+      assert(I->value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructible<int>;
+    using It = input_iterator<int*>;
+    {
+      std::list<T> v(It(arr1), It(std::end(arr1)));
+      auto I = v.begin();
+      assert(I->value == 42);
+    }
+    {
+      std::list<T> v(It(arr2), It(std::end(arr2)));
+      auto I = v.begin();
+      //assert(v[0].copied == 0);
+      assert(I->value == 1);
+      //assert(v[1].copied == 0);
+      ++I;
+      assert(I->value == 101);
+      ++I;
+      assert(I->value == 42);
+    }
+  }
+#endif
+}
+
+
+
+void test_emplacable_concept_with_alloc() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructible<int>;
+    using It = random_access_iterator<int*>;
+    std::allocator<T> a;
+    {
+      std::list<T> v(It(arr1), It(std::end(arr1)), a);
+      auto I = v.begin();
+      assert(I->value == 42);
+    }
+    {
+      std::list<T> v(It(arr2), It(std::end(arr2)), a);
+      auto I = v.begin();
+      assert(I->value == 1);
+      ++I;
+      assert(I->value == 101);
+      ++I;
+      assert(I->value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructible<int>;
+    using It = input_iterator<int*>;
+    std::allocator<T> a;
+    {
+      std::list<T> v(It(arr1), It(std::end(arr1)), a);
+      auto I = v.begin();
+      assert(I->value == 42);
+    }
+    {
+      std::list<T> v(It(arr2), It(std::end(arr2)), a);
+      auto I = v.begin();
+      //assert(v[0].copied == 0);
+      assert(I->value == 1);
+      //assert(v[1].copied == 0);
+      ++I;
+      assert(I->value == 101);
+      ++I;
+      assert(I->value == 42);
+    }
+  }
+#endif
+}
+
+void test_ctor_under_alloc() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using C = TCT::list<>;
+    using T = typename C::value_type;
+    using It = forward_iterator<int*>;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)));
+    }
+    {
+      ExpectConstructGuard<int&> G(3);
+      C v(It(arr2), It(std::end(arr2)));
+    }
+  }
+  {
+    using C = TCT::list<>;
+    using T = typename C::value_type;
+    using It = input_iterator<int*>;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)));
+    }
+    {
+      ExpectConstructGuard<int&> G(3);
+      C v(It(arr2), It(std::end(arr2)));
+    }
+  }
+#endif
+}
+
+void test_ctor_under_alloc_with_alloc() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using C = TCT::list<>;
+    using T = typename C::value_type;
+    using It = forward_iterator<int*>;
+    using Alloc = typename C::allocator_type;
+    Alloc a;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)), a);
+    }
+    {
+      ExpectConstructGuard<int&> G(3);
+      C v(It(arr2), It(std::end(arr2)), a);
+    }
+  }
+  {
+    using C = TCT::list<>;
+    using T = typename C::value_type;
+    using It = input_iterator<int*>;
+    using Alloc = typename C::allocator_type;
+    Alloc a;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)), a);
+    }
+    {
+      ExpectConstructGuard<int&> G(3);
+      C v(It(arr2), It(std::end(arr2)), a);
+    }
+  }
+#endif
+}
+
+
+
+int main() {
+  basic_test();
+  test_emplacable_concept();
+  test_emplacable_concept_with_alloc();
+  test_ctor_under_alloc();
+  test_ctor_under_alloc_with_alloc();
+}

test/std/containers/sequences/vector/vector.cons/assign_iter_iter.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.
+//
+//===----------------------------------------------------------------------===//
+
+// <vector>
+
+// void assign(size_type n, const_reference v);
+
+#include <vector>
+#include <algorithm>
+#include <cassert>
+#include <iostream>
+#include "test_macros.h"
+#include "min_allocator.h"
+#include "asan_testing.h"
+#include "test_iterators.h"
+#if TEST_STD_VER >= 11
+#include "emplace_constructible.h"
+#include "container_test_types.h"
+#endif
+
+
+void test_emplaceable_concept() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructibleMoveableAndAssignable<int>;
+    using It = forward_iterator<int*>;
+    {
+      std::vector<T> v;
+      v.assign(It(arr1), It(std::end(arr1)));
+      assert(v[0].value == 42);
+    }
+    {
+      std::vector<T> v;
+      v.assign(It(arr2), It(std::end(arr2)));
+      assert(v[0].value == 1);
+      assert(v[1].value == 101);
+      assert(v[2].value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructibleMoveableAndAssignable<int>;
+    using It = input_iterator<int*>;
+    {
+      std::vector<T> v;
+      v.assign(It(arr1), It(std::end(arr1)));
+      assert(v[0].copied == 0);
+      assert(v[0].value == 42);
+    }
+    {
+      std::vector<T> v;
+      v.assign(It(arr2), It(std::end(arr2)));
+      //assert(v[0].copied == 0);
+      assert(v[0].value == 1);
+      //assert(v[1].copied == 0);
+      assert(v[1].value == 101);
+      assert(v[2].copied == 0);
+      assert(v[2].value == 42);
+    }
+  }
+#endif
+}
+
+
+
+int main()
+{
+    test_emplaceable_concept();
+}

test/std/containers/sequences/vector/vector.cons/construct_iter_iter.pass.cpp

 #include <cassert>
 #include <cstddef>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
 #include "asan_testing.h"
+#if TEST_STD_VER >= 11
+#include "emplace_constructible.h"
+#include "container_test_types.h"
+#endif
 
 template <class C, class Iterator>
-void
-test(Iterator first, Iterator last)
-{
-    C c(first, last);
-    LIBCPP_ASSERT(c.__invariants());
-    assert(c.size() == static_cast<std::size_t>(std::distance(first, last)));
-    LIBCPP_ASSERT(is_contiguous_container_asan_correct(c));
-    for (typename C::const_iterator i = c.cbegin(), e = c.cend(); i != e; ++i, ++first)
-        assert(*i == *first);
+void test(Iterator first, Iterator last) {
+  for (typename C::const_iterator i = c.cbegin(), e = c.cend(); i != e;
+       ++i, ++first)
 }
 
-int main()
-{
-    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 1, 0};
-    int* an = a + sizeof(a)/sizeof(a[0]);
-    test<std::vector<int> >(input_iterator<const int*>(a), input_iterator<const int*>(an));
-    test<std::vector<int> >(forward_iterator<const int*>(a), forward_iterator<const int*>(an));
-    test<std::vector<int> >(bidirectional_iterator<const int*>(a), bidirectional_iterator<const int*>(an));
-    test<std::vector<int> >(random_access_iterator<const int*>(a), random_access_iterator<const int*>(an));
-    test<std::vector<int> >(a, an);
+static void basic_test_cases() {
+  int* an = a + sizeof(a) / sizeof(a[0]);
+  test<std::vector<int> >(input_iterator<const int*>(a),
+                          input_iterator<const int*>(an));
+  test<std::vector<int> >(forward_iterator<const int*>(a),
+                          forward_iterator<const int*>(an));
+  test<std::vector<int> >(bidirectional_iterator<const int*>(a),
+                          bidirectional_iterator<const int*>(an));
+  test<std::vector<int> >(random_access_iterator<const int*>(a),
+                          random_access_iterator<const int*>(an));
 
-    test<std::vector<int, limited_allocator<int, 63> > >(input_iterator<const int*>(a), input_iterator<const int*>(an));
-    // Add 1 for implementations that dynamically allocate a container proxy.
-    test<std::vector<int, limited_allocator<int, 18 + 1> > >(forward_iterator<const int*>(a), forward_iterator<const int*>(an));
-    test<std::vector<int, limited_allocator<int, 18 + 1> > >(bidirectional_iterator<const int*>(a), bidirectional_iterator<const int*>(an));
-    test<std::vector<int, limited_allocator<int, 18 + 1> > >(random_access_iterator<const int*>(a), random_access_iterator<const int*>(an));
-    test<std::vector<int, limited_allocator<int, 18 + 1> > >(a, an);
+  test<std::vector<int, limited_allocator<int, 63> > >(
+      input_iterator<const int*>(a), input_iterator<const int*>(an));
+  test<std::vector<int, limited_allocator<int, 18 + 1> > >(
+      forward_iterator<const int*>(a), forward_iterator<const int*>(an));
+  test<std::vector<int, limited_allocator<int, 18 + 1> > >(
+      bidirectional_iterator<const int*>(a),
+      bidirectional_iterator<const int*>(an));
+  test<std::vector<int, limited_allocator<int, 18 + 1> > >(
+      random_access_iterator<const int*>(a),
+      random_access_iterator<const int*>(an));
 #if TEST_STD_VER >= 11
-    test<std::vector<int, min_allocator<int>> >(input_iterator<const int*>(a), input_iterator<const int*>(an));
-    test<std::vector<int, min_allocator<int>> >(forward_iterator<const int*>(a), forward_iterator<const int*>(an));
-    test<std::vector<int, min_allocator<int>> >(bidirectional_iterator<const int*>(a), bidirectional_iterator<const int*>(an));
-    test<std::vector<int, min_allocator<int>> >(random_access_iterator<const int*>(a), random_access_iterator<const int*>(an));
-    test<std::vector<int> >(a, an);
+  test<std::vector<int, min_allocator<int> > >(input_iterator<const int*>(a),
+                                               input_iterator<const int*>(an));
+  test<std::vector<int, min_allocator<int> > >(
+      forward_iterator<const int*>(a), forward_iterator<const int*>(an));
+  test<std::vector<int, min_allocator<int> > >(
+      bidirectional_iterator<const int*>(a),
+      bidirectional_iterator<const int*>(an));
+  test<std::vector<int, min_allocator<int> > >(
+      random_access_iterator<const int*>(a),
+      random_access_iterator<const int*>(an));
 #endif
 }
+
+void emplaceable_concept_tests() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructible<int>;
+    using It = forward_iterator<int*>;
+    {
+      std::vector<T> v(It(arr1), It(std::end(arr1)));
+      assert(v[0].value == 42);
+    }
+    {
+      std::vector<T> v(It(arr2), It(std::end(arr2)));
+      assert(v[0].value == 1);
+      assert(v[1].value == 101);
+      assert(v[2].value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructibleAndMoveInsertable<int>;
+    using It = input_iterator<int*>;
+    {
+      std::vector<T> v(It(arr1), It(std::end(arr1)));
+      assert(v[0].copied == 0);
+      assert(v[0].value == 42);
+    }
+    {
+      std::vector<T> v(It(arr2), It(std::end(arr2)));
+      //assert(v[0].copied == 0);
+      assert(v[0].value == 1);
+      //assert(v[1].copied == 0);
+      assert(v[1].value == 101);
+      assert(v[2].copied == 0);
+      assert(v[2].value == 42);
+    }
+  }
+#endif
+}
+
+void test_ctor_under_alloc() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using C = TCT::vector<>;
+    using T = typename C::value_type;
+    using It = forward_iterator<int*>;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)));
+    }
+    {
+      ExpectConstructGuard<int&> G(3);
+      C v(It(arr2), It(std::end(arr2)));
+    }
+  }
+  {
+    using C = TCT::vector<>;
+    using T = typename C::value_type;
+    using It = input_iterator<int*>;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)));
+    }
+    {
+      //ExpectConstructGuard<int&> G(3);
+      //C v(It(arr2), It(std::end(arr2)), a);
+    }
+  }
+#endif
+}
+
+
+int main() {
+  basic_test_cases();
+  emplaceable_concept_tests(); // See PR34898
+  test_ctor_under_alloc();
+}

test/std/containers/sequences/vector/vector.cons/construct_iter_iter_alloc.pass.cpp

 #include <cassert>
 #include <cstddef>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
 #include "asan_testing.h"
+#if TEST_STD_VER >= 11
+#include "emplace_constructible.h"
+#include "container_test_types.h"
+#endif
 
 template <class C, class Iterator, class A>
-void
-test(Iterator first, Iterator last, const A& a)
-{
-    C c(first, last, a);
-    LIBCPP_ASSERT(c.__invariants());
-    assert(c.size() == static_cast<std::size_t>(std::distance(first, last)));
-    LIBCPP_ASSERT(is_contiguous_container_asan_correct(c));
-    for (typename C::const_iterator i = c.cbegin(), e = c.cend(); i != e; ++i, ++first)
-        assert(*i == *first);
+void test(Iterator first, Iterator last, const A& a) {
+  for (typename C::const_iterator i = c.cbegin(), e = c.cend(); i != e;
+       ++i, ++first)
 }
 
 #if TEST_STD_VER >= 11
 
 template <class T>
-struct implicit_conv_allocator : min_allocator<T>
-{
-    implicit_conv_allocator(void*) {}
-    implicit_conv_allocator(const implicit_conv_allocator&) = default;
+struct implicit_conv_allocator : min_allocator<T> {
 
-    template <class U>
-    implicit_conv_allocator(implicit_conv_allocator<U>) {}
 };
 
 #endif
 
-int main()
-{
-    {
+void basic_tests() {
     int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 1, 0};
-    int* an = a + sizeof(a)/sizeof(a[0]);
+    int* an = a + sizeof(a) / sizeof(a[0]);
     std::allocator<int> alloc;
-    test<std::vector<int> >(input_iterator<const int*>(a), input_iterator<const int*>(an), alloc);
-    test<std::vector<int> >(forward_iterator<const int*>(a), forward_iterator<const int*>(an), alloc);
-    test<std::vector<int> >(bidirectional_iterator<const int*>(a), bidirectional_iterator<const int*>(an), alloc);
-    test<std::vector<int> >(random_access_iterator<const int*>(a), random_access_iterator<const int*>(an), alloc);
+    test<std::vector<int> >(input_iterator<const int*>(a),
+                            input_iterator<const int*>(an), alloc);
+    test<std::vector<int> >(forward_iterator<const int*>(a),
+                            forward_iterator<const int*>(an), alloc);
+    test<std::vector<int> >(bidirectional_iterator<const int*>(a),
+                            bidirectional_iterator<const int*>(an), alloc);
+    test<std::vector<int> >(random_access_iterator<const int*>(a),
+                            random_access_iterator<const int*>(an), alloc);
     test<std::vector<int> >(a, an, alloc);
-    }
 #if TEST_STD_VER >= 11
-    {
     int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 1, 0};
-    int* an = a + sizeof(a)/sizeof(a[0]);
+    int* an = a + sizeof(a) / sizeof(a[0]);
     min_allocator<int> alloc;
-    test<std::vector<int, min_allocator<int>> >(input_iterator<const int*>(a), input_iterator<const int*>(an), alloc);
-    test<std::vector<int, min_allocator<int>> >(forward_iterator<const int*>(a), forward_iterator<const int*>(an), alloc);
-    test<std::vector<int, min_allocator<int>> >(bidirectional_iterator<const int*>(a), bidirectional_iterator<const int*>(an), alloc);
-    test<std::vector<int, min_allocator<int>> >(random_access_iterator<const int*>(a), random_access_iterator<const int*>(an), alloc);
-    test<std::vector<int, min_allocator<int>> >(a, an, alloc);
-    test<std::vector<int, implicit_conv_allocator<int>> >(a, an, nullptr);
-    }
+    test<std::vector<int, min_allocator<int> > >(
+        input_iterator<const int*>(a), input_iterator<const int*>(an), alloc);
+    test<std::vector<int, min_allocator<int> > >(
+        forward_iterator<const int*>(a), forward_iterator<const int*>(an),
+        alloc);
+    test<std::vector<int, min_allocator<int> > >(
+        bidirectional_iterator<const int*>(a),
+        bidirectional_iterator<const int*>(an), alloc);
+    test<std::vector<int, min_allocator<int> > >(
+        random_access_iterator<const int*>(a),
+        random_access_iterator<const int*>(an), alloc);
+    test<std::vector<int, min_allocator<int> > >(a, an, alloc);
+    test<std::vector<int, implicit_conv_allocator<int> > >(a, an, nullptr);
 #endif
 }
+
+void emplaceable_concept_tests() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using T = EmplaceConstructible<int>;
+    using It = forward_iterator<int*>;
+    using Alloc = std::allocator<T>;
+    Alloc a;
+    {
+      std::vector<T> v(It(arr1), It(std::end(arr1)), a);
+      assert(v[0].value == 42);
+    }
+    {
+      std::vector<T> v(It(arr2), It(std::end(arr2)), a);
+      assert(v[0].value == 1);
+      assert(v[1].value == 101);
+      assert(v[2].value == 42);
+    }
+  }
+  {
+    using T = EmplaceConstructibleAndMoveInsertable<int>;
+    using It = input_iterator<int*>;
+    using Alloc = std::allocator<T>;
+    Alloc a;
+    {
+      std::vector<T> v(It(arr1), It(std::end(arr1)), a);
+      assert(v[0].copied == 0);
+      assert(v[0].value == 42);
+    }
+    {
+      std::vector<T> v(It(arr2), It(std::end(arr2)), a);
+      assert(v[0].value == 1);
+      assert(v[1].value == 101);
+      assert(v[2].copied == 0);
+      assert(v[2].value == 42);
+    }
+  }
+#endif
+}
+
+void test_ctor_under_alloc() {
+#if TEST_STD_VER >= 11
+  int arr1[] = {42};
+  int arr2[] = {1, 101, 42};
+  {
+    using C = TCT::vector<>;
+    using T = typename C::value_type;
+    using It = forward_iterator<int*>;
+    using Alloc = typename C::allocator_type;
+    Alloc a;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)), a);
+    }
+    {
+      ExpectConstructGuard<int&> G(3);
+      C v(It(arr2), It(std::end(arr2)), a);
+    }
+  }
+  {
+    using C = TCT::vector<>;
+    using T = typename C::value_type;
+    using It = input_iterator<int*>;
+    using Alloc = typename C::allocator_type;
+    Alloc a;
+    {
+      ExpectConstructGuard<int&> G(1);
+      C v(It(arr1), It(std::end(arr1)), a);
+    }
+    {
+      //ExpectConstructGuard<int&> G(3);
+      //C v(It(arr2), It(std::end(arr2)), a);
+    }
+  }
+#endif
+}
+
+int main() {
+  basic_tests();
+  emplaceable_concept_tests(); // See PR34898
+  test_ctor_under_alloc();
+}

test/support/container_test_types.h

 typedef AllocatorConstructController ConstructController;
 
 // getConstructController - Return the global allocator construction controller.
 inline ConstructController* getConstructController() {
   static ConstructController c;
   return &c;
 }
 
+template <class ...Args>
+struct ExpectConstructGuard {
+  ExpectConstructGuard(int N)  {
+    auto CC = getConstructController();
+    assert(!CC->unchecked());
+    CC->expect<Args...>(N);
+  }
+
+  ~ExpectConstructGuard() {
+    assert(!getConstructController()->unchecked());
+  }
+};
+
 //===----------------------------------------------------------------------===//
 //                       ContainerTestAllocator
 //===----------------------------------------------------------------------===//
 
 // ContainerTestAllocator - A STL allocator type that only allows 'construct'
 // and 'destroy' to be called for 'AllowConstructT' types. ContainerTestAllocator
 // uses the 'AllocatorConstructionController' interface.
 template <class T, class AllowConstructT>
#endif
   struct hash< ::CopyInsertable<ID> > {
     typedef ::CopyInsertable<ID> argument_type;
     typedef size_t result_type;
 
     size_t operator()(argument_type const& arg) const {
       return arg.data;
     }
   };
-
+  template <class T, class Alloc>
+  class vector;
+  template <class T, class Alloc>
+  class deque;
+  template <class T, class Alloc>
+  class list;
   template <class _Key, class _Value, class _Less, class _Alloc>
   class map;
   template <class _Key, class _Value, class _Less, class _Alloc>
   class multimap;
   template <class _Value, class _Less, class _Alloc>
   class set;
   template <class _Value, class _Less, class _Alloc>
   class multiset;

 _LIBCPP_END_NAMESPACE_STD
 #else
 } // end namespace std
 #endif
 
 // TCT - Test container type
 namespace TCT {
 
+template <class T = CopyInsertable<1>>
+using vector = std::vector<T, ContainerTestAllocator<T, T> >;
+template <class T = CopyInsertable<1>>
+using deque = std::deque<T, ContainerTestAllocator<T, T> >;
+template <class T = CopyInsertable<1>>
+using list = std::list<T, ContainerTestAllocator<T, T> >;
+
 template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>,
           class ValueTp = std::pair<const Key, Value> >
 using unordered_map =
       std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>,
                               ContainerTestAllocator<ValueTp, ValueTp> >;
 
 template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>,
           class ValueTp = std::pair<const Key, Value> >
std::unordered_multiset<Value, std::hash<Value>, std::equal_to<Value>,
                                     ContainerTestAllocator<Value, Value> >;
 
 template <class Value = CopyInsertable<1> >
 using multiset =
     std::multiset<Value, std::less<Value>, ContainerTestAllocator<Value, Value> >;
 
 } // end namespace TCT
 
-
 #endif // SUPPORT_CONTAINER_TEST_TYPES_H

test/support/emplace_constructible.h

+#ifndef TEST_SUPPORT_EMPLACE_CONSTRUCTIBLE_H
+#define TEST_SUPPORT_EMPLACE_CONSTRUCTIBLE_H
+
+#include "test_macros.h"
+
+#if TEST_STD_VER >= 11
+template <class T>
+struct EmplaceConstructible {
+  T value;
+  explicit EmplaceConstructible(T value) : value(value) {}
+  EmplaceConstructible(EmplaceConstructible const&) = delete;
+};
+
+template <class T>
+struct EmplaceConstructibleAndMoveInsertable {
+  int copied = 0;
+  T value;
+  explicit EmplaceConstructibleAndMoveInsertable(T value) : value(value) {}
+
+  EmplaceConstructibleAndMoveInsertable(
+      EmplaceConstructibleAndMoveInsertable&& Other)
+      : copied(Other.copied + 1), value(std::move(Other.value)) {}
+};
+
+template <class T>
+struct EmplaceConstructibleAndMoveable {
+  int copied = 0;
+  int assigned = 0;
+  T value;
+  explicit EmplaceConstructibleAndMoveable(T value) noexcept : value(value) {}
+
+  EmplaceConstructibleAndMoveable(EmplaceConstructibleAndMoveable&& Other)
+      noexcept : copied(Other.copied + 1),
+                 value(std::move(Other.value)) {}
+
+  EmplaceConstructibleAndMoveable&
+  operator=(EmplaceConstructibleAndMoveable&& Other) noexcept {
+    copied = Other.copied;
+    assigned = Other.assigned + 1;
+    value = std::move(Other.value);
+    return *this;
+  }
+};
+
+template <class T>
+struct EmplaceConstructibleMoveableAndAssignable {
+  int copied = 0;
+  int assigned = 0;
+  T value;
+  explicit EmplaceConstructibleMoveableAndAssignable(T value) noexcept
+      : value(value) {}
+
+  EmplaceConstructibleMoveableAndAssignable(
+      EmplaceConstructibleMoveableAndAssignable&& Other) noexcept
+      : copied(Other.copied + 1),
+        value(std::move(Other.value)) {}
+
+  EmplaceConstructibleMoveableAndAssignable&
+  operator=(EmplaceConstructibleMoveableAndAssignable&& Other) noexcept {
+    copied = Other.copied;
+    assigned = Other.assigned + 1;
+    value = std::move(Other.value);
+    return *this;
+  }
+
+  EmplaceConstructibleMoveableAndAssignable& operator=(T xvalue) {
+    value = std::move(xvalue);
+    ++assigned;
+    return *this;
+  }
+};
+#endif
+
+#endif // TEST_SUPPORT_EMPLACE_CONSTRUCTIBLE_H