import of libc++ 6.0.0

1 files changed, 290 insertions, 144 deletions

diff --git a/lib/libcxx/include/algorithm b/lib/libcxx/include/algorithm
index 7a6db7abd26..35c6129ea50 100644
--- a/lib/libcxx/include/algorithm
+++ b/lib/libcxx/include/algorithm
@@ -35,6 +35,9 @@ template <class InputIterator, class Function>
     Function
     for_each(InputIterator first, InputIterator last, Function f);
 
+template<class InputIterator, class Size, class Function>
+    InputIterator for_each_n(InputIterator first, Size n, Function f); // C++17
+
 template <class InputIterator, class T>
     InputIterator
     find(InputIterator first, InputIterator last, const T& value);
@@ -89,7 +92,7 @@ template <class InputIterator1, class InputIterator2>
 
 template <class InputIterator1, class InputIterator2>
     pair<InputIterator1, InputIterator2>
-    mismatch(InputIterator1 first1, InputIterator1 last1, 
+    mismatch(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2); // **C++14**
 
 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
@@ -109,7 +112,7 @@ template <class InputIterator1, class InputIterator2>
 
 template <class InputIterator1, class InputIterator2>
     bool
-    equal(InputIterator1 first1, InputIterator1 last1, 
+    equal(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2); // **C++14**
 
 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
@@ -281,12 +284,18 @@ template <class ForwardIterator, class OutputIterator>
 
 template <class RandomAccessIterator>
     void
-    random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14
+    random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
 
 template <class RandomAccessIterator, class RandomNumberGenerator>
     void
     random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
-                   RandomNumberGenerator& rand);  // deprecated in C++14
+                   RandomNumberGenerator& rand);  // deprecated in C++14, removed in C++17
+
+template<class PopulationIterator, class SampleIterator,
+         class Distance, class UniformRandomBitGenerator>
+    SampleIterator sample(PopulationIterator first, PopulationIterator last,
+                          SampleIterator out, Distance n,
+                          UniformRandomBitGenerator&& g); // C++17
 
 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
     void shuffle(RandomAccessIterator first, RandomAccessIterator last,
@@ -638,18 +647,20 @@ template <class BidirectionalIterator, class Compare>
 #if defined(__IBMCPP__)
 #include "support/ibm/support.h"
 #endif
-#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__)
-#include "support/win32/support.h"
+#if defined(_LIBCPP_COMPILER_MSVC)
+#include <intrin.h>
 #endif
 
-#include <__undef_min_max>
-
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // I'd like to replace these with _VSTD::equal_to<void>, but can't because:
@@ -688,7 +699,7 @@ struct __equal_to<_T1, const _T1>
 template <class _T1, class _T2 = _T1>
 struct __less
 {
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
     bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
 
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
@@ -723,15 +734,15 @@ struct __less<_T1, const _T1>
 };
 
 template <class _Predicate>
-class __negate
+class __invert // invert the sense of a comparison
 {
 private:
     _Predicate __p_;
 public:
-    _LIBCPP_INLINE_VISIBILITY __negate() {}
+    _LIBCPP_INLINE_VISIBILITY __invert() {}
 
     _LIBCPP_INLINE_VISIBILITY
-    explicit __negate(_Predicate __p) : __p_(__p) {}
+    explicit __invert(_Predicate __p) : __p_(__p) {}
 
     template <class _T1>
     _LIBCPP_INLINE_VISIBILITY
@@ -739,7 +750,7 @@ public:
 
     template <class _T1, class _T2>
     _LIBCPP_INLINE_VISIBILITY
-    bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
+    bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
 };
 
 #ifdef _LIBCPP_DEBUG
@@ -749,65 +760,160 @@ struct __debug_less
 {
     _Compare __comp_;
     __debug_less(_Compare& __c) : __comp_(__c) {}
+
     template <class _Tp, class _Up>
     bool operator()(const _Tp& __x, const _Up& __y)
     {
         bool __r = __comp_(__x, __y);
         if (__r)
-            _LIBCPP_ASSERT(!__comp_(__y, __x), "Comparator does not induce a strict weak ordering");
+            __do_compare_assert(0, __y, __x);
         return __r;
     }
+
+    template <class _LHS, class _RHS>
+    inline _LIBCPP_INLINE_VISIBILITY
+    decltype((void)_VSTD::declval<_Compare&>()(
+        _VSTD::declval<_LHS const&>(), _VSTD::declval<_RHS const&>()))
+    __do_compare_assert(int, _LHS const& __l, _RHS const& __r) {
+        _LIBCPP_ASSERT(!__comp_(__l, __r),
+            "Comparator does not induce a strict weak ordering");
+    }
+
+    template <class _LHS, class _RHS>
+    inline _LIBCPP_INLINE_VISIBILITY
+    void __do_compare_assert(long, _LHS const&, _RHS const&) {}
 };
 
 #endif  // _LIBCPP_DEBUG
 
 // Precondition:  __x != 0
 inline _LIBCPP_INLINE_VISIBILITY
-unsigned
-__ctz(unsigned __x)
-{
+unsigned __ctz(unsigned __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
     return static_cast<unsigned>(__builtin_ctz(__x));
+#else
+  static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
+  static_assert(sizeof(unsigned long) == 4, "");
+  unsigned long where;
+  // Search from LSB to MSB for first set bit.
+  // Returns zero if no set bit is found.
+  if (_BitScanForward(&where, __x))
+    return where;
+  return 32;
+#endif
 }
 
 inline _LIBCPP_INLINE_VISIBILITY
-unsigned long
-__ctz(unsigned long __x)
-{
+unsigned long __ctz(unsigned long __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
     return static_cast<unsigned long>(__builtin_ctzl(__x));
+#else
+    static_assert(sizeof(unsigned long) == sizeof(unsigned), "");
+    return __ctz(static_cast<unsigned>(__x));
+#endif
 }
 
 inline _LIBCPP_INLINE_VISIBILITY
-unsigned long long
-__ctz(unsigned long long __x)
-{
+unsigned long long __ctz(unsigned long long __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
     return static_cast<unsigned long long>(__builtin_ctzll(__x));
+#else
+    unsigned long where;
+// Search from LSB to MSB for first set bit.
+// Returns zero if no set bit is found.
+#if defined(_LIBCPP_HAS_BITSCAN64)
+    (defined(_M_AMD64) || defined(__x86_64__))
+  if (_BitScanForward64(&where, __x))
+    return static_cast<int>(where);
+#else
+  // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls.
+  // Scan the Low Word.
+  if (_BitScanForward(&where, static_cast<unsigned long>(__x)))
+    return where;
+  // Scan the High Word.
+  if (_BitScanForward(&where, static_cast<unsigned long>(__x >> 32)))
+    return where + 32; // Create a bit offset from the LSB.
+#endif
+  return 64;
+#endif // _LIBCPP_COMPILER_MSVC
 }
 
 // Precondition:  __x != 0
 inline _LIBCPP_INLINE_VISIBILITY
-unsigned
-__clz(unsigned __x)
-{
+unsigned __clz(unsigned __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
     return static_cast<unsigned>(__builtin_clz(__x));
+#else
+  static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
+  static_assert(sizeof(unsigned long) == 4, "");
+  unsigned long where;
+  // Search from LSB to MSB for first set bit.
+  // Returns zero if no set bit is found.
+  if (_BitScanReverse(&where, __x))
+    return 31 - where;
+  return 32; // Undefined Behavior.
+#endif
 }
 
 inline _LIBCPP_INLINE_VISIBILITY
-unsigned long
-__clz(unsigned long __x)
-{
+unsigned long __clz(unsigned long __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
     return static_cast<unsigned long>(__builtin_clzl (__x));
+#else
+    static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
+    return __clz(static_cast<unsigned>(__x));
+#endif
 }
 
 inline _LIBCPP_INLINE_VISIBILITY
-unsigned long long
-__clz(unsigned long long __x)
-{
+unsigned long long __clz(unsigned long long __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
     return static_cast<unsigned long long>(__builtin_clzll(__x));
+#else
+  unsigned long where;
+// BitScanReverse scans from MSB to LSB for first set bit.
+// Returns 0 if no set bit is found.
+#if defined(_LIBCPP_HAS_BITSCAN64)
+  if (_BitScanReverse64(&where, __x))
+    return static_cast<int>(63 - where);
+#else
+  // Scan the high 32 bits.
+  if (_BitScanReverse(&where, static_cast<unsigned long>(__x >> 32)))
+    return 63 - (where + 32); // Create a bit offset from the MSB.
+  // Scan the low 32 bits.
+  if (_BitScanReverse(&where, static_cast<unsigned long>(__x)))
+    return 63 - where;
+#endif
+  return 64; // Undefined Behavior.
+#endif // _LIBCPP_COMPILER_MSVC
+}
+
+inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
+  return __builtin_popcount  (__x);
+#else
+  static_assert(sizeof(unsigned) == 4, "");
+  return __popcnt(__x);
+#endif
 }
 
-inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned           __x) {return __builtin_popcount  (__x);}
-inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned      long __x) {return __builtin_popcountl (__x);}
-inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}
+inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
+  return __builtin_popcountl (__x);
+#else
+  static_assert(sizeof(unsigned long) == 4, "");
+  return __popcnt(__x);
+#endif
+}
+
+inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {
+#ifndef _LIBCPP_COMPILER_MSVC
+  return __builtin_popcountll(__x);
+#else
+  static_assert(sizeof(unsigned long long) == 8, "");
+  return __popcnt64(__x);
+#endif
+}
 
 // all_of
 
@@ -857,9 +963,29 @@ for_each(_InputIterator __first, _InputIterator __last, _Function __f)
 {
     for (; __first != __last; ++__first)
         __f(*__first);
-    return _LIBCPP_EXPLICIT_MOVE(__f);  // explicitly moved for (emulated) C++03
+    return __f;
 }
 
+#if _LIBCPP_STD_VER > 14
+// for_each_n
+
+template <class _InputIterator, class _Size, class _Function>
+inline _LIBCPP_INLINE_VISIBILITY
+_InputIterator
+for_each_n(_InputIterator __first, _Size __orig_n, _Function __f)
+{
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
+    while (__n > 0)
+    {
+         __f(*__first);
+         ++__first;
+         --__n;
+    }
+    return __first;
+}
+#endif
+
 // find
 
 template <class _InputIterator, class _Tp>
@@ -1215,7 +1341,7 @@ equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first
 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
-__equal(_InputIterator1 __first1, _InputIterator1 __last1, 
+__equal(_InputIterator1 __first1, _InputIterator1 __last1,
         _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
         input_iterator_tag, input_iterator_tag )
 {
@@ -1228,8 +1354,8 @@ __equal(_InputIterator1 __first1, _InputIterator1 __last1,
 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
-__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, 
-        _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, 
+__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+        _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
       random_access_iterator_tag, random_access_iterator_tag )
 {
     if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
@@ -1242,11 +1368,11 @@ __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
-equal(_InputIterator1 __first1, _InputIterator1 __last1, 
+equal(_InputIterator1 __first1, _InputIterator1 __last1,
       _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
 {
     return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
-       (__first1, __last1, __first2, __last2, __pred, 
+       (__first1, __last1, __first2, __last2, __pred,
         typename iterator_traits<_InputIterator1>::iterator_category(),
         typename iterator_traits<_InputIterator2>::iterator_category());
 }
@@ -1254,7 +1380,7 @@ equal(_InputIterator1 __first1, _InputIterator1 __last1,
 template <class _InputIterator1, class _InputIterator2>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
-equal(_InputIterator1 __first1, _InputIterator1 __last1, 
+equal(_InputIterator1 __first1, _InputIterator1 __last1,
       _InputIterator2 __first2, _InputIterator2 __last2)
 {
     typedef typename iterator_traits<_InputIterator1>::value_type __v1;
@@ -1328,7 +1454,7 @@ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
 bool
 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-                 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 
+                 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
                  _BinaryPredicate __pred,
                  forward_iterator_tag, forward_iterator_tag )
 {
@@ -1379,7 +1505,7 @@ __next_iter:;
 template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 bool
 __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
-               _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, 
+               _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
                _BinaryPredicate __pred,
                random_access_iterator_tag, random_access_iterator_tag )
 {
@@ -1458,7 +1584,7 @@ __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 }
 
 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 
+_LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_RandomAccessIterator1, _RandomAccessIterator1>
 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
          _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
@@ -1474,9 +1600,9 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
     if (__len1 < __len2)
         return make_pair(__last1, __last1);
     const _RandomAccessIterator1 __s = __last1 - (__len2 - 1);  // Start of pattern match can't go beyond here
+
     while (true)
     {
-#if !_LIBCPP_UNROLL_LOOPS
         while (true)
         {
             if (__first1 == __s)
@@ -1485,40 +1611,9 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
                 break;
             ++__first1;
         }
-#else  // !_LIBCPP_UNROLL_LOOPS
-        for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
-        {
-            if (__pred(*__first1, *__first2))
-                goto __phase2;
-            if (__pred(*++__first1, *__first2))
-                goto __phase2;
-            if (__pred(*++__first1, *__first2))
-                goto __phase2;
-            if (__pred(*++__first1, *__first2))
-                goto __phase2;
-            ++__first1;
-        }
-        switch (__s - __first1)
-        {
-        case 3:
-            if (__pred(*__first1, *__first2))
-                break;
-            ++__first1;
-        case 2:
-            if (__pred(*__first1, *__first2))
-                break;
-            ++__first1;
-        case 1:
-            if (__pred(*__first1, *__first2))
-                break;
-        case 0:
-            return make_pair(__last1, __last1);
-        }
-    __phase2:
-#endif  // !_LIBCPP_UNROLL_LOOPS
+
         _RandomAccessIterator1 __m1 = __first1;
         _RandomAccessIterator2 __m2 = __first2;
-#if !_LIBCPP_UNROLL_LOOPS
          while (true)
          {
              if (++__m2 == __last2)
@@ -1530,43 +1625,6 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
                  break;
              }
          }
-#else  // !_LIBCPP_UNROLL_LOOPS
-        ++__m2;
-        ++__m1;
-        for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
-        {
-            if (!__pred(*__m1, *__m2))
-                goto __continue;
-            if (!__pred(*++__m1, *++__m2))
-                goto __continue;
-            if (!__pred(*++__m1, *++__m2))
-                goto __continue;
-            if (!__pred(*++__m1, *++__m2))
-                goto __continue;
-            ++__m1;
-            ++__m2;
-        }
-        switch (__last2 - __m2)
-        {
-        case 3:
-            if (!__pred(*__m1, *__m2))
-                break;
-            ++__m1;
-            ++__m2;
-        case 2:
-            if (!__pred(*__m1, *__m2))
-                break;
-            ++__m1;
-            ++__m2;
-        case 1:
-            if (!__pred(*__m1, *__m2))
-                break;
-        case 0:
-            return make_pair(__first1, __first1 + __len2);
-        }
-    __continue:
-        ++__first1;
-#endif  // !_LIBCPP_UNROLL_LOOPS
     }
 }
 
@@ -1729,6 +1787,20 @@ __unwrap_iter(__wrap_iter<_Tp*> __i)
     return __i.base();
 }
 
+#else
+
+template <class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY
+typename enable_if
+<
+    is_trivially_copy_assignable<_Tp>::value,
+    __wrap_iter<_Tp*>
+>::type
+__unwrap_iter(__wrap_iter<_Tp*> __i)
+{
+    return __i;
+}
+
 #endif  // _LIBCPP_DEBUG_LEVEL < 2
 
 template <class _InputIterator, class _OutputIterator>
@@ -1802,7 +1874,9 @@ _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
-    return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+    return _VSTD::__copy_backward(__unwrap_iter(__first),
+                                  __unwrap_iter(__last),
+                                  __unwrap_iter(__result));
 }
 
 // copy_if
@@ -2417,7 +2491,7 @@ __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIt
 template<typename _Integral>
 inline _LIBCPP_INLINE_VISIBILITY
 _Integral
-__gcd(_Integral __x, _Integral __y)
+__algo_gcd(_Integral __x, _Integral __y)
 {
     do
     {
@@ -2442,7 +2516,7 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran
         _VSTD::swap_ranges(__first, __middle, __middle);
         return __middle;
     }
-    const difference_type __g = _VSTD::__gcd(__m1, __m2);
+    const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
     {
         value_type __t(_VSTD::move(*--__p));
@@ -2580,7 +2654,7 @@ min(const _Tp& __a, const _Tp& __b)
     return _VSTD::min(__a, __b, __less<_Tp>());
 }
 
-#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+#ifndef _LIBCPP_CXX03_LANG
 
 template<class _Tp, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
@@ -2598,7 +2672,7 @@ min(initializer_list<_Tp> __t)
     return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
 }
 
-#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+#endif  // _LIBCPP_CXX03_LANG
 
 // max_element
 
@@ -2645,7 +2719,7 @@ max(const _Tp& __a, const _Tp& __b)
     return _VSTD::max(__a, __b, __less<_Tp>());
 }
 
-#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+#ifndef _LIBCPP_CXX03_LANG
 
 template<class _Tp, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
@@ -2663,7 +2737,7 @@ max(initializer_list<_Tp> __t)
     return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
 }
 
-#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+#endif  // _LIBCPP_CXX03_LANG
 
 #if _LIBCPP_STD_VER > 14
 // clamp
@@ -2764,7 +2838,7 @@ minmax(const _Tp& __a, const _Tp& __b)
     return _VSTD::minmax(__a, __b, __less<_Tp>());
 }
 
-#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+#ifndef _LIBCPP_CXX03_LANG
 
 template<class _Tp, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
@@ -2785,7 +2859,7 @@ minmax(initializer_list<_Tp> __t, _Compare __comp)
             __result.second = *__first;
         ++__first;
     }
-    
+
     while (__first != __last)
     {
         _Tp __prev = *__first++;
@@ -2797,7 +2871,7 @@ minmax(initializer_list<_Tp> __t, _Compare __comp)
             if ( __comp(__prev, __result.first))    __result.first  = __prev;
             if (!__comp(*__first, __result.second)) __result.second = *__first;
             }
-                
+
         __first++;
     }
     return __result;
@@ -2811,7 +2885,7 @@ minmax(initializer_list<_Tp> __t)
     return _VSTD::minmax(__t, __less<_Tp>());
 }
 
