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 */ 544