Move __construct_forward (etc.) out of std::allocator_traits.

[• Quuxplusone]

Summary

Inspired by Volodymyr's work on D48753, I've taken it upon myself to refactor the static member functions std::allocator_traits<A>::__construct_forward, __construct_backward, and __construct_range_forward into non-member functions. I think this is reasonable just in terms of code-cleanliness — they don't *have* to be member functions for any reason I can think of — and then it also permits a suitably sadomasochistic programmer to define his own specialization of std::allocator_traits without causing compiler errors in <vector>.

I have added a test case in test/libcxx/ for the sadomasochistic case, which I describe as "arguably ill-formed." I would be very very happy to see WG21 agree that specializing traits classes (pointer_traits, allocator_traits, iterator_traits) *is* ill-formed; I believe there's some disagreement on the subject at the moment. In the meantime, I think this would be a nice patch just on code-cleanliness grounds.

This patch is also groundwork for the "trivially relocatable" fork that I'm building on my GitHub; we'd need an architecture something like this in order to easily drop in support for trivial relocatability.

UPDATE: I suppose I should point out for context that a draft of the "trivially relocatable" proposal is now public, and a fork of libc++ incorporating the proposed feature is available on Compiler Explorer with vastly improved codegen compared to vanilla libc++.

[• Quuxplusone]

Move the functions from <memory> to <vector>, since that's their only caller.
Uniform treatment of the pointer/iterator parameters; discover that the difference between "copy_forward" and "copy_range_forward" was that the former did moves and the latter did copies. Rename accordingly.

[vsapsai]

My review is incomplete, especially I cannot say with confidence if the proposed change is entirely free from unintended consequences that might break code not covered by the test suite. So other reviewers are welcome to chime in.

include/vector

298

Why does this function use _CopyViaMemcpy and not false_type like other functions?

300

Have you checked why using is accepted in C++03 mode? The tests are passing but I expected a compiler warning and didn't investigate further.

366–367

Good. I think decrementing __end2 after _Np check is better than what we had before.

464

I think the name __vector_constructable_via_memcpy better reflects the meaning. It detects cases when individual element construction can be safely replaced with memcpy, so it feels more about construct than about copy. And copy_via_memcpy is too imperative as for me, not really conveying it has boolean semantic.

937

It's not immediately obvious why there is no check like is_same<_ForwardIterator, _Tp*> here. My guess is that we are using variables like this->__end_, v.__begin_ that we know are pointers. Don't think it's really a problem and not suggesting any changes, decided to mention it's a little bit tricky to understand.

[• Quuxplusone]

Address @vsapsai's review comments.

include/vector

298

Oops, that's totally cruft left over from an earlier revision. Fixed!

300

I talked with Glen Fernandes about this on Slack the other day. I think the deal is that make check-cxx runs only the -std=c++2a tests, and if you want -std=c++03 you have to run them manually with llvm-lit --param=-std=c++03 -sv path/to/tests. Which of course I didn't do. :)
If there's a more foolproof way of automatically testing libc++ in *all* compiler modes, I'd like to know about it.

Fixed!

464

copy_via_memcpy is too imperative for me

I see your point. However, for background... in my other branch, this trait is joined by two companions:

struct __vector_relocate_via_memcpy
struct __vector_destroy_via_noop

So I'd like a naming scheme that fits all three use-cases comfortably.

How about just adding the word "should"? __vector_should_construct_via_memcpy, __vector_should_destroy_via_noop, etc? Would that sufficiently address the "too imperative" issue?

937

Your guess is 100% correct, AFAIK. All we're doing here is copying from one __split_buffer to another, so both sides are always a contiguous range.

[vsapsai]

include/vector

300

The test suite didn't detect anything even in C++03 mode because of [-Wno-c++11-extensions](https://github.com/llvm-mirror/libcxx/blob/ffbb91bb640b1b0425a91aa70e2a6a2e0f7244e0/utils/libcxx/test/config.py#L922). Thanks for using typedef instead.

464

Yes, "should" is fine as it implies yes/no answer.

[ldionne]