-#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
+#endif  // _LIBCPP_CXX03_LANG
 
 // random_shuffle
 
@@ -2836,11 +2910,11 @@ struct __log2_imp<0, _Rp>
     static const size_t value = _Rp + 1;
 };
 
-template <class _UI, _UI _Xp>
+template <class _UIntType, _UIntType _Xp>
 struct __log2
 {
     static const size_t value = __log2_imp<_Xp,
-                                         sizeof(_UI) * __CHAR_BIT__ - 1>::value;
+                                         sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;
 };
 
 template<class _Engine, class _UIntType>
@@ -2869,7 +2943,7 @@ private:
     _Engine_result_type __mask0_;
     _Engine_result_type __mask1_;
 
-#ifdef _LIBCPP_HAS_NO_CONSTEXPR
+#ifdef _LIBCPP_CXX03_LANG
     static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
                                           + _Working_result_type(1);
 #else
@@ -2939,6 +3013,7 @@ template<class _Engine, class _UIntType>
 _UIntType
 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
 {
+    const size_t _WRt = numeric_limits<result_type>::digits;
     result_type _Sp = 0;
     for (size_t __k = 0; __k < __n0_; ++__k)
     {
@@ -2947,7 +3022,7 @@ __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
         {
             __u = __e_() - _Engine::min();
         } while (__u >= __y0_);
-        if (__w0_ < _WDt)
+        if (__w0_ < _WRt)
             _Sp <<= __w0_;
         else
             _Sp = 0;
@@ -2960,7 +3035,7 @@ __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
         {
             __u = __e_() - _Engine::min();
         } while (__u >= __y1_);
-        if (__w0_ < _WDt - 1)
+        if (__w0_ < _WRt - 1)
             _Sp <<= __w0_ + 1;
         else
             _Sp = 0;
@@ -3058,6 +3133,8 @@ uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p
     return static_cast<result_type>(__u + __p.a());
 }
 
+#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
+  || defined(_LIBCPP_BUILDING_LIBRARY)
 class _LIBCPP_TYPE_VIS __rs_default;
 
 _LIBCPP_FUNC_VIS __rs_default __rs_get();
@@ -3110,7 +3187,7 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
 template <class _RandomAccessIterator, class _RandomNumberGenerator>
 void
 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
                _RandomNumberGenerator&& __rand)
 #else
                _RandomNumberGenerator& __rand)
