libstdc++
stl_pair.h
Go to the documentation of this file.
00001 // Pair implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2016 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   constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
00080 
00081   // Forward declarations.
00082   template<typename...>
00083     class tuple;
00084 
00085   template<std::size_t...>
00086     struct _Index_tuple;
00087 
00088   // Concept utility functions, reused in conditionally-explicit
00089   // constructors.
00090   // See PR 70437, don't look at is_constructible or
00091   // is_convertible if the decayed types are the same to
00092   // avoid querying those properties for incomplete types.
00093   template <typename _T1, typename _T2, typename _U1, typename _U2>
00094   constexpr bool _ConstructiblePair()
00095   {
00096     return __and_<__or_<is_same<typename decay<_T1>::type,
00097                                 typename decay<_U1>::type>,
00098                         is_constructible<_T1, const _U1&>>,
00099                   __or_<is_same<typename decay<_T2>::type,
00100                                 typename decay<_U2>::type>,
00101                         is_constructible<_T2, const _U2&>>>::value;
00102   }
00103 
00104   template <typename _T1, typename _T2, typename _U1, typename _U2>
00105   constexpr bool _ImplicitlyConvertiblePair()
00106   {
00107     return __and_<__or_<is_same<typename decay<_T1>::type,
00108                                 typename decay<_U1>::type>,
00109                         is_convertible<const _U1&, _T1>>,
00110                   __or_<is_same<typename decay<_T2>::type,
00111                                 typename decay<_U2>::type>,
00112                        is_convertible<const _U2&, _T2>>>::value;
00113   }
00114 
00115   template <typename _T1, typename _T2, typename _U1, typename _U2>
00116   constexpr bool _MoveConstructiblePair()
00117   {
00118     return __and_<__or_<is_same<typename decay<_T1>::type,
00119                                 typename decay<_U1>::type>,
00120                         is_constructible<_T1, _U1&&>>,
00121                   __or_<is_same<typename decay<_T2>::type,
00122                                 typename decay<_U2>::type>,
00123                         is_constructible<_T2, _U2&&>>>::value;
00124   }
00125 
00126   template <typename _T1, typename _T2, typename _U1, typename _U2>
00127   constexpr bool _ImplicitlyMoveConvertiblePair()
00128   {
00129     return __and_<__or_<is_same<typename decay<_T1>::type,
00130                                 typename decay<_U1>::type>,
00131                         is_convertible<_U1&&, _T1>>,
00132                   __or_<is_same<typename decay<_T2>::type,
00133                                 typename decay<_U2>::type>,
00134                        is_convertible<_U2&&, _T2>>>::value;
00135   }
00136 
00137 
00138 #endif
00139 
00140  /**
00141    *  @brief Struct holding two objects of arbitrary type.
00142    *
00143    *  @tparam _T1  Type of first object.
00144    *  @tparam _T2  Type of second object.
00145    */
00146   template<typename _T1, typename _T2>
00147     struct pair
00148     {
00149       typedef _T1 first_type;    /// @c first_type is the first bound type
00150       typedef _T2 second_type;   /// @c second_type is the second bound type
00151 
00152       _T1 first;                 /// @c first is a copy of the first object
00153       _T2 second;                /// @c second is a copy of the second object
00154 
00155       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00156       // 265.  std::pair::pair() effects overly restrictive
00157       /** The default constructor creates @c first and @c second using their
00158        *  respective default constructors.  */
00159 #if __cplusplus >= 201103L
00160       template <typename _U1 = _T1,
00161                 typename _U2 = _T2,
00162                 typename enable_if<__and_<
00163                                      __is_implicitly_default_constructible<_U1>,
00164                                      __is_implicitly_default_constructible<_U2>>
00165                                    ::value, bool>::type = true>
00166 #endif
00167       _GLIBCXX_CONSTEXPR pair()
00168       : first(), second() { }
00169 
00170 #if __cplusplus >= 201103L
00171       template <typename _U1 = _T1,
00172                 typename _U2 = _T2,
00173                 typename enable_if<__and_<
00174                        is_default_constructible<_U1>,
00175                        is_default_constructible<_U2>,
00176                        __not_<
00177                          __and_<__is_implicitly_default_constructible<_U1>,
00178                                 __is_implicitly_default_constructible<_U2>>>>
00179                                    ::value, bool>::type = false>
00180       explicit constexpr pair()
00181       : first(), second() { }
00182 #endif
00183 
00184       /** Two objects may be passed to a @c pair constructor to be copied.  */
00185 #if __cplusplus < 201103L
00186       pair(const _T1& __a, const _T2& __b)
00187       : first(__a), second(__b) { }
00188 #else
00189       template<typename _U1 = _T1, typename _U2=_T2, typename
00190                 enable_if<_ConstructiblePair<_T1, _T2, _U1, _U2>()
00191                          && _ImplicitlyConvertiblePair<_T1, _T2, _U1, _U2>(),
00192                          bool>::type=true>
00193       constexpr pair(const _T1& __a, const _T2& __b)
00194       : first(__a), second(__b) { }
00195 
00196        template<typename _U1 = _T1, typename _U2=_T2, typename
00197                enable_if<_ConstructiblePair<_T1, _T2, _U1, _U2>()
00198                          && !_ImplicitlyConvertiblePair<_T1, _T2, _U1, _U2>(),
00199                          bool>::type=false>
00200       explicit constexpr pair(const _T1& __a, const _T2& __b)
00201       : first(__a), second(__b) { }
00202 #endif
00203 
00204       /** There is also a templated copy ctor for the @c pair class itself.  */
00205 #if __cplusplus < 201103L
00206       template<typename _U1, typename _U2>
00207         pair(const pair<_U1, _U2>& __p)
00208         : first(__p.first), second(__p.second) { }
00209 #else
00210       template<typename _U1, typename _U2, typename
00211                enable_if<_ConstructiblePair<_T1, _T2, _U1, _U2>()
00212                          && _ImplicitlyConvertiblePair<_T1, _T2, _U1, _U2>(),
00213                          bool>::type=true>
00214         constexpr pair(const pair<_U1, _U2>& __p)
00215         : first(__p.first), second(__p.second) { }
00216 
00217       template<typename _U1, typename _U2, typename
00218                enable_if<_ConstructiblePair<_T1, _T2, _U1, _U2>()
00219                          && !_ImplicitlyConvertiblePair<_T1, _T2, _U1, _U2>(),
00220                          bool>::type=false>
00221         explicit constexpr pair(const pair<_U1, _U2>& __p)
00222         : first(__p.first), second(__p.second) { }
00223 
00224       constexpr pair(const pair&) = default;
00225       constexpr pair(pair&&) = default;
00226 
00227       // DR 811.
00228       template<typename _U1, typename
00229                enable_if<_ConstructiblePair<_T2, _T2, _T2, _T2>()
00230                          && _MoveConstructiblePair<_T1, _T2, _U1, _T2>()
00231                          && _ImplicitlyConvertiblePair<_T2, _T2, _T2, _T2>()
00232                          && _ImplicitlyMoveConvertiblePair<_T1, _T2,
00233                                                           _U1, _T2>(),
00234                          bool>::type=true>
00235        constexpr pair(_U1&& __x, const _T2& __y)
00236        : first(std::forward<_U1>(__x)), second(__y) { }
00237 
00238       template<typename _U1, typename
00239                enable_if<_ConstructiblePair<_T2, _T2, _T2, _T2>()
00240                          && _MoveConstructiblePair<_T1, _T2, _U1, _T2>()
00241                          && (!_ImplicitlyConvertiblePair<_T2, _T2, _T2, _T2>()
00242                              || !_ImplicitlyMoveConvertiblePair<_T1, _T2,
00243                                                                 _U1, _T2>()),
00244                          bool>::type=false>
00245        explicit constexpr pair(_U1&& __x, const _T2& __y)
00246        : first(std::forward<_U1>(__x)), second(__y) { }
00247 
00248       template<typename _U2, typename
00249                enable_if<_ConstructiblePair<_T1, _T1, _T1, _T1>()
00250                          && _MoveConstructiblePair<_T1, _T2, _T1, _U2>()
00251                          && _ImplicitlyConvertiblePair<_T1, _T1, _T1, _T1>()
00252                          && _ImplicitlyMoveConvertiblePair<_T1, _T2,
00253                                                            _T1, _U2>(),
00254                          bool>::type=true>
00255        constexpr pair(const _T1& __x, _U2&& __y)
00256        : first(__x), second(std::forward<_U2>(__y)) { }
00257 
00258       template<typename _U2, typename
00259                enable_if<_ConstructiblePair<_T1, _T1, _T1, _T1>()
00260                          && _MoveConstructiblePair<_T1, _T2, _T1, _U2>()
00261                          && (!_ImplicitlyConvertiblePair<_T1, _T1, _T1, _T1>()
00262                              || !_ImplicitlyMoveConvertiblePair<_T1, _T2,
00263                                                                 _T1, _U2>()),
00264                          bool>::type=false>
00265        explicit pair(const _T1& __x, _U2&& __y)
00266        : first(__x), second(std::forward<_U2>(__y)) { }
00267 
00268       template<typename _U1, typename _U2, typename
00269                enable_if<_MoveConstructiblePair<_T1, _T2, _U1, _U2>()
00270                          && _ImplicitlyMoveConvertiblePair<_T1, _T2,
00271                                                            _U1, _U2>(),
00272                          bool>::type=true>
00273         constexpr pair(_U1&& __x, _U2&& __y)
00274         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
00275 
00276       template<typename _U1, typename _U2, typename
00277                enable_if<_MoveConstructiblePair<_T1, _T2, _U1, _U2>()
00278                          && !_ImplicitlyMoveConvertiblePair<_T1, _T2,
00279                                                             _U1, _U2>(),
00280                          bool>::type=false>
00281         explicit constexpr pair(_U1&& __x, _U2&& __y)
00282         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
00283 
00284 
00285       template<typename _U1, typename _U2, typename
00286                enable_if<_MoveConstructiblePair<_T1, _T2, _U1, _U2>()
00287                          && _ImplicitlyMoveConvertiblePair<_T1, _T2,
00288                                                            _U1, _U2>(),
00289                          bool>::type=true>
00290         constexpr pair(pair<_U1, _U2>&& __p)
00291         : first(std::forward<_U1>(__p.first)),
00292           second(std::forward<_U2>(__p.second)) { }
00293 
00294       template<typename _U1, typename _U2, typename
00295                enable_if<_MoveConstructiblePair<_T1, _T2, _U1, _U2>()
00296                          && !_ImplicitlyMoveConvertiblePair<_T1, _T2,
00297                                                            _U1, _U2>(),
00298                          bool>::type=false>
00299         explicit constexpr pair(pair<_U1, _U2>&& __p)
00300         : first(std::forward<_U1>(__p.first)),
00301           second(std::forward<_U2>(__p.second)) { }
00302 
00303       template<typename... _Args1, typename... _Args2>
00304         pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
00305 
00306       pair&
00307       operator=(const pair& __p)
00308       {
00309         first = __p.first;
00310         second = __p.second;
00311         return *this;
00312       }
00313 
00314       pair&
00315       operator=(pair&& __p)
00316       noexcept(__and_<is_nothrow_move_assignable<_T1>,
00317                       is_nothrow_move_assignable<_T2>>::value)
00318       {
00319         first = std::forward<first_type>(__p.first);
00320         second = std::forward<second_type>(__p.second);
00321         return *this;
00322       }
00323 
00324       template<typename _U1, typename _U2>
00325         pair&
00326         operator=(const pair<_U1, _U2>& __p)
00327         {
00328           first = __p.first;
00329           second = __p.second;
00330           return *this;
00331         }
00332 
00333       template<typename _U1, typename _U2>
00334         pair&
00335         operator=(pair<_U1, _U2>&& __p)
00336         {
00337           first = std::forward<_U1>(__p.first);
00338           second = std::forward<_U2>(__p.second);
00339           return *this;
00340         }
00341 
00342       void
00343       swap(pair& __p)
00344       noexcept(__is_nothrow_swappable<_T1>::value
00345                && __is_nothrow_swappable<_T2>::value)
00346       {
00347         using std::swap;
00348         swap(first, __p.first);
00349         swap(second, __p.second);
00350       }
00351 
00352     private:
00353       template<typename... _Args1, std::size_t... _Indexes1,
00354                typename... _Args2, std::size_t... _Indexes2>
00355         pair(tuple<_Args1...>&, tuple<_Args2...>&,
00356              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
00357 #endif
00358     };
00359 
00360   /// Two pairs of the same type are equal iff their members are equal.
00361   template<typename _T1, typename _T2>
00362     inline _GLIBCXX_CONSTEXPR bool
00363     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00364     { return __x.first == __y.first && __x.second == __y.second; }
00365 
00366   /// <http://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
00367   template<typename _T1, typename _T2>
00368     inline _GLIBCXX_CONSTEXPR bool
00369     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00370     { return __x.first < __y.first
00371              || (!(__y.first < __x.first) && __x.second < __y.second); }
00372 
00373   /// Uses @c operator== to find the result.
00374   template<typename _T1, typename _T2>
00375     inline _GLIBCXX_CONSTEXPR bool
00376     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00377     { return !(__x == __y); }
00378 
00379   /// Uses @c operator< to find the result.
00380   template<typename _T1, typename _T2>
00381     inline _GLIBCXX_CONSTEXPR bool
00382     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00383     { return __y < __x; }
00384 
00385   /// Uses @c operator< to find the result.
00386   template<typename _T1, typename _T2>
00387     inline _GLIBCXX_CONSTEXPR bool
00388     operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00389     { return !(__y < __x); }
00390 
00391   /// Uses @c operator< to find the result.
00392   template<typename _T1, typename _T2>
00393     inline _GLIBCXX_CONSTEXPR bool
00394     operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
00395     { return !(__x < __y); }
00396 
00397 #if __cplusplus >= 201103L
00398   /// See std::pair::swap().
00399   // Note:  no std::swap overloads in C++03 mode, this has performance
00400   //        implications, see, eg, libstdc++/38466.
00401   template<typename _T1, typename _T2>
00402     inline void
00403     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
00404     noexcept(noexcept(__x.swap(__y)))
00405     { __x.swap(__y); }
00406 #endif
00407 
00408   /**
00409    *  @brief A convenience wrapper for creating a pair from two objects.
00410    *  @param  __x  The first object.
00411    *  @param  __y  The second object.
00412    *  @return   A newly-constructed pair<> object of the appropriate type.
00413    *
00414    *  The standard requires that the objects be passed by reference-to-const,
00415    *  but LWG issue #181 says they should be passed by const value.  We follow
00416    *  the LWG by default.
00417    */
00418   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00419   // 181.  make_pair() unintended behavior
00420 #if __cplusplus >= 201103L
00421   // NB: DR 706.
00422   template<typename _T1, typename _T2>
00423     constexpr pair<typename __decay_and_strip<_T1>::__type,
00424                    typename __decay_and_strip<_T2>::__type>
00425     make_pair(_T1&& __x, _T2&& __y)
00426     {
00427       typedef typename __decay_and_strip<_T1>::__type __ds_type1;
00428       typedef typename __decay_and_strip<_T2>::__type __ds_type2;
00429       typedef pair<__ds_type1, __ds_type2>            __pair_type;
00430       return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
00431     }
00432 #else
00433   template<typename _T1, typename _T2>
00434     inline pair<_T1, _T2>
00435     make_pair(_T1 __x, _T2 __y)
00436     { return pair<_T1, _T2>(__x, __y); }
00437 #endif
00438 
00439   /// @}
00440 
00441 _GLIBCXX_END_NAMESPACE_VERSION
00442 } // namespace std
00443 
00444 #endif /* _STL_PAIR_H */