libstdc++
stl_pair.h
Go to the documentation of this file.
00001 // Pair implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2017 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996,1997
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_pair.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{utility}
00054  */
00055 
00056 #ifndef _STL_PAIR_H
00057 #define _STL_PAIR_H 1
00058 
00059 #include <bits/move.h> // for std::move / std::forward, and std::swap
00060 
00061 #if __cplusplus >= 201103L
00062 #include <type_traits> // for std::__decay_and_strip too
00063 #endif
00064 
00065 namespace std _GLIBCXX_VISIBILITY(default)
00066 {
00067 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00068 
00069   /**
00070    *  @addtogroup utilities
00071    *  @{
00072    */
00073 
00074 #if __cplusplus >= 201103L
00075   /// piecewise_construct_t
00076   struct piecewise_construct_t { explicit piecewise_construct_t() = default; };
00077 
00078   /// piecewise_construct
00079   _GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct =
00080     piecewise_construct_t();
00081 
00082   // Forward declarations.
00083   template<typename...>
00084     class tuple;
00085 
00086   template<std::size_t...>
00087     struct _Index_tuple;
00088 
00089   // Concept utility functions, reused in conditionally-explicit
00090   // constructors.
00091   // See PR 70437, don't look at is_constructible or
00092   // is_convertible if the types are the same to
00093   // avoid querying those properties for incomplete types.
00094   template <bool, typename _T1, typename _T2>
00095     struct _PCC
00096     {
00097       template <typename _U1, typename _U2>
00098       static constexpr bool _ConstructiblePair()
00099       {
00100         return __and_<is_constructible<_T1, const _U1&>,
00101                       is_constructible<_T2, const _U2&>>::value;
00102       }
00103 
00104       template <typename _U1, typename _U2>
00105       static constexpr bool _ImplicitlyConvertiblePair()
00106       {
00107         return __and_<is_convertible<const _U1&, _T1>,
00108                       is_convertible<const _U2&, _T2>>::value;
00109       }
00110 
00111       template <typename _U1, typename _U2>
00112       static constexpr bool _MoveConstructiblePair()
00113       {
00114         return __and_<is_constructible<_T1, _U1&&>,
00115                       is_constructible<_T2, _U2&&>>::value;
00116       }
00117 
00118       template <typename _U1, typename _U2>
00119       static constexpr bool _ImplicitlyMoveConvertiblePair()
00120       {
00121         return __and_<is_convertible<_U1&&, _T1>,
00122                       is_convertible<_U2&&, _T2>>::value;
00123       }
00124 
00125       template <bool __implicit, typename _U1, typename _U2>
00126       static constexpr bool _CopyMovePair()
00127       {
00128         using __do_converts = __and_<is_convertible<const _U1&, _T1>,
00129                                   is_convertible<_U2&&, _T2>>;
00130         using __converts = typename conditional<__implicit,
00131                                        __do_converts,
00132                                        __not_<__do_converts>>::type;
00133         return __and_<is_constructible<_T1, const _U1&>,
00134                       is_constructible<_T2, _U2&&>,
00135                       __converts
00136                       >::value;
00137       }
00138 
00139       template <bool __implicit, typename _U1, typename _U2>
00140       static constexpr bool _MoveCopyPair()
00141       {
00142         using __do_converts = __and_<is_convertible<_U1&&, _T1>,
00143                                   is_convertible<const _U2&, _T2>>;
00144         using __converts = typename conditional<__implicit,
00145                                        __do_converts,
00146                                        __not_<__do_converts>>::type;
00147         return __and_<is_constructible<_T1, _U1&&>,
00148                       is_constructible<_T2, const _U2&&>,
00149                       __converts
00150                       >::value;
00151       }
00152   };
00153 
00154   template <typename _T1, typename _T2>
00155     struct _PCC<false, _T1, _T2>
00156     {
00157       template <typename _U1, typename _U2>
00158       static constexpr bool _ConstructiblePair()
00159       {
00160         return false;
00161       }
00162 
00163       template <typename _U1, typename _U2>
00164       static constexpr bool _ImplicitlyConvertiblePair()
00165       {
00166         return false;
00167       }
00168 
00169       template <typename _U1, typename _U2>
00170       static constexpr bool _MoveConstructiblePair()
00171       {
00172         return false;
00173       }
00174 
00175       template <typename _U1, typename _U2>
00176       static constexpr bool _ImplicitlyMoveConvertiblePair()
00177       {
00178         return false;
00179       }
00180   };
00181 
00182   // PR libstdc++/79141, a utility type for preventing
00183   // initialization of an argument of a disabled assignment
00184   // operator from a pair of empty braces.
00185   struct __nonesuch_no_braces : std::__nonesuch {
00186     explicit __nonesuch_no_braces(const __nonesuch&) = delete;
00187   };
00188 
00189 #endif
00190 
00191  /**
00192    *  @brief Struct holding two objects of arbitrary type.
00193    *
00194    *  @tparam _T1  Type of first object.
00195    *  @tparam _T2  Type of second object.
00196    */
00197   template<typename _T1, typename _T2>
00198     struct pair
00199     {
00200       typedef _T1 first_type;    /// @c first_type is the first bound type
00201       typedef _T2 second_type;   /// @c second_type is the second bound type
00202 
00203       _T1 first;                 /// @c first is a copy of the first object
00204       _T2 second;                /// @c second is a copy of the second object
00205 
00206       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00207       // 265.  std::pair::pair() effects overly restrictive
00208       /** The default constructor creates @c first and @c second using their
00209        *  respective default constructors.  */
00210 #if __cplusplus >= 201103L
00211       template <typename _U1 = _T1,
00212                 typename _U2 = _T2,
00213                 typename enable_if<__and_<
00214                                      __is_implicitly_default_constructible<_U1>,
00215                                      __is_implicitly_default_constructible<_U2>>
00216                                    ::value, bool>::type = true>
00217 #endif
00218       _GLIBCXX_CONSTEXPR pair()
00219       : first(), second() { }
00220 
00221 #if __cplusplus >= 201103L
00222       template <typename _U1 = _T1,
00223                 typename _U2 = _T2,
00224                 typename enable_if<__and_<
00225                        is_default_constructible<_U1>,
00226                        is_default_constructible<_U2>,
00227                        __not_<
00228                          __and_<__is_implicitly_default_constructible<_U1>,
00229                                 __is_implicitly_default_constructible<_U2>>>>
00230                                    ::value, bool>::type = false>
00231       explicit constexpr pair()
00232       : first(), second() { }
00233 #endif
00234 
00235       /** Two objects may be passed to a @c pair constructor to be copied.  */
00236 #if __cplusplus < 201103L
00237       pair(const _T1& __a, const _T2& __b)
00238       : first(__a), second(__b) { }
00239 #else
00240       // Shortcut for constraining the templates that don't take pairs.
00241       using _PCCP = _PCC<true, _T1, _T2>;
00242 
00243       template<typename _U1 = _T1, typename _U2=_T2, typename
00244                enable_if<_PCCP::template
00245                            _ConstructiblePair<_U1, _U2>()
00246                          && _PCCP::template
00247                            _ImplicitlyConvertiblePair<_U1, _U2>(),
00248                          bool>::type=true>
00249       constexpr pair(const _T1& __a, const _T2& __b)
00250       : first(__a), second(__b) { }
00251 
00252        template<typename _U1 = _T1, typename _U2=_T2, typename
00253                 enable_if<_PCCP::template
00254                             _ConstructiblePair<_U1, _U2>()
00255                           && !_PCCP::template
00256                             _ImplicitlyConvertiblePair<_U1, _U2>(),
00257                          bool>::type=false>
00258       explicit constexpr pair(const _T1& __a, const _T2& __b)
00259       : first(__a), second(__b) { }
00260 #endif
00261 
00262       /** There is also a templated copy ctor for the @c pair class itself.  */
00263 #if __cplusplus < 201103L
00264       template<typename _U1, typename _U2>
00265         pair(const pair<_U1, _U2>& __p)
00266         : first(__p.first), second(__p.second) { }
00267 #else
00268       // Shortcut for constraining the templates that take pairs.
00269       template <typename _U1, typename _U2>
00270         using _PCCFP = _PCC<!is_same<_T1, _U1>::value
00271                             || !is_same<_T2, _U2>::value,
00272                             _T1, _T2>;
00273 
00274       template<typename _U1, typename _U2, typename
00275                enable_if<_PCCFP<_U1, _U2>::template
00276                            _ConstructiblePair<_U1, _U2>()
00277                          && _PCCFP<_U1, _U2>::template
00278                            _ImplicitlyConvertiblePair<_U1, _U2>(),
00279                           bool>::type=true>
00280         constexpr pair(const pair<_U1, _U2>& __p)
00281         : first(__p.first), second(__p.second) { }
00282 
00283       template<typename _U1, typename _U2, typename
00284                enable_if<_PCCFP<_U1, _U2>::template
00285                            _ConstructiblePair<_U1, _U2>()
00286                          && !_PCCFP<_U1, _U2>::template
00287                            _ImplicitlyConvertiblePair<_U1, _U2>(),
00288                          bool>::type=false>
00289         explicit constexpr pair(const pair<_U1, _U2>& __p)
00290         : first(__p.first), second(__p.second) { }
00291 
00292       constexpr pair(const pair&) = default;
00293       constexpr pair(pair&&) = default;
00294 
00295       // DR 811.
00296       template<typename _U1, typename
00297                enable_if<_PCCP::template
00298                            _MoveCopyPair<true, _U1, _T2>(),
00299                          bool>::type=true>
00300        constexpr pair(_U1&& __x, const _T2& __y)
00301        : first(std::forward<_U1>(__x)), second(__y) { }
00302 
00303       template<typename _U1, typename
00304                enable_if<_PCCP::template
00305                            _MoveCopyPair<false, _U1, _T2>(),
00306                          bool>::type=false>
00307        explicit constexpr pair(_U1&& __x, const _T2& __y)
00308        : first(std::forward<_U1>(__x)), second(__y) { }
00309 
00310       template<typename _U2, typename
00311                enable_if<_PCCP::template
00312                            _CopyMovePair<true, _T1, _U2>(),
00313                          bool>::type=true>
00314        constexpr pair(const _T1& __x, _U2&& __y)
00315        : first(__x), second(std::forward<_U2>(__y)) { }
00316 
00317       template<typename _U2, typename
00318                enable_if<_PCCP::template
00319                            _CopyMovePair<false, _T1, _U2>(),
00320                          bool>::type=false>
00321        explicit pair(const _T1& __x, _U2&& __y)
00322        : first(__x), second(std::forward<_U2>(__y)) { }
00323 
00324       template<typename _U1, typename _U2, typename
00325                enable_if<_PCCP::template
00326                            _MoveConstructiblePair<_U1, _U2>()
00327                           && _PCCP::template
00328                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00329                          bool>::type=true>
00330         constexpr pair(_U1&& __x, _U2&& __y)
00331         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
00332 
00333       template<typename _U1, typename _U2, typename
00334                enable_if<_PCCP::template
00335                            _MoveConstructiblePair<_U1, _U2>()
00336                           && !_PCCP::template
00337                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00338                          bool>::type=false>
00339         explicit constexpr pair(_U1&& __x, _U2&& __y)
00340         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
00341 
00342 
00343       template<typename _U1, typename _U2, typename
00344                enable_if<_PCCFP<_U1, _U2>::template
00345                            _MoveConstructiblePair<_U1, _U2>()
00346                           && _PCCFP<_U1, _U2>::template
00347                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00348                          bool>::type=true>
00349         constexpr pair(pair<_U1, _U2>&& __p)
00350         : first(std::forward<_U1>(__p.first)),
00351           second(std::forward<_U2>(__p.second)) { }
00352 
00353       template<typename _U1, typename _U2, typename
00354                enable_if<_PCCFP<_U1, _U2>::template
00355                            _MoveConstructiblePair<_U1, _U2>()
00356                           && !_PCCFP<_U1, _U2>::template
00357                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00358                          bool>::type=false>
00359         explicit constexpr pair(pair<_U1, _U2>&& __p)
00360         : first(std::forward<_U1>(__p.first)),
00361           second(std::forward<_U2>(__p.second)) { }
00362 
00363       template<typename... _Args1, typename... _Args2>
00364         pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
00365 
00366       pair&
00367       operator=(typename conditional<
00368                 __and_<is_copy_assignable<_T1>,
00369                        is_copy_assignable<_T2>>::value,
00370                 const pair&, const __nonesuch_no_braces&>::type __p)
00371       {
00372         first = __p.first;
00373         second = __p.second;
00374         return *this;
00375       }
00376 
00377       pair&
00378       operator=(typename conditional<
00379                 __not_<__and_<is_copy_assignable<_T1>,
00380                               is_copy_assignable<_T2>>>::value,
00381                 const pair&, const __nonesuch_no_braces&>::type __p) = delete;
00382 
00383       pair&
00384       operator=(typename conditional<
00385                 __and_<is_move_assignable<_T1>,
00386                        is_move_assignable<_T2>>::value,
00387                 pair&&, __nonesuch_no_braces&&>::type __p)
00388       noexcept(__and_<is_nothrow_move_assignable<_T1>,
00389                       is_nothrow_move_assignable<_T2>>::value)
00390       {
00391         first = std::forward<first_type>(__p.first);
00392         second = std::forward<second_type>(__p.second);
00393         return *this;
00394       }
00395 
00396       template<typename _U1, typename _U2>
00397       typename enable_if<__and_<is_assignable<_T1&, const _U1&>,
00398                                 is_assignable<_T2&, const _U2&>>::value,
00399                          pair&>::type
00400         operator=(const pair<_U1, _U2>& __p)
00401         {
00402           first = __p.first;
00403           second = __p.second;
00404           return *this;
00405         }
00406 
00407       template<typename _U1, typename _U2>
00408       typename enable_if<__and_<is_assignable<_T1&, _U1&&>,
00409                                 is_assignable<_T2&, _U2&&>>::value,
00410                          pair&>::type
00411         operator=(pair<_U1, _U2>&& __p)
00412         {
00413           first = std::forward<_U1>(__p.first);
00414           second = std::forward<_U2>(__p.second);
00415           return *this;
00416         }
00417 
00418       void
00419       swap(pair& __p)
00420       noexcept(__and_<__is_nothrow_swappable<_T1>,
00421                       __is_nothrow_swappable<_T2>>::value)
00422       {
00423         using std::swap;
00424         swap(first, __p.first);
00425         swap(second, __p.second);
00426       }
00427 
00428     private:
00429       template<typename... _Args1, std::size_t... _Indexes1,
00430                typename... _Args2, std::size_t... _Indexes2>
00431         pair(tuple<_Args1...>&, tuple<_Args2...>&,
00432              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
00433 #endif
00434     };
00435 
00436 #if __cpp_deduction_guides >= 201606
00437   template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>;
00438 #endif
00439 
00440   /// Two pairs of the same type are equal iff their members are equal.
00441   template<typename _T1, typename _T2>
00442     inline _GLIBCXX_CONSTEXPR bool
00443     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00444     { return __x.first == __y.first && __x.second == __y.second; }
00445 
00446   /// <http://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
00447   template<typename _T1, typename _T2>
00448     inline _GLIBCXX_CONSTEXPR bool
00449     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00450     { return __x.first < __y.first
00451              || (!(__y.first < __x.first) && __x.second < __y.second); }
00452 
00453   /// Uses @c operator== to find the result.
00454   template<typename _T1, typename _T2>
00455     inline _GLIBCXX_CONSTEXPR bool
00456     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00457     { return !(__x == __y); }
00458 
00459   /// Uses @c operator< to find the result.
00460   template<typename _T1, typename _T2>
00461     inline _GLIBCXX_CONSTEXPR bool
00462     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00463     { return __y < __x; }
00464 
00465   /// Uses @c operator< to find the result.
00466   template<typename _T1, typename _T2>
00467     inline _GLIBCXX_CONSTEXPR bool
00468     operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00469     { return !(__y < __x); }
00470 
00471   /// Uses @c operator< to find the result.
00472   template<typename _T1, typename _T2>
00473     inline _GLIBCXX_CONSTEXPR bool
00474     operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00475     { return !(__x < __y); }
00476 
00477 #if __cplusplus >= 201103L
00478   /// See std::pair::swap().
00479   // Note:  no std::swap overloads in C++03 mode, this has performance
00480   //        implications, see, eg, libstdc++/38466.
00481   template<typename _T1, typename _T2>
00482     inline
00483 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
00484     // Constrained free swap overload, see p0185r1
00485     typename enable_if<__and_<__is_swappable<_T1>,
00486                               __is_swappable<_T2>>::value>::type
00487 #else
00488     void
00489 #endif
00490     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
00491     noexcept(noexcept(__x.swap(__y)))
00492     { __x.swap(__y); }
00493 
00494 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
00495   template<typename _T1, typename _T2>
00496     typename enable_if<!__and_<__is_swappable<_T1>,
00497                                __is_swappable<_T2>>::value>::type
00498     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
00499 #endif
00500 #endif // __cplusplus >= 201103L
00501 
00502   /**
00503    *  @brief A convenience wrapper for creating a pair from two objects.
00504    *  @param  __x  The first object.
00505    *  @param  __y  The second object.
00506    *  @return   A newly-constructed pair<> object of the appropriate type.
00507    *
00508    *  The standard requires that the objects be passed by reference-to-const,
00509    *  but LWG issue #181 says they should be passed by const value.  We follow
00510    *  the LWG by default.
00511    */
00512   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00513   // 181.  make_pair() unintended behavior
00514 #if __cplusplus >= 201103L
00515   // NB: DR 706.
00516   template<typename _T1, typename _T2>
00517     constexpr pair<typename __decay_and_strip<_T1>::__type,
00518                    typename __decay_and_strip<_T2>::__type>
00519     make_pair(_T1&& __x, _T2&& __y)
00520     {
00521       typedef typename __decay_and_strip<_T1>::__type __ds_type1;
00522       typedef typename __decay_and_strip<_T2>::__type __ds_type2;
00523       typedef pair<__ds_type1, __ds_type2>            __pair_type;
00524       return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
00525     }
00526 #else
00527   template<typename _T1, typename _T2>
00528     inline pair<_T1, _T2>
00529     make_pair(_T1 __x, _T2 __y)
00530     { return pair<_T1, _T2>(__x, __y); }
00531 #endif
00532 
00533   /// @}
00534 
00535 _GLIBCXX_END_NAMESPACE_VERSION
00536 } // namespace std
00537 
00538 #endif /* _STL_PAIR_H */