[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

55

Sorry, this is all just re-formatting.

test/support/emplace_constructible.h

6 ↗

(On Diff #118474)

THis file needs re-formatting.

[EricWF]

• Update whitespace.

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/vector/emplace_constructible.h

+#ifndef EMPLACE_CONSTRUCTIBLE_H
+#define 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 // EMPLACE_CONSTRUCTIBLE_H

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"
+#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"
+#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
+}
+
+int main() {
+  basic_test_cases();
+  emplaceable_concept_tests(); // See PR34898
+}

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"
+#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
+}
+
+int main() {
+  basic_tests();
+  emplaceable_concept_tests(); // See PR34898
+}