libstdc++
stl_pair.h
Go to the documentation of this file.
00001 // Pair implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2018 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 #endif // C++11
00189 
00190   template<typename _U1, typename _U2> class __pair_base
00191   {
00192 #if __cplusplus >= 201103L
00193     template<typename _T1, typename _T2> friend struct pair;
00194     __pair_base() = default;
00195     ~__pair_base() = default;
00196     __pair_base(const __pair_base&) = default;
00197     __pair_base& operator=(const __pair_base&) = delete;
00198 #endif // C++11
00199   };
00200 
00201  /**
00202    *  @brief Struct holding two objects of arbitrary type.
00203    *
00204    *  @tparam _T1  Type of first object.
00205    *  @tparam _T2  Type of second object.
00206    */
00207   template<typename _T1, typename _T2>
00208     struct pair
00209     : private __pair_base<_T1, _T2>
00210     {
00211       typedef _T1 first_type;    /// @c first_type is the first bound type
00212       typedef _T2 second_type;   /// @c second_type is the second bound type
00213 
00214       _T1 first;                 /// @c first is a copy of the first object
00215       _T2 second;                /// @c second is a copy of the second object
00216 
00217       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00218       // 265.  std::pair::pair() effects overly restrictive
00219       /** The default constructor creates @c first and @c second using their
00220        *  respective default constructors.  */
00221 #if __cplusplus >= 201103L
00222       template <typename _U1 = _T1,
00223                 typename _U2 = _T2,
00224                 typename enable_if<__and_<
00225                                      __is_implicitly_default_constructible<_U1>,
00226                                      __is_implicitly_default_constructible<_U2>>
00227                                    ::value, bool>::type = true>
00228 #endif
00229       _GLIBCXX_CONSTEXPR pair()
00230       : first(), second() { }
00231 
00232 #if __cplusplus >= 201103L
00233       template <typename _U1 = _T1,
00234                 typename _U2 = _T2,
00235                 typename enable_if<__and_<
00236                        is_default_constructible<_U1>,
00237                        is_default_constructible<_U2>,
00238                        __not_<
00239                          __and_<__is_implicitly_default_constructible<_U1>,
00240                                 __is_implicitly_default_constructible<_U2>>>>
00241                                    ::value, bool>::type = false>
00242       explicit constexpr pair()
00243       : first(), second() { }
00244 #endif
00245 
00246       /** Two objects may be passed to a @c pair constructor to be copied.  */
00247 #if __cplusplus < 201103L
00248       pair(const _T1& __a, const _T2& __b)
00249       : first(__a), second(__b) { }
00250 #else
00251       // Shortcut for constraining the templates that don't take pairs.
00252       using _PCCP = _PCC<true, _T1, _T2>;
00253 
00254       template<typename _U1 = _T1, typename _U2=_T2, typename
00255                enable_if<_PCCP::template
00256                            _ConstructiblePair<_U1, _U2>()
00257                          && _PCCP::template
00258                            _ImplicitlyConvertiblePair<_U1, _U2>(),
00259                          bool>::type=true>
00260       constexpr pair(const _T1& __a, const _T2& __b)
00261       : first(__a), second(__b) { }
00262 
00263        template<typename _U1 = _T1, typename _U2=_T2, typename
00264                 enable_if<_PCCP::template
00265                             _ConstructiblePair<_U1, _U2>()
00266                           && !_PCCP::template
00267                             _ImplicitlyConvertiblePair<_U1, _U2>(),
00268                          bool>::type=false>
00269       explicit constexpr pair(const _T1& __a, const _T2& __b)
00270       : first(__a), second(__b) { }
00271 #endif
00272 
00273       /** There is also a templated copy ctor for the @c pair class itself.  */
00274 #if __cplusplus < 201103L
00275       template<typename _U1, typename _U2>
00276         pair(const pair<_U1, _U2>& __p)
00277         : first(__p.first), second(__p.second) { }
00278 #else
00279       // Shortcut for constraining the templates that take pairs.
00280       template <typename _U1, typename _U2>
00281         using _PCCFP = _PCC<!is_same<_T1, _U1>::value
00282                             || !is_same<_T2, _U2>::value,
00283                             _T1, _T2>;
00284 
00285       template<typename _U1, typename _U2, typename
00286                enable_if<_PCCFP<_U1, _U2>::template
00287                            _ConstructiblePair<_U1, _U2>()
00288                          && _PCCFP<_U1, _U2>::template
00289                            _ImplicitlyConvertiblePair<_U1, _U2>(),
00290                           bool>::type=true>
00291         constexpr pair(const pair<_U1, _U2>& __p)
00292         : first(__p.first), second(__p.second) { }
00293 
00294       template<typename _U1, typename _U2, typename
00295                enable_if<_PCCFP<_U1, _U2>::template
00296                            _ConstructiblePair<_U1, _U2>()
00297                          && !_PCCFP<_U1, _U2>::template
00298                            _ImplicitlyConvertiblePair<_U1, _U2>(),
00299                          bool>::type=false>
00300         explicit constexpr pair(const pair<_U1, _U2>& __p)
00301         : first(__p.first), second(__p.second) { }
00302 
00303       constexpr pair(const pair&) = default;
00304       constexpr pair(pair&&) = default;
00305 
00306       // DR 811.
00307       template<typename _U1, typename
00308                enable_if<_PCCP::template
00309                            _MoveCopyPair<true, _U1, _T2>(),
00310                          bool>::type=true>
00311        constexpr pair(_U1&& __x, const _T2& __y)
00312        : first(std::forward<_U1>(__x)), second(__y) { }
00313 
00314       template<typename _U1, typename
00315                enable_if<_PCCP::template
00316                            _MoveCopyPair<false, _U1, _T2>(),
00317                          bool>::type=false>
00318        explicit constexpr pair(_U1&& __x, const _T2& __y)
00319        : first(std::forward<_U1>(__x)), second(__y) { }
00320 
00321       template<typename _U2, typename
00322                enable_if<_PCCP::template
00323                            _CopyMovePair<true, _T1, _U2>(),
00324                          bool>::type=true>
00325        constexpr pair(const _T1& __x, _U2&& __y)
00326        : first(__x), second(std::forward<_U2>(__y)) { }
00327 
00328       template<typename _U2, typename
00329                enable_if<_PCCP::template
00330                            _CopyMovePair<false, _T1, _U2>(),
00331                          bool>::type=false>
00332        explicit pair(const _T1& __x, _U2&& __y)
00333        : first(__x), second(std::forward<_U2>(__y)) { }
00334 
00335       template<typename _U1, typename _U2, typename
00336                enable_if<_PCCP::template
00337                            _MoveConstructiblePair<_U1, _U2>()
00338                           && _PCCP::template
00339                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00340                          bool>::type=true>
00341         constexpr pair(_U1&& __x, _U2&& __y)
00342         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
00343 
00344       template<typename _U1, typename _U2, typename
00345                enable_if<_PCCP::template
00346                            _MoveConstructiblePair<_U1, _U2>()
00347                           && !_PCCP::template
00348                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00349                          bool>::type=false>
00350         explicit constexpr pair(_U1&& __x, _U2&& __y)
00351         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
00352 
00353 
00354       template<typename _U1, typename _U2, typename
00355                enable_if<_PCCFP<_U1, _U2>::template
00356                            _MoveConstructiblePair<_U1, _U2>()
00357                           && _PCCFP<_U1, _U2>::template
00358                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00359                          bool>::type=true>
00360         constexpr pair(pair<_U1, _U2>&& __p)
00361         : first(std::forward<_U1>(__p.first)),
00362           second(std::forward<_U2>(__p.second)) { }
00363 
00364       template<typename _U1, typename _U2, typename
00365                enable_if<_PCCFP<_U1, _U2>::template
00366                            _MoveConstructiblePair<_U1, _U2>()
00367                           && !_PCCFP<_U1, _U2>::template
00368                            _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
00369                          bool>::type=false>
00370         explicit constexpr pair(pair<_U1, _U2>&& __p)
00371         : first(std::forward<_U1>(__p.first)),
00372           second(std::forward<_U2>(__p.second)) { }
00373 
00374       template<typename... _Args1, typename... _Args2>
00375         pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
00376 
00377       pair&
00378       operator=(typename conditional<
00379                 __and_<is_copy_assignable<_T1>,
00380                        is_copy_assignable<_T2>>::value,
00381                 const pair&, const __nonesuch_no_braces&>::type __p)
00382       {
00383         first = __p.first;
00384         second = __p.second;
00385         return *this;
00386       }
00387 
00388       pair&
00389       operator=(typename conditional<
00390                 __and_<is_move_assignable<_T1>,
00391                        is_move_assignable<_T2>>::value,
00392                 pair&&, __nonesuch_no_braces&&>::type __p)
00393       noexcept(__and_<is_nothrow_move_assignable<_T1>,
00394                       is_nothrow_move_assignable<_T2>>::value)
00395       {
00396         first = std::forward<first_type>(__p.first);
00397         second = std::forward<second_type>(__p.second);
00398         return *this;
00399       }
00400 
00401       template<typename _U1, typename _U2>
00402       typename enable_if<__and_<is_assignable<_T1&, const _U1&>,
00403                                 is_assignable<_T2&, const _U2&>>::value,
00404                          pair&>::type
00405         operator=(const pair<_U1, _U2>& __p)
00406         {
00407           first = __p.first;
00408           second = __p.second;
00409           return *this;
00410         }
00411 
00412       template<typename _U1, typename _U2>
00413       typename enable_if<__and_<is_assignable<_T1&, _U1&&>,
00414                                 is_assignable<_T2&, _U2&&>>::value,
00415                          pair&>::type
00416         operator=(pair<_U1, _U2>&& __p)
00417         {
00418           first = std::forward<_U1>(__p.first);
00419           second = std::forward<_U2>(__p.second);
00420           return *this;
00421         }
00422 
00423       void
00424       swap(pair& __p)
00425       noexcept(__and_<__is_nothrow_swappable<_T1>,
00426                       __is_nothrow_swappable<_T2>>::value)
00427       {
00428         using std::swap;
00429         swap(first, __p.first);
00430         swap(second, __p.second);
00431       }
00432 
00433     private:
00434       template<typename... _Args1, std::size_t... _Indexes1,
00435                typename... _Args2, std::size_t... _Indexes2>
00436         pair(tuple<_Args1...>&, tuple<_Args2...>&,
00437              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
00438 #endif
00439     };
00440 
00441 #if __cpp_deduction_guides >= 201606
00442   template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>;
00443 #endif
00444 
00445   /// Two pairs of the same type are equal iff their members are equal.
00446   template<typename _T1, typename _T2>
00447     inline _GLIBCXX_CONSTEXPR bool
00448     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00449     { return __x.first == __y.first && __x.second == __y.second; }
00450 
00451   /// <http://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
00452   template<typename _T1, typename _T2>
00453     inline _GLIBCXX_CONSTEXPR bool
00454     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00455     { return __x.first < __y.first
00456              || (!(__y.first < __x.first) && __x.second < __y.second); }
00457 
00458   /// Uses @c operator== to find the result.
00459   template<typename _T1, typename _T2>
00460     inline _GLIBCXX_CONSTEXPR bool
00461     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00462     { return !(__x == __y); }
00463 
00464   /// Uses @c operator< to find the result.
00465   template<typename _T1, typename _T2>
00466     inline _GLIBCXX_CONSTEXPR bool
00467     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00468     { return __y < __x; }
00469 
00470   /// Uses @c operator< to find the result.
00471   template<typename _T1, typename _T2>
00472     inline _GLIBCXX_CONSTEXPR bool
00473     operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00474     { return !(__y < __x); }
00475 
00476   /// Uses @c operator< to find the result.
00477   template<typename _T1, typename _T2>
00478     inline _GLIBCXX_CONSTEXPR bool
00479     operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00480     { return !(__x < __y); }
00481 
00482 #if __cplusplus >= 201103L
00483   /// See std::pair::swap().
00484   // Note:  no std::swap overloads in C++03 mode, this has performance
00485   //        implications, see, eg, libstdc++/38466.
00486   template<typename _T1, typename _T2>
00487     inline
00488 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
00489     // Constrained free swap overload, see p0185r1
00490     typename enable_if<__and_<__is_swappable<_T1>,
00491                               __is_swappable<_T2>>::value>::type
00492 #else
00493     void
00494 #endif
00495     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
00496     noexcept(noexcept(__x.swap(__y)))
00497     { __x.swap(__y); }
00498 
00499 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
00500   template<typename _T1, typename _T2>
00501     typename enable_if<!__and_<__is_swappable<_T1>,
00502                                __is_swappable<_T2>>::value>::type
00503     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
00504 #endif
00505 #endif // __cplusplus >= 201103L
00506 
00507   /**
00508    *  @brief A convenience wrapper for creating a pair from two objects.
00509    *  @param  __x  The first object.
00510    *  @param  __y  The second object.
00511    *  @return   A newly-constructed pair<> object of the appropriate type.
00512    *
00513    *  The standard requires that the objects be passed by reference-to-const,
00514    *  but LWG issue #181 says they should be passed by const value.  We follow
00515    *  the LWG by default.
00516    */
00517   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00518   // 181.  make_pair() unintended behavior
00519 #if __cplusplus >= 201103L
00520   // NB: DR 706.
00521   template<typename _T1, typename _T2>
00522     constexpr pair<typename __decay_and_strip<_T1>::__type,
00523                    typename __decay_and_strip<_T2>::__type>
00524     make_pair(_T1&& __x, _T2&& __y)
00525     {
00526       typedef typename __decay_and_strip<_T1>::__type __ds_type1;
00527       typedef typename __decay_and_strip<_T2>::__type __ds_type2;
00528       typedef pair<__ds_type1, __ds_type2>            __pair_type;
00529       return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
00530     }
00531 #else
00532   template<typename _T1, typename _T2>
00533     inline pair<_T1, _T2>
00534     make_pair(_T1 __x, _T2 __y)
00535     { return pair<_T1, _T2>(__x, __y); }
00536 #endif
00537 
00538   /// @}
00539 
00540 _GLIBCXX_END_NAMESPACE_VERSION
00541 } // namespace std
00542 
00543 #endif /* _STL_PAIR_H */