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

   1 // Pair implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2018 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 #include <bits/move.h> // for std::move / std::forward, and std::swap
  60
  61 #if __cplusplus >= 201103L
  62 #include <type_traits> // for std::__decay_and_strip too
  63 #endif
  64
  65 namespace std _GLIBCXX_VISIBILITY(default)
  66 {
  67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  68
  69   /**
  70    *  @addtogroup utilities
  71    *  @{
  72    */
  73
  74 #if __cplusplus >= 201103L
  75   /// piecewise_construct_t
  76   struct piecewise_construct_t { explicit piecewise_construct_t() = default; };
  77
  78   /// piecewise_construct
  79   _GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct =
  80     piecewise_construct_t();
  81
  82   // Forward declarations.
  83   template<typename...>
  84     class tuple;
  85
  86   template<std::size_t...>
  87     struct _Index_tuple;
  88
  89   // Concept utility functions, reused in conditionally-explicit
  90   // constructors.
  91   // See PR 70437, don't look at is_constructible or
  92   // is_convertible if the types are the same to
  93   // avoid querying those properties for incomplete types.
  94   template <bool, typename _T1, typename _T2>
  95     struct _PCC
  96     {
  97       template <typename _U1, typename _U2>
  98       static constexpr bool _ConstructiblePair()
  99       {
 100         return __and_<is_constructible<_T1, const _U1&>,
 101                       is_constructible<_T2, const _U2&>>::value;
 102       }
 103
 104       template <typename _U1, typename _U2>
 105       static constexpr bool _ImplicitlyConvertiblePair()
 106       {
 107         return __and_<is_convertible<const _U1&, _T1>,
 108                       is_convertible<const _U2&, _T2>>::value;
 109       }
 110
 111       template <typename _U1, typename _U2>
 112       static constexpr bool _MoveConstructiblePair()
 113       {
 114         return __and_<is_constructible<_T1, _U1&&>,
 115                       is_constructible<_T2, _U2&&>>::value;
 116       }
 117
 118       template <typename _U1, typename _U2>
 119       static constexpr bool _ImplicitlyMoveConvertiblePair()
 120       {
 121         return __and_<is_convertible<_U1&&, _T1>,
 122                       is_convertible<_U2&&, _T2>>::value;
 123       }
 124
 125       template <bool __implicit, typename _U1, typename _U2>
 126       static constexpr bool _CopyMovePair()
 127       {
 128         using __do_converts = __and_<is_convertible<const _U1&, _T1>,
 129                                   is_convertible<_U2&&, _T2>>;
 130         using __converts = typename conditional<__implicit,
 131                                        __do_converts,
 132                                        __not_<__do_converts>>::type;
 133         return __and_<is_constructible<_T1, const _U1&>,
 134                       is_constructible<_T2, _U2&&>,
 135                       __converts
 136                       >::value;
 137       }
 138
 139       template <bool __implicit, typename _U1, typename _U2>
 140       static constexpr bool _MoveCopyPair()
 141       {
 142         using __do_converts = __and_<is_convertible<_U1&&, _T1>,
 143                                   is_convertible<const _U2&, _T2>>;
 144         using __converts = typename conditional<__implicit,
 145                                        __do_converts,
 146                                        __not_<__do_converts>>::type;
 147         return __and_<is_constructible<_T1, _U1&&>,
 148                       is_constructible<_T2, const _U2&&>,
 149                       __converts
 150                       >::value;
 151       }
 152   };
 153
 154   template <typename _T1, typename _T2>
 155     struct _PCC<false, _T1, _T2>
 156     {
 157       template <typename _U1, typename _U2>
 158       static constexpr bool _ConstructiblePair()
 159       {
 160         return false;
 161       }
 162
 163       template <typename _U1, typename _U2>
 164       static constexpr bool _ImplicitlyConvertiblePair()
 165       {
 166         return false;
 167       }
 168
 169       template <typename _U1, typename _U2>
 170       static constexpr bool _MoveConstructiblePair()
 171       {
 172         return false;
 173       }
 174
 175       template <typename _U1, typename _U2>
 176       static constexpr bool _ImplicitlyMoveConvertiblePair()
 177       {
 178         return false;
 179       }
 180   };
 181
 182   // PR libstdc++/79141, a utility type for preventing
 183   // initialization of an argument of a disabled assignment
 184   // operator from a pair of empty braces.
 185   struct __nonesuch_no_braces : std::__nonesuch {
 186     explicit __nonesuch_no_braces(const __nonesuch&) = delete;
 187   };
 188 #endif // C++11
 189
 190   template<typename _U1, typename _U2> class __pair_base
 191   {
 192 #if __cplusplus >= 201103L
 193     template<typename _T1, typename _T2> friend struct pair;
 194     __pair_base() = default;
 195     ~__pair_base() = default;
 196     __pair_base(const __pair_base&) = default;
 197     __pair_base& operator=(const __pair_base&) = delete;
 198 #endif // C++11
 199   };
 200
 201  /**
 202    *  @brief Struct holding two objects of arbitrary type.
 203    *
 204    *  @tparam _T1  Type of first object.
 205    *  @tparam _T2  Type of second object.
 206    */
 207   template<typename _T1, typename _T2>
 208     struct pair
 209     : private __pair_base<_T1, _T2>
 210     {
 211       typedef _T1 first_type;    /// @c first_type is the first bound type
 212       typedef _T2 second_type;   /// @c second_type is the second bound type
 213
 214       _T1 first;                 /// @c first is a copy of the first object
 215       _T2 second;                /// @c second is a copy of the second object
 216
 217       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 218       // 265.  std::pair::pair() effects overly restrictive
 219       /** The default constructor creates @c first and @c second using their
 220        *  respective default constructors.  */
 221 #if __cplusplus >= 201103L
 222       template <typename _U1 = _T1,
 223                 typename _U2 = _T2,
 224                 typename enable_if<__and_<
 225                                      __is_implicitly_default_constructible<_U1>,
 226                                      __is_implicitly_default_constructible<_U2>>
 227                                    ::value, bool>::type = true>
 228 #endif
 229       _GLIBCXX_CONSTEXPR pair()
 230       : first(), second() { }
 231
 232 #if __cplusplus >= 201103L
 233       template <typename _U1 = _T1,
 234                 typename _U2 = _T2,
 235                 typename enable_if<__and_<
 236                        is_default_constructible<_U1>,
 237                        is_default_constructible<_U2>,
 238                        __not_<
 239                          __and_<__is_implicitly_default_constructible<_U1>,
 240                                 __is_implicitly_default_constructible<_U2>>>>
 241                                    ::value, bool>::type = false>
 242       explicit constexpr pair()
 243       : first(), second() { }
 244 #endif
 245
 246       /** Two objects may be passed to a @c pair constructor to be copied.  */
 247 #if __cplusplus < 201103L
 248       pair(const _T1& __a, const _T2& __b)
 249       : first(__a), second(__b) { }
 250 #else
 251       // Shortcut for constraining the templates that don't take pairs.
 252       using _PCCP = _PCC<true, _T1, _T2>;
 253
 254       template<typename _U1 = _T1, typename _U2=_T2, typename
 255                enable_if<_PCCP::template
 256                            _ConstructiblePair<_U1, _U2>()
 257                          && _PCCP::template
 258                            _ImplicitlyConvertiblePair<_U1, _U2>(),
 259                          bool>::type=true>
 260       constexpr pair(const _T1& __a, const _T2& __b)
 261       : first(__a), second(__b) { }
 262
 263        template<typename _U1 = _T1, typename _U2=_T2, typename
 264                 enable_if<_PCCP::template
 265                             _ConstructiblePair<_U1, _U2>()
 266                           && !_PCCP::template
 267                             _ImplicitlyConvertiblePair<_U1, _U2>(),
 268                          bool>::type=false>
 269       explicit constexpr pair(const _T1& __a, const _T2& __b)
 270       : first(__a), second(__b) { }
 271 #endif
 272
 273       /** There is also a templated copy ctor for the @c pair class itself.  */
 274 #if __cplusplus < 201103L
 275       template<typename _U1, typename _U2>
 276         pair(const pair<_U1, _U2>& __p)
 277         : first(__p.first), second(__p.second) { }
 278 #else
 279       // Shortcut for constraining the templates that take pairs.
 280       template <typename _U1, typename _U2>
 281         using _PCCFP = _PCC<!is_same<_T1, _U1>::value
 282                             || !is_same<_T2, _U2>::value,
 283                             _T1, _T2>;
 284
 285       template<typename _U1, typename _U2, typename
 286                enable_if<_PCCFP<_U1, _U2>::template
 287                            _ConstructiblePair<_U1, _U2>()
 288                          && _PCCFP<_U1, _U2>::template
 289                            _ImplicitlyConvertiblePair<_U1, _U2>(),
 290                           bool>::type=true>
 291         constexpr pair(const pair<_U1, _U2>& __p)
 292         : first(__p.first), second(__p.second) { }
 293
 294       template<typename _U1, typename _U2, typename
 295                enable_if<_PCCFP<_U1, _U2>::template
 296                            _ConstructiblePair<_U1, _U2>()
 297                          && !_PCCFP<_U1, _U2>::template
 298                            _ImplicitlyConvertiblePair<_U1, _U2>(),
 299                          bool>::type=false>
 300         explicit constexpr pair(const pair<_U1, _U2>& __p)
 301         : first(__p.first), second(__p.second) { }
 302
 303       constexpr pair(const pair&) = default;
 304       constexpr pair(pair&&) = default;
 305
 306       // DR 811.
 307       template<typename _U1, typename
 308                enable_if<_PCCP::template
 309                            _MoveCopyPair<true, _U1, _T2>(),
 310                          bool>::type=true>
 311        constexpr pair(_U1&& __x, const _T2& __y)
 312        : first(std::forward<_U1>(__x)), second(__y) { }
 313
 314       template<typename _U1, typename
 315                enable_if<_PCCP::template
 316                            _MoveCopyPair<false, _U1, _T2>(),
 317                          bool>::type=false>
 318        explicit constexpr pair(_U1&& __x, const _T2& __y)
 319        : first(std::forward<_U1>(__x)), second(__y) { }
 320
 321       template<typename _U2, typename
 322                enable_if<_PCCP::template
 323                            _CopyMovePair<true, _T1, _U2>(),
 324                          bool>::type=true>
 325        constexpr pair(const _T1& __x, _U2&& __y)
 326        : first(__x), second(std::forward<_U2>(__y)) { }
 327
 328       template<typename _U2, typename
 329                enable_if<_PCCP::template
 330                            _CopyMovePair<false, _T1, _U2>(),
 331                          bool>::type=false>
 332        explicit pair(const _T1& __x, _U2&& __y)
 333        : first(__x), second(std::forward<_U2>(__y)) { }
 334
 335       template<typename _U1, typename _U2, typename
 336                enable_if<_PCCP::template
 337                            _MoveConstructiblePair<_U1, _U2>()
 338                           && _PCCP::template
 339                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 340                          bool>::type=true>
 341         constexpr pair(_U1&& __x, _U2&& __y)
 342         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
 343
 344       template<typename _U1, typename _U2, typename
 345                enable_if<_PCCP::template
 346                            _MoveConstructiblePair<_U1, _U2>()
 347                           && !_PCCP::template
 348                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 349                          bool>::type=false>
 350         explicit constexpr pair(_U1&& __x, _U2&& __y)
 351         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
 352
 353
 354       template<typename _U1, typename _U2, typename
 355                enable_if<_PCCFP<_U1, _U2>::template
 356                            _MoveConstructiblePair<_U1, _U2>()
 357                           && _PCCFP<_U1, _U2>::template
 358                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 359                          bool>::type=true>
 360         constexpr pair(pair<_U1, _U2>&& __p)
 361         : first(std::forward<_U1>(__p.first)),
 362           second(std::forward<_U2>(__p.second)) { }
 363
 364       template<typename _U1, typename _U2, typename
 365                enable_if<_PCCFP<_U1, _U2>::template
 366                            _MoveConstructiblePair<_U1, _U2>()
 367                           && !_PCCFP<_U1, _U2>::template
 368                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
 369                          bool>::type=false>
 370         explicit constexpr pair(pair<_U1, _U2>&& __p)
 371         : first(std::forward<_U1>(__p.first)),
 372           second(std::forward<_U2>(__p.second)) { }
 373
 374       template<typename... _Args1, typename... _Args2>
 375         pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
 376
 377       pair&
 378       operator=(typename conditional<
 379                 __and_<is_copy_assignable<_T1>,
 380                        is_copy_assignable<_T2>>::value,
 381                 const pair&, const __nonesuch_no_braces&>::type __p)
 382       {
 383         first = __p.first;
 384         second = __p.second;
 385         return *this;
 386       }
 387
 388       pair&
 389       operator=(typename conditional<
 390                 __and_<is_move_assignable<_T1>,
 391                        is_move_assignable<_T2>>::value,
 392                 pair&&, __nonesuch_no_braces&&>::type __p)
 393       noexcept(__and_<is_nothrow_move_assignable<_T1>,
 394                       is_nothrow_move_assignable<_T2>>::value)
 395       {
 396         first = std::forward<first_type>(__p.first);
 397         second = std::forward<second_type>(__p.second);
 398         return *this;
 399       }
 400
 401       template<typename _U1, typename _U2>
 402       typename enable_if<__and_<is_assignable<_T1&, const _U1&>,
 403                                 is_assignable<_T2&, const _U2&>>::value,
 404                          pair&>::type
 405         operator=(const pair<_U1, _U2>& __p)
 406         {
 407           first = __p.first;
 408           second = __p.second;
 409           return *this;
 410         }
 411
 412       template<typename _U1, typename _U2>
 413       typename enable_if<__and_<is_assignable<_T1&, _U1&&>,
 414                                 is_assignable<_T2&, _U2&&>>::value,
 415                          pair&>::type
 416         operator=(pair<_U1, _U2>&& __p)
 417         {
 418           first = std::forward<_U1>(__p.first);
 419           second = std::forward<_U2>(__p.second);
 420           return *this;
 421         }
 422
 423       void
 424       swap(pair& __p)
 425       noexcept(__and_<__is_nothrow_swappable<_T1>,
 426                       __is_nothrow_swappable<_T2>>::value)
 427       {
 428         using std::swap;
 429         swap(first, __p.first);
 430         swap(second, __p.second);
 431       }
 432
 433     private:
 434       template<typename... _Args1, std::size_t... _Indexes1,
 435                typename... _Args2, std::size_t... _Indexes2>
 436         pair(tuple<_Args1...>&, tuple<_Args2...>&,
 437              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
 438 #endif
 439     };
 440
 441 #if __cpp_deduction_guides >= 201606
 442   template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>;
 443 #endif
 444
 445   /// Two pairs of the same type are equal iff their members are equal.
 446   template<typename _T1, typename _T2>
 447     inline _GLIBCXX_CONSTEXPR bool
 448     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 449     { return __x.first == __y.first && __x.second == __y.second; }
 450
 451   /// <http://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
 452   template<typename _T1, typename _T2>
 453     inline _GLIBCXX_CONSTEXPR bool
 454     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 455     { return __x.first < __y.first
 456              || (!(__y.first < __x.first) && __x.second < __y.second); }
 457
 458   /// Uses @c operator== to find the result.
 459   template<typename _T1, typename _T2>
 460     inline _GLIBCXX_CONSTEXPR bool
 461     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 462     { return !(__x == __y); }
 463
 464   /// Uses @c operator< to find the result.
 465   template<typename _T1, typename _T2>
 466     inline _GLIBCXX_CONSTEXPR bool
 467     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 468     { return __y < __x; }
 469
 470   /// Uses @c operator< to find the result.
 471   template<typename _T1, typename _T2>
 472     inline _GLIBCXX_CONSTEXPR bool
 473     operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 474     { return !(__y < __x); }
 475
 476   /// Uses @c operator< to find the result.
 477   template<typename _T1, typename _T2>
 478     inline _GLIBCXX_CONSTEXPR bool
 479     operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 480     { return !(__x < __y); }
 481
 482 #if __cplusplus >= 201103L
 483   /// See std::pair::swap().
 484   // Note:  no std::swap overloads in C++03 mode, this has performance
 485   //        implications, see, eg, libstdc++/38466.
 486   template<typename _T1, typename _T2>
 487     inline
 488 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 489     // Constrained free swap overload, see p0185r1
 490     typename enable_if<__and_<__is_swappable<_T1>,
 491                               __is_swappable<_T2>>::value>::type
 492 #else
 493     void
 494 #endif
 495     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
 496     noexcept(noexcept(__x.swap(__y)))
 497     { __x.swap(__y); }
 498
 499 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 500   template<typename _T1, typename _T2>
 501     typename enable_if<!__and_<__is_swappable<_T1>,
 502                                __is_swappable<_T2>>::value>::type
 503     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
 504 #endif
 505 #endif // __cplusplus >= 201103L
 506
 507   /**
 508    *  @brief A convenience wrapper for creating a pair from two objects.
 509    *  @param  __x  The first object.
 510    *  @param  __y  The second object.
 511    *  @return   A newly-constructed pair<> object of the appropriate type.
 512    *
 513    *  The standard requires that the objects be passed by reference-to-const,
 514    *  but LWG issue #181 says they should be passed by const value.  We follow
 515    *  the LWG by default.
 516    */
 517   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 518   // 181.  make_pair() unintended behavior
 519 #if __cplusplus >= 201103L
 520   // NB: DR 706.
 521   template<typename _T1, typename _T2>
 522     constexpr pair<typename __decay_and_strip<_T1>::__type,
 523                    typename __decay_and_strip<_T2>::__type>
 524     make_pair(_T1&& __x, _T2&& __y)
 525     {
 526       typedef typename __decay_and_strip<_T1>::__type __ds_type1;
 527       typedef typename __decay_and_strip<_T2>::__type __ds_type2;
 528       typedef pair<__ds_type1, __ds_type2>            __pair_type;
 529       return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
 530     }
 531 #else
 532   template<typename _T1, typename _T2>
 533     inline pair<_T1, _T2>
 534     make_pair(_T1 __x, _T2 __y)
 535     { return pair<_T1, _T2>(__x, __y); }
 536 #endif
 537
 538   /// @}
 539
 540 _GLIBCXX_END_NAMESPACE_VERSION
 541 } // namespace std
 542
 543 #endif /* _STL_PAIR_H */