libstdc++-v3/include/bits/stl_pair.h

   1 // Pair implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2021 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996,1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/stl_pair.h
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{utility}
  54  */
  55
  56 #ifndef _STL_PAIR_H
  57 #define _STL_PAIR_H 1
  58
  59 #if __cplusplus >= 201103L
  60 # include <type_traits>    // for std::__decay_and_strip
  61 # include <bits/move.h>    // for std::move / std::forward, and std::swap
  62 # include <bits/utility.h> // for std::tuple_element, std::tuple_size
  63 #endif
  64 #if __cplusplus >= 202002L
  65 # include <compare>
  66 # define __cpp_lib_constexpr_utility 201811L
  67 #endif
  68
  69 namespace std _GLIBCXX_VISIBILITY(default)
  70 {
  71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  72
  73   /**
  74    *  @addtogroup utilities
  75    *  @{
  76    */
  77
  78 #if __cplusplus >= 201103L
  79   /// Tag type for piecewise construction of std::pair objects.
  80   struct piecewise_construct_t { explicit piecewise_construct_t() = default; };
  81
  82   /// Tag for piecewise construction of std::pair objects.
  83   _GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct =
  84     piecewise_construct_t();
  85
  86   /// @cond undocumented
  87
  88   // Forward declarations.
  89   template<typename...>
  90     class tuple;
  91
  92   template<size_t...>
  93     struct _Index_tuple;
  94
  95 #if ! __cpp_lib_concepts
  96   // Concept utility functions, reused in conditionally-explicit
  97   // constructors.
  98   // See PR 70437, don't look at is_constructible or
  99   // is_convertible if the types are the same to
 100   // avoid querying those properties for incomplete types.
 101   template <bool, typename _T1, typename _T2>
 102     struct _PCC
 103     {
 104       template <typename _U1, typename _U2>
 105       static constexpr bool _ConstructiblePair()
 106       {
 107         return __and_<is_constructible<_T1, const _U1&>,
 108                       is_constructible<_T2, const _U2&>>::value;
 109       }
 110
 111       template <typename _U1, typename _U2>
 112       static constexpr bool _ImplicitlyConvertiblePair()
 113       {
 114         return __and_<is_convertible<const _U1&, _T1>,
 115                       is_convertible<const _U2&, _T2>>::value;
 116       }
 117
 118       template <typename _U1, typename _U2>
 119       static constexpr bool _MoveConstructiblePair()
 120       {
 121         return __and_<is_constructible<_T1, _U1&&>,
 122                       is_constructible<_T2, _U2&&>>::value;
 123       }
 124
 125       template <typename _U1, typename _U2>
 126       static constexpr bool _ImplicitlyMoveConvertiblePair()
 127       {
 128         return __and_<is_convertible<_U1&&, _T1>,
 129                       is_convertible<_U2&&, _T2>>::value;
 130       }
 131
 132
 133       template <bool __implicit, typename _U1, typename _U2>
 134       static constexpr bool _DeprConsPair()
 135       {
 136         using __do_converts = __and_<is_convertible<_U1&&, _T1>,
 137                                      is_convertible<_U2&&, _T2>>;
 138         using __converts = typename conditional<__implicit,
 139                                                 __do_converts,
 140                                                 __not_<__do_converts>>::type;
 141         return __and_<is_constructible<_T1, _U1&&>,
 142                       is_constructible<_T2, _U2&&>,
 143                       __converts
 144                      >::value;
 145       }
 146     };
 147
 148   template <typename _T1, typename _T2>
 149     struct _PCC<false, _T1, _T2>
 150     {
 151       template <typename _U1, typename _U2>
 152       static constexpr bool _ConstructiblePair()
 153       {
 154         return false;
 155       }
 156
 157       template <typename _U1, typename _U2>
 158       static constexpr bool _ImplicitlyConvertiblePair()
 159       {
 160         return false;
 161       }
 162
 163       template <typename _U1, typename _U2>
 164       static constexpr bool _MoveConstructiblePair()
 165       {
 166         return false;
 167       }
 168
 169       template <typename _U1, typename _U2>
 170       static constexpr bool _ImplicitlyMoveConvertiblePair()
 171       {
 172         return false;
 173       }
 174     };
 175 #endif // lib concepts
 176 #endif // C++11
 177
 178   template<typename _U1, typename _U2> class __pair_base
 179   {
 180 #if __cplusplus >= 201103L && ! __cpp_lib_concepts
 181     template<typename _T1, typename _T2> friend struct pair;
 182     __pair_base() = default;
 183     ~__pair_base() = default;
 184     __pair_base(const __pair_base&) = default;
 185     __pair_base& operator=(const __pair_base&) = delete;
 186 #endif // C++11
 187   };
 188
 189   /// @endcond
 190
 191  /**
 192    *  @brief Struct holding two objects of arbitrary type.
 193    *
 194    *  @tparam _T1  Type of first object.
 195    *  @tparam _T2  Type of second object.
 196    *
 197    *  <https://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
 198    */
 199   template<typename _T1, typename _T2>
 200     struct pair
 201     : public __pair_base<_T1, _T2>
 202     {
 203       typedef _T1 first_type;    ///< The type of the `first` member
 204       typedef _T2 second_type;   ///< The type of the `second` member
 205
 206       _T1 first;                 ///< The first member
 207       _T2 second;                ///< The second member
 208
 209 #if __cplusplus >= 201103L
 210       constexpr pair(const pair&) = default;    ///< Copy constructor
 211       constexpr pair(pair&&) = default;         ///< Move constructor
 212
 213       template<typename... _Args1, typename... _Args2>
 214         _GLIBCXX20_CONSTEXPR
 215         pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
 216
 217       /// Swap the first members and then the second members.
 218       _GLIBCXX20_CONSTEXPR void
 219       swap(pair& __p)
 220       noexcept(__and_<__is_nothrow_swappable<_T1>,
 221                       __is_nothrow_swappable<_T2>>::value)
 222       {
 223         using std::swap;
 224         swap(first, __p.first);
 225         swap(second, __p.second);
 226       }
 227
 228     private:
 229       template<typename... _Args1, size_t... _Indexes1,
 230                typename... _Args2, size_t... _Indexes2>
 231         _GLIBCXX20_CONSTEXPR
 232         pair(tuple<_Args1...>&, tuple<_Args2...>&,
 233              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
 234     public:
 235
 236 #if __cpp_lib_concepts
 237       // C++20 implementation using concepts, explicit(bool), fully constexpr.
 238
 239       /// Default constructor
 240       constexpr
 241       explicit(__not_<__and_<__is_implicitly_default_constructible<_T1>,
 242                              __is_implicitly_default_constructible<_T2>>>())
 243       pair()
 244       requires is_default_constructible_v<_T1>
 245                && is_default_constructible_v<_T2>
 246       : first(), second()
 247       { }
 248
 249     private:
 250
 251       /// @cond undocumented
 252       template<typename _U1, typename _U2>
 253         static constexpr bool
 254         _S_constructible()
 255         {
 256           if constexpr (is_constructible_v<_T1, _U1>)
 257             return is_constructible_v<_T2, _U2>;
 258           return false;
 259         }
 260
 261       template<typename _U1, typename _U2>
 262         static constexpr bool
 263         _S_nothrow_constructible()
 264         {
 265           if constexpr (is_nothrow_constructible_v<_T1, _U1>)
 266             return is_nothrow_constructible_v<_T2, _U2>;
 267           return false;
 268         }
 269
 270       template<typename _U1, typename _U2>
 271         static constexpr bool
 272         _S_convertible()
 273         {
 274           if constexpr (is_convertible_v<_U1, _T1>)
 275             return is_convertible_v<_U2, _T2>;
 276           return false;
 277         }
 278       /// @endcond
 279
 280     public:
 281
 282       /// Constructor accepting lvalues of `first_type` and `second_type`
 283       constexpr explicit(!_S_convertible<const _T1&, const _T2&>())
 284       pair(const _T1& __x, const _T2& __y)
 285       noexcept(_S_nothrow_constructible<const _T1&, const _T2&>())
 286       requires (_S_constructible<const _T1&, const _T2&>())
 287       : first(__x), second(__y)
 288       { }
 289
 290       /// Constructor accepting two values of arbitrary types
 291       template<typename _U1, typename _U2>
 292         requires (_S_constructible<_U1, _U2>())
 293         constexpr explicit(!_S_convertible<_U1, _U2>())
 294         pair(_U1&& __x, _U2&& __y)
 295         noexcept(_S_nothrow_constructible<_U1, _U2>())
 296         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y))
 297         { }
 298
 299       /// Converting constructor from a `pair<U1, U2>` lvalue
 300       template<typename _U1, typename _U2>
 301         requires (_S_constructible<const _U1&, const _U2&>())
 302         constexpr explicit(!_S_convertible<const _U1&, const _U2&>())
 303         pair(const pair<_U1, _U2>& __p)
 304         noexcept(_S_nothrow_constructible<const _U1&, const _U2&>())
 305         : first(__p.first), second(__p.second)
 306         { }
 307
 308       /// Converting constructor from a `pair<U1, U2>` rvalue
 309       template<typename _U1, typename _U2>
 310         requires (_S_constructible<_U1, _U2>())
 311         constexpr explicit(!_S_convertible<_U1, _U2>())
 312         pair(pair<_U1, _U2>&& __p)
 313         noexcept(_S_nothrow_constructible<_U1, _U2>())
 314         : first(std::forward<_U1>(__p.first)),
 315           second(std::forward<_U2>(__p.second))
 316         { }
 317
 318   private:
 319       /// @cond undocumented
 320       template<typename _U1, typename _U2>
 321         static constexpr bool
 322         _S_assignable()
 323         {
 324           if constexpr (is_assignable_v<_T1&, _U1>)
 325             return is_assignable_v<_T2&, _U2>;
 326           return false;
 327         }
 328
 329       template<typename _U1, typename _U2>
 330         static constexpr bool
 331         _S_nothrow_assignable()
 332         {
 333           if constexpr (is_nothrow_assignable_v<_T1&, _U1>)
 334             return is_nothrow_assignable_v<_T2&, _U2>;
 335           return false;
 336         }
 337       /// @endcond
 338
 339   public:
 340
 341       pair& operator=(const pair&) = delete;
 342
 343       /// Copy assignment operator
 344       constexpr pair&
 345       operator=(const pair& __p)
 346       noexcept(_S_nothrow_assignable<const _T1&, const _T2&>())
 347       requires (_S_assignable<const _T1&, const _T2&>())
 348       {
 349         first = __p.first;
 350         second = __p.second;
 351         return *this;
 352       }
 353
 354       /// Move assignment operator
 355       constexpr pair&
 356       operator=(pair&& __p)
 357       noexcept(_S_nothrow_assignable<_T1, _T2>())
 358       requires (_S_assignable<_T1, _T2>())
 359       {
 360         first = std::forward<first_type>(__p.first);
 361         second = std::forward<second_type>(__p.second);
 362         return *this;
 363       }
 364
 365       /// Converting assignment from a `pair<U1, U2>` lvalue
 366       template<typename _U1, typename _U2>
 367         constexpr pair&
 368         operator=(const pair<_U1, _U2>& __p)
 369         noexcept(_S_nothrow_assignable<const _U1&, const _U2&>())
 370         requires (_S_assignable<const _U1&, const _U2&>())
 371         {
 372           first = __p.first;
 373           second = __p.second;
 374           return *this;
 375         }
 376
 377       /// Converting assignment from a `pair<U1, U2>` rvalue
 378       template<typename _U1, typename _U2>
 379         constexpr pair&
 380         operator=(pair<_U1, _U2>&& __p)
 381         noexcept(_S_nothrow_assignable<_U1, _U2>())
 382         requires (_S_assignable<_U1, _U2>())
 383         {
 384           first = std::forward<_U1>(__p.first);
 385           second = std::forward<_U2>(__p.second);
 386           return *this;
 387         }
 388 #else
 389       // C++11/14/17 implementation using enable_if, partially constexpr.
 390
 391       /** The default constructor creates @c first and @c second using their
 392        *  respective default constructors.  */
 393       template <typename _U1 = _T1,
 394                 typename _U2 = _T2,
 395                 typename enable_if<__and_<
 396                                      __is_implicitly_default_constructible<_U1>,
 397                                      __is_implicitly_default_constructible<_U2>>
 398                                    ::value, bool>::type = true>
 399       constexpr pair()
 400       : first(), second() { }
 401
 402       template <typename _U1 = _T1,
 403                 typename _U2 = _T2,
 404                 typename enable_if<__and_<
 405                        is_default_constructible<_U1>,
 406                        is_default_constructible<_U2>,
 407                        __not_<
 408                          __and_<__is_implicitly_default_constructible<_U1>,
 409                                 __is_implicitly_default_constructible<_U2>>>>
 410                                    ::value, bool>::type = false>
 411       explicit constexpr pair()
 412       : first(), second() { }
 413
 414       // Shortcut for constraining the templates that don't take pairs.
 415       /// @cond undocumented
 416       using _PCCP = _PCC<true, _T1, _T2>;
 417       /// @endcond
 418
 419       /// Construct from two const lvalues, allowing implicit conversions.
 420       template<typename _U1 = _T1, typename _U2=_T2, typename
 421                enable_if<_PCCP::template
 422                            _ConstructiblePair<_U1, _U2>()
 423                          && _PCCP::template
 424                            _ImplicitlyConvertiblePair<_U1, _U2>(),
 425                          bool>::type=true>
 426       constexpr pair(const _T1& __a, const _T2& __b)
 427       : first(__a), second(__b) { }
 428
 429       /// Construct from two const lvalues, disallowing implicit conversions.
 430        template<typename _U1 = _T1, typename _U2=_T2, typename
 431                 enable_if<_PCCP::template
 432                             _ConstructiblePair<_U1, _U2>()
 433                           && !_PCCP::template
 434                             _ImplicitlyConvertiblePair<_U1, _U2>(),
 435                          bool>::type=false>
 436       explicit constexpr pair(const _T1& __a, const _T2& __b)
 437       : first(__a), second(__b) { }
 438
 439       // Shortcut for constraining the templates that take pairs.
 440       /// @cond undocumented
 441       template <typename _U1, typename _U2>
 442         using _PCCFP = _PCC<!is_same<_T1, _U1>::value
 443                             || !is_same<_T2, _U2>::value,
 444                             _T1, _T2>;
 445       /// @endcond
 446
 447       template<typename _U1, typename _U2, typename
 448                enable_if<_PCCFP<_U1, _U2>::template
 449                            _ConstructiblePair<_U1, _U2>()
 450                          && _PCCFP<_U1, _U2>::template
 451                            _ImplicitlyConvertiblePair<_U1, _U2>(),
 452                           bool>::type=true>
 453         constexpr pair(const pair<_U1, _U2>& __p)
 454         : first(__p.first), second(__p.second) { }
 455
 456       template<typename _U1, typename _U2, typename
 457                enable_if<_PCCFP<_U1, _U2>::template
 458                            _ConstructiblePair<_U1, _U2>()
 459                          && !_PCCFP<_U1, _U2>::template
 460                            _ImplicitlyConvertiblePair<_U1, _U2>(),
 461                          bool>::type=false>
 462         explicit constexpr pair(const pair<_U1, _U2>& __p)
 463         : first(__p.first), second(__p.second) { }
 464
 465 #if _GLIBCXX_USE_DEPRECATED
 466     private:
 467       /// @cond undocumented
 468
 469       // A type which can be constructed from literal zero, but not nullptr
 470       struct __null_ptr_constant
 471       {
 472         __null_ptr_constant(int __null_ptr_constant::*) { }
 473         template<typename _Tp,
 474                  typename = __enable_if_t<is_null_pointer<_Tp>::value>>
 475         __null_ptr_constant(_Tp) = delete;
 476       };
 477
 478       // True if type _Up is one of _Tp& or const _Tp&
 479       template<typename _Up, typename _Tp>
 480         using __is_lvalue_of
 481           = __or_<is_same<_Up, const _Tp&>, is_same<_Up, _Tp&>>;
 482
 483       /// @endcond
 484     public:
 485
 486       // Deprecated extensions to DR 811.
 487       template<typename _U1,
 488                __enable_if_t<!__is_lvalue_of<_U1, _T1>::value
 489                              && _PCCP::template
 490                                _DeprConsPair<true, _U1, nullptr_t>(),
 491                              bool> = true>
 492        _GLIBCXX_DEPRECATED_SUGGEST("nullptr")
 493        constexpr pair(_U1&& __x, __null_ptr_constant)
 494        : first(std::forward<_U1>(__x)), second(nullptr) { }
 495
 496       template<typename _U1,
 497                __enable_if_t<!__is_lvalue_of<_U1, _T1>::value
 498                              && _PCCP::template
 499                                _DeprConsPair<false, _U1, nullptr_t>(),
 500                              bool> = false>
 501        _GLIBCXX_DEPRECATED_SUGGEST("nullptr")
 502        explicit constexpr pair(_U1&& __x, __null_ptr_constant)
 503        : first(std::forward<_U1>(__x)), second(nullptr) { }
 504
 505       template<typename _U2,
 506                __enable_if_t<!__is_lvalue_of<_U2, _T2>::value
 507                              && _PCCP::template
 508                                _DeprConsPair<true, nullptr_t, _U2>(),
 509                              bool> = true>
 510        _GLIBCXX_DEPRECATED_SUGGEST("nullptr")
 511        constexpr pair(__null_ptr_constant, _U2&& __y)
 512        : first(nullptr), second(std::forward<_U2>(__y)) { }
 513
 514       template<typename _U2,
 515                __enable_if_t<!__is_lvalue_of<_U2, _T2>::value
 516                              && _PCCP::template
 517                                _DeprConsPair<false, nullptr_t, _U2>(),
 518                              bool> = false>
 519        _GLIBCXX_DEPRECATED_SUGGEST("nullptr")
 520        explicit pair(__null_ptr_constant, _U2&& __y)
 521        : first(nullptr), second(std::forward<_U2>(__y)) { }
 522 #endif
 523
 524       template<typename _U1, typename _U2, typename
 525                enable_if<_PCCP::template
 526                            _MoveConstructiblePair<_U1, _U2>()
 527                           && _PCCP::template
 528                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 529                          bool>::type=true>
 530         constexpr pair(_U1&& __x, _U2&& __y)
 531         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
 532
 533       template<typename _U1, typename _U2, typename
 534                enable_if<_PCCP::template
 535                            _MoveConstructiblePair<_U1, _U2>()
 536                           && !_PCCP::template
 537                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 538                          bool>::type=false>
 539         explicit constexpr pair(_U1&& __x, _U2&& __y)
 540         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
 541
 542
 543       template<typename _U1, typename _U2, typename
 544                enable_if<_PCCFP<_U1, _U2>::template
 545                            _MoveConstructiblePair<_U1, _U2>()
 546                           && _PCCFP<_U1, _U2>::template
 547                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 548                          bool>::type=true>
 549         constexpr pair(pair<_U1, _U2>&& __p)
 550         : first(std::forward<_U1>(__p.first)),
 551           second(std::forward<_U2>(__p.second)) { }
 552
 553       template<typename _U1, typename _U2, typename
 554                enable_if<_PCCFP<_U1, _U2>::template
 555                            _MoveConstructiblePair<_U1, _U2>()
 556                           && !_PCCFP<_U1, _U2>::template
 557                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 558                          bool>::type=false>
 559         explicit constexpr pair(pair<_U1, _U2>&& __p)
 560         : first(std::forward<_U1>(__p.first)),
 561           second(std::forward<_U2>(__p.second)) { }
 562
 563       pair&
 564       operator=(typename conditional<
 565                 __and_<is_copy_assignable<_T1>,
 566                        is_copy_assignable<_T2>>::value,
 567                 const pair&, const __nonesuch&>::type __p)
 568       {
 569         first = __p.first;
 570         second = __p.second;
 571         return *this;
 572       }
 573
 574       pair&
 575       operator=(typename conditional<
 576                 __and_<is_move_assignable<_T1>,
 577                        is_move_assignable<_T2>>::value,
 578                 pair&&, __nonesuch&&>::type __p)
 579       noexcept(__and_<is_nothrow_move_assignable<_T1>,
 580                       is_nothrow_move_assignable<_T2>>::value)
 581       {
 582         first = std::forward<first_type>(__p.first);
 583         second = std::forward<second_type>(__p.second);
 584         return *this;
 585       }
 586
 587       template<typename _U1, typename _U2>
 588         typename enable_if<__and_<is_assignable<_T1&, const _U1&>,
 589                                   is_assignable<_T2&, const _U2&>>::value,
 590                            pair&>::type
 591         operator=(const pair<_U1, _U2>& __p)
 592         {
 593           first = __p.first;
 594           second = __p.second;
 595           return *this;
 596         }
 597
 598       template<typename _U1, typename _U2>
 599         typename enable_if<__and_<is_assignable<_T1&, _U1&&>,
 600                                   is_assignable<_T2&, _U2&&>>::value,
 601                            pair&>::type
 602         operator=(pair<_U1, _U2>&& __p)
 603         {
 604           first = std::forward<_U1>(__p.first);
 605           second = std::forward<_U2>(__p.second);
 606           return *this;
 607         }
 608 #endif // lib concepts
 609 #else
 610       // C++03 implementation
 611
 612       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 613       // 265.  std::pair::pair() effects overly restrictive
 614       /** The default constructor creates @c first and @c second using their
 615        *  respective default constructors.  */
 616       pair() : first(), second() { }
 617
 618       /// Two objects may be passed to a `pair` constructor to be copied.
 619       pair(const _T1& __a, const _T2& __b)
 620       : first(__a), second(__b) { }
 621
 622       /// Templated constructor to convert from other pairs.
 623       template<typename _U1, typename _U2>
 624         pair(const pair<_U1, _U2>& __p)
 625         : first(__p.first), second(__p.second) { }
 626 #endif // C++11
 627     };
 628
 629   /// @relates pair @{
 630
 631 #if __cpp_deduction_guides >= 201606
 632   template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>;
 633 #endif
 634
 635   /// Two pairs of the same type are equal iff their members are equal.
 636   template<typename _T1, typename _T2>
 637     inline _GLIBCXX_CONSTEXPR bool
 638     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 639     { return __x.first == __y.first && __x.second == __y.second; }
 640
 641 #if __cpp_lib_three_way_comparison && __cpp_lib_concepts
 642   template<typename _T1, typename _T2>
 643     constexpr common_comparison_category_t<__detail::__synth3way_t<_T1>,
 644                                            __detail::__synth3way_t<_T2>>
 645     operator<=>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 646     {
 647       if (auto __c = __detail::__synth3way(__x.first, __y.first); __c != 0)
 648         return __c;
 649       return __detail::__synth3way(__x.second, __y.second);
 650     }
 651 #else
 652   /** Defines a lexicographical order for pairs.
 653    *
 654    * For two pairs of the same type, `P` is ordered before `Q` if
 655    * `P.first` is less than `Q.first`, or if `P.first` and `Q.first`
 656    * are equivalent (neither is less than the other) and `P.second` is less
 657    * than `Q.second`.
 658   */
 659   template<typename _T1, typename _T2>
 660     inline _GLIBCXX_CONSTEXPR bool
 661     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 662     { return __x.first < __y.first
 663              || (!(__y.first < __x.first) && __x.second < __y.second); }
 664
 665   /// Uses @c operator== to find the result.
 666   template<typename _T1, typename _T2>
 667     inline _GLIBCXX_CONSTEXPR bool
 668     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 669     { return !(__x == __y); }
 670
 671   /// Uses @c operator< to find the result.
 672   template<typename _T1, typename _T2>
 673     inline _GLIBCXX_CONSTEXPR bool
 674     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 675     { return __y < __x; }
 676
 677   /// Uses @c operator< to find the result.
 678   template<typename _T1, typename _T2>
 679     inline _GLIBCXX_CONSTEXPR bool
 680     operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 681     { return !(__y < __x); }
 682
 683   /// Uses @c operator< to find the result.
 684   template<typename _T1, typename _T2>
 685     inline _GLIBCXX_CONSTEXPR bool
 686     operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 687     { return !(__x < __y); }
 688 #endif // !(three_way_comparison && concepts)
 689
 690 #if __cplusplus >= 201103L
 691   /** Swap overload for pairs. Calls std::pair::swap().
 692    *
 693    * @note This std::swap overload is not declared in C++03 mode,
 694    * which has performance implications, e.g. see https://gcc.gnu.org/PR38466
 695   */
 696   template<typename _T1, typename _T2>
 697     _GLIBCXX20_CONSTEXPR inline
 698 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 699     // Constrained free swap overload, see p0185r1
 700     typename enable_if<__and_<__is_swappable<_T1>,
 701                               __is_swappable<_T2>>::value>::type
 702 #else
 703     void
 704 #endif
 705     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
 706     noexcept(noexcept(__x.swap(__y)))
 707     { __x.swap(__y); }
 708
 709 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 710   template<typename _T1, typename _T2>
 711     typename enable_if<!__and_<__is_swappable<_T1>,
 712                                __is_swappable<_T2>>::value>::type
 713     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
 714 #endif
 715 #endif // __cplusplus >= 201103L
 716
 717   /// @} relates pair
 718
 719   /**
 720    *  @brief A convenience wrapper for creating a pair from two objects.
 721    *  @param  __x  The first object.
 722    *  @param  __y  The second object.
 723    *  @return   A newly-constructed pair<> object of the appropriate type.
 724    *
 725    *  The C++98 standard says the objects are passed by reference-to-const,
 726    *  but C++03 says they are passed by value (this was LWG issue #181).
 727    *
 728    *  Since C++11 they have been passed by forwarding reference and then
 729    *  forwarded to the new members of the pair. To create a pair with a
 730    *  member of reference type, pass a `reference_wrapper` to this function.
 731    */
 732   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 733   // 181.  make_pair() unintended behavior
 734 #if __cplusplus >= 201103L
 735   // NB: DR 706.
 736   template<typename _T1, typename _T2>
 737     constexpr pair<typename __decay_and_strip<_T1>::__type,
 738                    typename __decay_and_strip<_T2>::__type>
 739     make_pair(_T1&& __x, _T2&& __y)
 740     {
 741       typedef typename __decay_and_strip<_T1>::__type __ds_type1;
 742       typedef typename __decay_and_strip<_T2>::__type __ds_type2;
 743       typedef pair<__ds_type1, __ds_type2>            __pair_type;
 744       return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
 745     }
 746 #else
 747   template<typename _T1, typename _T2>
 748     inline pair<_T1, _T2>
 749     make_pair(_T1 __x, _T2 __y)
 750     { return pair<_T1, _T2>(__x, __y); }
 751 #endif
 752
 753   /// @}
 754
 755 #if __cplusplus >= 201103L
 756   // Various functions which give std::pair a tuple-like interface.
 757
 758   template<typename _T1, typename _T2>
 759     struct __is_tuple_like_impl<pair<_T1, _T2>> : true_type
 760     { };
 761
 762   /// Partial specialization for std::pair
 763   template<class _Tp1, class _Tp2>
 764     struct tuple_size<pair<_Tp1, _Tp2>>
 765     : public integral_constant<size_t, 2> { };
 766
 767   /// Partial specialization for std::pair
 768   template<class _Tp1, class _Tp2>
 769     struct tuple_element<0, pair<_Tp1, _Tp2>>
 770     { typedef _Tp1 type; };
 771
 772   /// Partial specialization for std::pair
 773   template<class _Tp1, class _Tp2>
 774     struct tuple_element<1, pair<_Tp1, _Tp2>>
 775     { typedef _Tp2 type; };
 776
 777   /// @cond undocumented
 778   template<size_t _Int>
 779     struct __pair_get;
 780
 781   template<>
 782     struct __pair_get<0>
 783     {
 784       template<typename _Tp1, typename _Tp2>
 785         static constexpr _Tp1&
 786         __get(pair<_Tp1, _Tp2>& __pair) noexcept
 787         { return __pair.first; }
 788
 789       template<typename _Tp1, typename _Tp2>
 790         static constexpr _Tp1&&
 791         __move_get(pair<_Tp1, _Tp2>&& __pair) noexcept
 792         { return std::forward<_Tp1>(__pair.first); }
 793
 794       template<typename _Tp1, typename _Tp2>
 795         static constexpr const _Tp1&
 796         __const_get(const pair<_Tp1, _Tp2>& __pair) noexcept
 797         { return __pair.first; }
 798
 799       template<typename _Tp1, typename _Tp2>
 800         static constexpr const _Tp1&&
 801         __const_move_get(const pair<_Tp1, _Tp2>&& __pair) noexcept
 802         { return std::forward<const _Tp1>(__pair.first); }
 803     };
 804
 805   template<>
 806     struct __pair_get<1>
 807     {
 808       template<typename _Tp1, typename _Tp2>
 809         static constexpr _Tp2&
 810         __get(pair<_Tp1, _Tp2>& __pair) noexcept
 811         { return __pair.second; }
 812
 813       template<typename _Tp1, typename _Tp2>
 814         static constexpr _Tp2&&
 815         __move_get(pair<_Tp1, _Tp2>&& __pair) noexcept
 816         { return std::forward<_Tp2>(__pair.second); }
 817
 818       template<typename _Tp1, typename _Tp2>
 819         static constexpr const _Tp2&
 820         __const_get(const pair<_Tp1, _Tp2>& __pair) noexcept
 821         { return __pair.second; }
 822
 823       template<typename _Tp1, typename _Tp2>
 824         static constexpr const _Tp2&&
 825         __const_move_get(const pair<_Tp1, _Tp2>&& __pair) noexcept
 826         { return std::forward<const _Tp2>(__pair.second); }
 827     };
 828   /// @endcond
 829
 830   /** @{
 831    * std::get overloads for accessing members of std::pair
 832    */
 833
 834   template<size_t _Int, class _Tp1, class _Tp2>
 835     constexpr typename tuple_element<_Int, pair<_Tp1, _Tp2>>::type&
 836     get(pair<_Tp1, _Tp2>& __in) noexcept
 837     { return __pair_get<_Int>::__get(__in); }
 838
 839   template<size_t _Int, class _Tp1, class _Tp2>
 840     constexpr typename tuple_element<_Int, pair<_Tp1, _Tp2>>::type&&
 841     get(pair<_Tp1, _Tp2>&& __in) noexcept
 842     { return __pair_get<_Int>::__move_get(std::move(__in)); }
 843
 844   template<size_t _Int, class _Tp1, class _Tp2>
 845     constexpr const typename tuple_element<_Int, pair<_Tp1, _Tp2>>::type&
 846     get(const pair<_Tp1, _Tp2>& __in) noexcept
 847     { return __pair_get<_Int>::__const_get(__in); }
 848
 849   template<size_t _Int, class _Tp1, class _Tp2>
 850     constexpr const typename tuple_element<_Int, pair<_Tp1, _Tp2>>::type&&
 851     get(const pair<_Tp1, _Tp2>&& __in) noexcept
 852     { return __pair_get<_Int>::__const_move_get(std::move(__in)); }
 853
 854 #if __cplusplus >= 201402L
 855
 856 #define __cpp_lib_tuples_by_type 201304L
 857
 858   template <typename _Tp, typename _Up>
 859     constexpr _Tp&
 860     get(pair<_Tp, _Up>& __p) noexcept
 861     { return __p.first; }
 862
 863   template <typename _Tp, typename _Up>
 864     constexpr const _Tp&
 865     get(const pair<_Tp, _Up>& __p) noexcept
 866     { return __p.first; }
 867
 868   template <typename _Tp, typename _Up>
 869     constexpr _Tp&&
 870     get(pair<_Tp, _Up>&& __p) noexcept
 871     { return std::move(__p.first); }
 872
 873   template <typename _Tp, typename _Up>
 874     constexpr const _Tp&&
 875     get(const pair<_Tp, _Up>&& __p) noexcept
 876     { return std::move(__p.first); }
 877
 878   template <typename _Tp, typename _Up>
 879     constexpr _Tp&
 880     get(pair<_Up, _Tp>& __p) noexcept
 881     { return __p.second; }
 882
 883   template <typename _Tp, typename _Up>
 884     constexpr const _Tp&
 885     get(const pair<_Up, _Tp>& __p) noexcept
 886     { return __p.second; }
 887
 888   template <typename _Tp, typename _Up>
 889     constexpr _Tp&&
 890     get(pair<_Up, _Tp>&& __p) noexcept
 891     { return std::move(__p.second); }
 892
 893   template <typename _Tp, typename _Up>
 894     constexpr const _Tp&&
 895     get(const pair<_Up, _Tp>&& __p) noexcept
 896     { return std::move(__p.second); }
 897
 898 #endif // C++14
 899   /// @}
 900 #endif // C++11
 901
 902 _GLIBCXX_END_NAMESPACE_VERSION
 903 } // namespace std
 904
 905 #endif /* _STL_PAIR_H */