@@ -3127,10 +3204,83 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
         }
     }
 }
+#endif
+
+template <class _PopulationIterator, class _SampleIterator, class _Distance,
+          class _UniformRandomNumberGenerator>
+_LIBCPP_INLINE_VISIBILITY
+_SampleIterator __sample(_PopulationIterator __first,
+                         _PopulationIterator __last, _SampleIterator __output_iter,
+                         _Distance __n,
+                         _UniformRandomNumberGenerator & __g,
+                         input_iterator_tag) {
+
+  _Distance __k = 0;
+  for (; __first != __last && __k < __n; ++__first, (void)++__k)
+    __output_iter[__k] = *__first;
+  _Distance __sz = __k;
+  for (; __first != __last; ++__first, (void)++__k) {
+    _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
+    if (__r < __sz)
+      __output_iter[__r] = *__first;
+  }
+  return __output_iter + _VSTD::min(__n, __k);
+}
+
+template <class _PopulationIterator, class _SampleIterator, class _Distance,
+          class _UniformRandomNumberGenerator>
+_LIBCPP_INLINE_VISIBILITY
+_SampleIterator __sample(_PopulationIterator __first,
+                         _PopulationIterator __last, _SampleIterator __output_iter,
+                         _Distance __n,
+                         _UniformRandomNumberGenerator& __g,
+                         forward_iterator_tag) {
+  _Distance __unsampled_sz = _VSTD::distance(__first, __last);
+  for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
+    _Distance __r =
+        _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
+    if (__r < __n) {
+      *__output_iter++ = *__first;
+      --__n;
+    }
+  }
+  return __output_iter;
+}
+
+template <class _PopulationIterator, class _SampleIterator, class _Distance,
+          class _UniformRandomNumberGenerator>
+_LIBCPP_INLINE_VISIBILITY
+_SampleIterator __sample(_PopulationIterator __first,
+                         _PopulationIterator __last, _SampleIterator __output_iter,
+                         _Distance __n, _UniformRandomNumberGenerator& __g) {
+  typedef typename iterator_traits<_PopulationIterator>::iterator_category
+        _PopCategory;
+  typedef typename iterator_traits<_PopulationIterator>::difference_type
+        _Difference;
+  static_assert(__is_forward_iterator<_PopulationIterator>::value ||
+                __is_random_access_iterator<_SampleIterator>::value,
+                "SampleIterator must meet the requirements of RandomAccessIterator");
+  typedef typename common_type<_Distance, _Difference>::type _CommonType;
+  _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
+  return _VSTD::__sample(
+      __first, __last, __output_iter, _CommonType(__n),
+      __g, _PopCategory());
+}
+
+#if _LIBCPP_STD_VER > 14
+template <class _PopulationIterator, class _SampleIterator, class _Distance,
+          class _UniformRandomNumberGenerator>
+inline _LIBCPP_INLINE_VISIBILITY
+_SampleIterator sample(_PopulationIterator __first,
+                       _PopulationIterator __last, _SampleIterator __output_iter,
+                       _Distance __n, _UniformRandomNumberGenerator&& __g) {
+    return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
+}
+#endif // _LIBCPP_STD_VER > 14
 
 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
     void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
                  _UniformRandomNumberGenerator&& __g)
 #else
                  _UniformRandomNumberGenerator& __g)