It would be nice if all the TMP required to determine whether to call __move_construct_forward(..., true_type) or __move_construct_forward(..., false_type) was done in __move_construct_forward itself (or a helper). This way, callers wouldn't have to do it themselves. For example, vector currently needs

typedef integral_constant<bool,
        __vector_should_construct_via_memcpy<_Tp, _Allocator>::value &&
        (is_same<_ForwardIterator, _Tp*>::value ||
         is_same<_ForwardIterator, const _Tp*>::value ||
         is_same<_ForwardIterator, pointer>::value)
    > __copy_via_memcpy;
...
_VSTD::__copy_construct_forward(__a, __first, __last, this->__end_, __copy_via_memcpy());

It would be neat if we could just do

VSTD::__copy_construct_forward(__a, __first, __last, this->__end_);

and have it dispatched correctly from there. That would make those functions potentially useful elsewhere. Does that make sense? Otherwise this LGTM.

include/vector

296

Do you really need inline here?

[• Quuxplusone]

include/vector

296

I'm actually not sure — and also suddenly not sure if the visibility attribute should be _LIBCPP_INLINE_VISIBILITY or _LIBCPP_TEMPLATE_VIS. (I *think* the latter is only for type templates, though, not function templates?) However, this is exactly parallel to what we do for operator<, so I think changing it would be gratuitous. If someone wants to remove inline from a bunch of templates, I won't complain, but I also don't want this PR to be the one that initiates it.

template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
{
    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
}

467

Louis writes:

It would be nice if all the TMP required to determine whether to call __move_construct_forward(..., true_type) or __move_construct_forward(..., false_type) was done in __move_construct_forward itself (or a helper). This way, callers wouldn't have to do it themselves.

I know where you're coming from, but I believe that in this case we definitely *can't* do that, because the whole point of these routines is that the routine itself can't always tell whether it's supposed to memcpy or not; the *caller* is the only one with the power to decide that. The decision (in theory, though not yet in practice, because this particular PR is a pure refactoring) depends not only on details of _Tp and _Allocator but also on the specific call-site: we can memcpy more aggressively at some call-sites than others, because of information available only to the caller (such as "this is a relocation operation").

See https://github.com/Quuxplusone/libcxx/commit/e7e5999b01#diff-07c2b769648850d040dcbb07754e5f2fR1076 , lines 1076 et seq., for how I envision some future caller making the decisions on a callsite-by-callsite basis.

[ldionne]

LGTM

include/vector

296

Sure. Then, the current one is correct. You want to be using _LIBCPP_INLINE_VISIBILITY here. Actually, you want to be using _LIBCPP_HIDE_FROM_ABI, but don't start doing this in this commit -- I'll do a bulk replacement later.

467

Got it.

[• Quuxplusone]

@ldionne: I don't know if your "LGTM" is necessarily sufficient to commit this or not; but either way, I don't have commit privs, so could I ask you (or someone else) to commit this on my behalf? Thanks!

[ldionne]

In D49317#1178767, @Quuxplusone wrote:

@ldionne: I don't know if your "LGTM" is necessarily sufficient to commit this or not; but either way, I don't have commit privs, so could I ask you (or someone else) to commit this on my behalf? Thanks!

I would not dare say that my LGTM is sufficient. My goal in reviewing this was to lower the barrier for a more senior contributor (Eric/Marshall) to give a definitive LGTM.

[mclow.lists]

I am not in favor of this patch.

I'm in favor of fixing the problem that Arthur has described, but not like this, for the following reasons:

• Conceptually, these are (similar to) "Allocator-based versions of the algorithms proposed in P0040", and should (probably? possibly?) look more like them.