@@ -4085,10 +4235,6 @@ sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
     _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
 }
 
-#ifdef _LIBCPP_MSVC
-#pragma warning( push )
-#pragma warning( disable: 4231)
-#endif // _LIBCPP_MSVC
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
@@ -4122,9 +4268,6 @@ _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
 
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))
-#ifdef _LIBCPP_MSVC
-#pragma warning( pop )
-#endif  // _LIBCPP_MSVC
 
 // lower_bound
 
@@ -4423,9 +4566,9 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
             ::new(__p) value_type(_VSTD::move(*__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
-        __half_inplace_merge(_Rv(__p), _Rv(__buff), 
+        __half_inplace_merge(_Rv(__p), _Rv(__buff),
                              _RBi(__middle), _RBi(__first),
-                             _RBi(__last), __negate<_Compare>(__comp));
+                             _RBi(__last), __invert<_Compare>(__comp));
     }
 }
 
@@ -4871,7 +5014,8 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 
 template <class _Compare, class _RandomAccessIterator>
 void
-__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
+            _Compare __comp,
             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
             _RandomAccessIterator __start)
 {
@@ -5403,9 +5547,9 @@ __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
         }
         else
         {
-            *__result = *__first1;
             if (!__comp(*__first1, *__first2))
                 ++__first2;
+            *__result = *__first1;
             ++__first1;
         }
     }
@@ -5756,4 +5900,6 @@ prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif  // _LIBCPP_ALGORITHM