• Mainly, though, I think that the goal of this patch (which is see as 'getting to memcpy') is not the direction that libc++ should take. Instead, we should be writing simple loops that the compiler can optimize into a call to memcpy if it chooses. Having calls to memcpy in the code paths makes it impossible to "constexp-ify" this code. (See https://libcxx.llvm.org/cxx2a_status.html (comments on std::copy and https://bugs.llvm.org/show_bug.cgi?id=25165).

[ldionne]

In D49317#1180200, @mclow.lists wrote:

I am not in favor of this patch.

I'm in favor of fixing the problem that Arthur has described, but not like this, for the following reasons:

• Conceptually, these are (similar to) "Allocator-based versions of the algorithms proposed in P0040", and should (probably? possibly?) look more like them.

• Mainly, though, I think that the goal of this patch (which is see as 'getting to memcpy') is not the direction that libc++ should take. Instead, we should be writing simple loops that the compiler can optimize into a call to memcpy if it chooses. Having calls to memcpy in the code paths makes it impossible to "constexp-ify" this code. (See https://libcxx.llvm.org/cxx2a_status.html (comments on std::copy and https://bugs.llvm.org/show_bug.cgi?id=25165).

Marshall makes a great point about memcpy and constexpr... We're trying to make the default allocator constexpr-friendly for C++20, and this doesn't play very nicely with that.

[• Quuxplusone]

include/vector

318

Marshall writes:

Instead, we should be writing simple loops that the compiler can optimize into a call to memcpy if it chooses. Having calls to memcpy in the code paths makes it impossible to "constexp-ify" this code.

Well, I have three thoughts on that.

(A), "removing the calls to memcpy" sounds like you want to just call the *actual* move-constructor in a loop, and then later call the actual destructor in a loop. Which is to say, you don't want libc++ to have a codepath for this speed optimization at all. That's just leaving a ton of performance on the table, and I strongly disagree with that idea.

(B), regardless, couldn't you achieve that goal simply by taking this patch almost exactly as it is except removing the overloads that take true_type? If you want constexpr-friendliness badly enough that you're willing to call the move-constructor and destructor even of trivially copyable types, then you can still use this framework; you just have to remove the overloads that call memcpy. That wouldn't be a major refactoring.

(C), surely if you want the best of both worlds, you should be pushing someone to invent a constexpr memcpy and/or a way to detect constexpr-context at compile time? I don't think it makes sense to pessimize existing (non-constexpr) users in C++03-through-C++17 just because someone hypothetically might in C++2a-or-later want to mutate a std::vector in a constexpr context.

[mclow.lists]

include/vector

318

Which is to say, you don't want libc++ to have a codepath for this speed optimization at all.

You're completely correct. I don't want libc++ to have such a code path.
I want clang to generate a memcpy from the code w/o ever mentioning memcpy in the source.

[• Quuxplusone]

include/vector

318

@mclow.lists: So would you accept a version of this patch that simply removed the true_type overloads? That would change this from a pure refactoring to a performance regression, but it would still reduce the overall diff between libc++ master and libc++ trivially-relocatable.

(Maybe it's no longer clear and needs restating: This patch is currently a pure refactoring. All I'm doing is moving the existing helper functions out of allocator_traits. IIUC, your objections apply to the existence of these existing helper functions just as much as to the refactored versions.)

[mclow.lists]

I don't think it makes sense to pessimize existing (non-constexpr) users in C++03-through-C++17 just because someone hypothetically might in C++2a-or-later want to mutate a std::vector in a constexpr context.

That's not the right (implied) question.

The correct question is:

Will libc++pessimize existing (non-constexpr) users in C++03-through-C++17 *who are using old compilers* in order to support new constexpr features that come down the pike?

And the answer to that is yes - eventually.
I don't know when that will be, since the new compilers don't yet exist.
That's the point of https://bugs.llvm.org/show_bug.cgi?id=25165.

[• Quuxplusone]

@mclow.lists: Well, anyway, is this pure refactoring acceptable, or would you prefer to keep these helpers inside allocator_traits until a better solution to constexpr-memcpy can be invented?

[ldionne]

After thinking about this for some more, I'm not sure this patch is worth doing in its current form. The minimal patch for allowing specializations of allocator_traits would be:

1. move the __move_construct_forward & friends functions from allocator_traits to private static member functions of std::vector (because they're only used in std::vector right now).
2. keep the SFINAE on the allocator and avoid encoding any memcpy decision at the call site.

However, an even better alternative would be to look into adding an overload to uninitialized_move & friends that takes an allocator. We could then be clever in how this is implemented. The major benefit I see here is that there would be one common code path to optimize, as opposed to a std::vector-specific code path.

Given the small benefit provided by this patch, my opinion is that it's not worth moving forward with it as-is. However, I believe either of the two alternatives suggested above would be welcome, with a preference for the more comprehensive second approach, which requires a paper.

Arthur, what do you think? Do you think the second approach can work?

[• Quuxplusone]

In D49317#1180852, @ldionne wrote:

After thinking about this for some more, I'm not sure this patch is worth doing in its current form. The minimal patch for allowing specializations of allocator_traits would be:

1. move the __move_construct_forward & friends functions from allocator_traits to private static member functions of std::vector (because they're only used in std::vector right now).
2. keep the SFINAE on the allocator and avoid encoding any memcpy decision at the call site.

FWLIW, I approve of (1) but not (2), for the previously stated reason that the optimal path is known only at the call-site; the callee doesn't have enough information to know whether memcpy is appropriate. (But it sounds like Marshall doesn't want any memcpy happening at all, so maybe it's moot?)

However, an even better alternative would be to look into adding an overload to uninitialized_move & friends that takes an allocator. We could then be clever in how this is implemented. The major benefit I see here is that there would be one common code path to optimize, as opposed to a std::vector-specific code path.

Yes, when I implemented https://github.com/Quuxplusone/from-scratch/, one of the many things I noticed was that none of the uninitialized_foo algorithms were useful out of the box; every one of them needed to be reimplemented to take an allocator parameter. (A.k.a., "scoped_allocator_adaptor is why we can't have nice things.") However, as you point out, this is a long-standing problem and would require a library paper to do "right." (It would still be easy enough to add the needed algorithms with uglified names, e.g. __uninitialized_copy_a, __destroy_a, etc. This is exactly what libstdc++ does, and libc++ might be wise to copy its approach.)

I'd be happy to throw together a patch for __uninitialized_copy_a etc., since I think that would improve libc++ in general; but I don't see how that would directly help any specific short-term problem in libc++. This patch as it is helps two specific short-term problems:
(1) that user specializations of allocator_traits don't work (but, as the test case comments, this is arguably not a good idea anyway; see also https://quuxplusone.github.io/blog/2018/07/14/traits-classes/ )
(2) that the diff between libc++ trunk and libc++ trivially-relocatable is unnecessarily large
Messing with the uninitialized_foo algorithms would not directly help either of these problems, so we'd have to come up with some other rationale for it.

[• Quuxplusone]

Abandoning, as this has been done in d9a4f936d05.

include/memory

 
     _LIBCPP_INLINE_VISIBILITY
     static allocator_type
         select_on_container_copy_construction(const allocator_type& __a)
             {return __select_on_container_copy_construction(
                 __has_select_on_container_copy_construction<const allocator_type>(),
                 __a);}
 
-    template <class _Ptr>
-        _LIBCPP_INLINE_VISIBILITY
-        static
-        void
-        __construct_forward(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2)
-        {
-            for (; __begin1 != __end1; ++__begin1, ++__begin2)
-                construct(__a, _VSTD::__to_raw_pointer(__begin2), _VSTD::move_if_noexcept(*__begin1));
-        }
-
-    template <class _Tp>
-        _LIBCPP_INLINE_VISIBILITY
-        static
-        typename enable_if
-        <
-            (is_same<allocator_type, allocator<_Tp> >::value
-                || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
-             is_trivially_move_constructible<_Tp>::value,
-            void
-        >::type
-        __construct_forward(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
-        {
-            ptrdiff_t _Np = __end1 - __begin1;
-            if (_Np > 0)
-            {
-                _VSTD::memcpy(__begin2, __begin1, _Np * sizeof(_Tp));
-                __begin2 += _Np;
-            }
-        }
-
-    template <class _Iter, class _Ptr>
-        _LIBCPP_INLINE_VISIBILITY
-        static
-        void
-        __construct_range_forward(allocator_type& __a, _Iter __begin1, _Iter __end1, _Ptr& __begin2)
-        {
-            for (; __begin1 != __end1; ++__begin1, (void) ++__begin2)
-                construct(__a, _VSTD::__to_raw_pointer(__begin2), *__begin1);
-        }
-
-    template <class _Tp>
-        _LIBCPP_INLINE_VISIBILITY
-        static
-        typename enable_if
-        <
-            (is_same<allocator_type, allocator<_Tp> >::value
-                || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
-             is_trivially_move_constructible<_Tp>::value,
-            void
-        >::type
-        __construct_range_forward(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
-        {
-            typedef typename remove_const<_Tp>::type _Vp;
-            ptrdiff_t _Np = __end1 - __begin1;
-            if (_Np > 0)
-            {
-                _VSTD::memcpy(const_cast<_Vp*>(__begin2), __begin1, _Np * sizeof(_Tp));
-                __begin2 += _Np;
-            }
-        }
-
-    template <class _Ptr>
-        _LIBCPP_INLINE_VISIBILITY
-        static
-        void
-        __construct_backward(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __end2)
-        {
-            while (__end1 != __begin1)
-            {
-                construct(__a, _VSTD::__to_raw_pointer(__end2-1), _VSTD::move_if_noexcept(*--__end1));
-                --__end2;
-            }
-        }
-
-    template <class _Tp>
-        _LIBCPP_INLINE_VISIBILITY
-        static
-        typename enable_if
-        <
-            (is_same<allocator_type, allocator<_Tp> >::value
-                || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
-             is_trivially_move_constructible<_Tp>::value,
-            void
-        >::type
-        __construct_backward(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __end2)
-        {
-            ptrdiff_t _Np = __end1 - __begin1;
-            __end2 -= _Np;
-            if (_Np > 0)
-                _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
-        }
-
 private:
 
     _LIBCPP_INLINE_VISIBILITY
     static pointer __allocate(allocator_type& __a, size_type __n,
         const_void_pointer __hint, true_type)
         {return __a.allocate(__n, __hint);}
     _LIBCPP_INLINE_VISIBILITY
     static pointer __allocate(allocator_type& __a, size_type __n,

 {
 #ifndef _LIBCPP_CXX03_LANG
     typedef typename _Traits::template rebind_alloc<_Tp>        type;
 #else
     typedef typename _Traits::template rebind_alloc<_Tp>::other type;
 #endif
 };
 
+template <class _Alloc, class _Ptr>
+_LIBCPP_INLINE_VISIBILITY
+inline void
+__construct_forward(_Alloc& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2, false_type)
+{
+    using _Alloc_traits = allocator_traits<_Alloc>;
+    for (; __begin1 != __end1; ++__begin1, ++__begin2)
+        _Alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__begin2), _VSTD::move_if_noexcept(*__begin1));
+}
+
+template <class _Alloc, class _Ptr>
+_LIBCPP_INLINE_VISIBILITY
+inline void
+__construct_forward(_Alloc&, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2, true_type)
+{
+    typedef typename iterator_traits<_Ptr>::value_type _Tp;
+    ptrdiff_t _Np = __end1 - __begin1;
+    if (_Np > 0)
+    {
+        _VSTD::memcpy(_VSTD::__to_raw_pointer(__begin2), _VSTD::__to_raw_pointer(__begin1), _Np * sizeof(_Tp));
+        __begin2 += _Np;
+    }
+}
+
+template <class _Alloc, class _Iter, class _Ptr, class _CopyViaMemcpy>
+_LIBCPP_INLINE_VISIBILITY
+inline void
+__construct_range_forward(_Alloc& __a, _Iter __begin1, _Iter __end1, _Ptr& __begin2, _CopyViaMemcpy)
+{
+    using _Alloc_traits = allocator_traits<_Alloc>;
+    for (; __begin1 != __end1; ++__begin1, (void)++__begin2)
+        _Alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__begin2), *__begin1);
+}
+
+template <class _Alloc, class _Tp>
+_LIBCPP_INLINE_VISIBILITY
+inline void
+__construct_range_forward(_Alloc&, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2, true_type)
+{
+    typedef typename remove_const<_Tp>::type _Vp;
+    ptrdiff_t _Np = __end1 - __begin1;
+    if (_Np > 0)
+    {
+        _VSTD::memcpy(const_cast<_Vp*>(__begin2), __begin1, _Np * sizeof(_Tp));
+        __begin2 += _Np;
+    }
+}
+
+template <class _Alloc, class _Ptr>
+_LIBCPP_INLINE_VISIBILITY
+inline void
+__construct_backward(_Alloc& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __end2, false_type)
+{
+    using _Alloc_traits = allocator_traits<_Alloc>;
+    while (__end1 != __begin1)
+    {
+        _Alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__end2-1), _VSTD::move_if_noexcept(*--__end1));
+        --__end2;
+    }
+}
+
+template <class _Alloc, class _Ptr>
+_LIBCPP_INLINE_VISIBILITY
+inline void
+__construct_backward(_Alloc&, _Ptr __begin1, _Ptr __end1, _Ptr& __end2, true_type)
+{
+    typedef typename iterator_traits<_Ptr>::value_type _Tp;
+    ptrdiff_t _Np = __end1 - __begin1;
+    if (_Np > 0)
+    {
+        __end2 -= _Np;
+        _VSTD::memcpy(_VSTD::__to_raw_pointer(__end2), _VSTD::__to_raw_pointer(__begin1), _Np * sizeof(_Tp));
+    }
+}
+
 // allocator
 
 template <class _Tp>
 class _LIBCPP_TEMPLATE_VIS allocator
 {
 public:
     typedef size_t            size_type;
     typedef ptrdiff_t         difference_type;

include/vector

 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <bool>
 class __vector_base_common
 {
 protected:
     _LIBCPP_INLINE_VISIBILITY __vector_base_common() {}
     _LIBCPP_NORETURN void __throw_length_error() const;
     _LIBCPP_NORETURN void __throw_out_of_range() const;
 };
 
 template <bool __b>
 void
 __vector_base_common<__b>::__throw_length_error() const
 {
     _VSTD::__throw_length_error("vector");
 }
 
 template <bool __b>
 void
 __vector_base_common<__b>::__throw_out_of_range() const
 {
     _VSTD::__throw_out_of_range("vector");
 }
 
 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __vector_base_common<true>)
 
 template <class _Tp, class _Allocator>
 class __vector_base
     : protected __vector_base_common<true>
 {
 public:
     typedef _Allocator                               allocator_type;
     typedef allocator_traits<allocator_type>         __alloc_traits;
     typedef typename __alloc_traits::size_type       size_type;

 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY __vector_base(allocator_type&& __a) _NOEXCEPT;
 #endif
     ~__vector_base();
 
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
     _LIBCPP_INLINE_VISIBILITY
     size_type capacity() const _NOEXCEPT
         {return static_cast<size_type>(__end_cap() - __begin_);}
 
     _LIBCPP_INLINE_VISIBILITY
     void __destruct_at_end(pointer __new_last) _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY
     void __copy_assign_alloc(const __vector_base& __c)
         {__copy_assign_alloc(__c, integral_constant<bool,
                       __alloc_traits::propagate_on_container_copy_assignment::value>());}

 {
     if (__begin_ != nullptr)
     {
         clear();
         __alloc_traits::deallocate(__alloc(), __begin_, capacity());
     }
 }
 
+template<class _Tp, class _Allocator>
+struct __vector_copy_via_memcpy : integral_constant<bool,
+    (is_same<_Allocator, allocator<_Tp> >::value || !__has_construct<_Allocator, _Tp*, _Tp>::value) &&
+    is_trivially_move_constructible<_Tp>::value
+> {};
+
 template <class _Tp, class _Allocator /* = allocator<_Tp> */>
 class _LIBCPP_TEMPLATE_VIS vector
     : private __vector_base<_Tp, _Allocator>
 {
 private:
     typedef __vector_base<_Tp, _Allocator>           __base;
     typedef allocator<_Tp>                           __default_allocator_type;
+
 public:
     typedef vector                                   __self;
     typedef _Tp                                      value_type;
     typedef _Allocator                               allocator_type;
     typedef typename __base::__alloc_traits          __alloc_traits;
     typedef typename __base::reference               reference;
     typedef typename __base::const_reference         const_reference;
     typedef typename __base::size_type               size_type;

 vector(_InputIterator, _InputIterator, _Alloc)
   -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
 #endif
 
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
 {
+    typedef typename __vector_copy_via_memcpy<_Tp, _Allocator>::type __copy_via_memcpy;
     __annotate_delete();
-    __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
+    _VSTD::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_, __copy_via_memcpy());
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
     __v.__first_ = __v.__begin_;
     __annotate_new(size());
     __invalidate_all_iterators();
 }
 
 template <class _Tp, class _Allocator>
 typename vector<_Tp, _Allocator>::pointer
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
 {
+    typedef typename __vector_copy_via_memcpy<_Tp, _Allocator>::type __copy_via_memcpy;
     __annotate_delete();
     pointer __r = __v.__begin_;
-    __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
-    __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
+    _VSTD::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_, __copy_via_memcpy());
+    _VSTD::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_, __copy_via_memcpy());
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
     __v.__first_ = __v.__begin_;
     __annotate_new(size());
     __invalidate_all_iterators();
     return __r;
 }

 template <class _ForwardIterator>
 typename enable_if
 <
     __is_forward_iterator<_ForwardIterator>::value,
     void
 >::type
 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
 {
+    typedef typename __vector_copy_via_memcpy<_Tp, _Allocator>::type __copy_via_memcpy;
     allocator_type& __a = this->__alloc();
     __RAII_IncreaseAnnotator __annotator(*this, __n);
-    __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_);
+    _VSTD::__construct_range_forward(__a, __first, __last, this->__end_, __copy_via_memcpy());
     __annotator.__done();
 }
 
 //  Default constructs __n objects starting at __end_
 //  throws if construction throws
 //  Postcondition:  size() == size() + __n
 //  Exception safety: strong.
 template <class _Tp, class _Allocator>

test/libcxx/containers/sequences/vector/specialized_allocator_traits.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.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03
+
+// <vector>
+
+// Test that vector does not use non-standard members of std::allocator_traits.
+// Specializing std::allocator_traits is arguably non-conforming, but libc++'s
+// support for specialized std::allocator_traits is a feature, not a bug.
+// Breaking (and subsequently deleting) this unit test should be done as a
+// conscious decision.
+
+#include <vector>
+
+template <class T>
+class A1
+{
+public:
+    using value_type = T;
+
+    A1() = default;
+
+    template <class U>
+    A1(const A1<U>&) {}
+
+    T *allocate(std::size_t n)
+    {
+        return (T *)std::malloc(n * sizeof (T));
+    }
+
+    void deallocate(T* p, std::size_t)
+    {
+        std::free(p);
+    }
+};
+
+template<class T>
+struct std::allocator_traits<A1<T>> {
+    using allocator_type = A1<T>;
+    using value_type = T;
+    using pointer = T*;
+    using const_pointer = const T*;
+    using void_pointer = void*;
+    using const_void_pointer = const void*;
+    using difference_type = std::ptrdiff_t;
+    using size_type = std::size_t;
+    using propagate_on_container_copy_assignment = std::true_type;
+    using propagate_on_container_move_assignment = std::true_type;
+    using propagate_on_container_swap = std::true_type;
+    using is_always_equal = std::true_type;
+
+    template<class U> using rebind_alloc = A1<U>;
+    template<class U> using rebind_traits = std::allocator_traits<A1<U>>;
+
+    static T *allocate(A1<T>& a, size_t n) {
+        return a.allocate(n);
+    }
+
+    static void deallocate(A1<T>& a, T *p, size_t n) {
+        return a.deallocate(p, n);
+    }
+
+    template<class U, class... Args>
+    static void construct(A1<T>&, U *p, Args&&... args) {
+        ::new ((void*)p) U(std::forward<Args>(args)...);
+    }
+
+    template<class U>
+    static void destroy(A1<T>&, U *p) {
+        p->~U();
+    }
+
+    static A1<T> select_on_container_copy_construction(const A1<T>& a) {
+        return a.select_on_container_copy_construction();
+    }
+
+    static size_type max_size(const A1<T>&) {
+        return size_t(-1);
+    }
+};
+
+int main()
+{
+    std::vector<int, A1<int>> v = {1, 2, 3};
+    v.resize(10);
+    v.insert(v.begin() + 4, 4);
+    assert(v[0] == 1);
+    assert(v[1] == 2);
+    assert(v[2] == 3);
+    assert(v[3] == 0);
+    assert(v[4] == 4);
+    assert(v[5] == 0);
+}