You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

587 lines
20KB

  1. // Pair implementation -*- C++ -*-
  2. // Copyright (C) 2001-2020 Free Software Foundation, Inc.
  3. //
  4. // This file is part of the GNU ISO C++ Library. This library is free
  5. // software; you can redistribute it and/or modify it under the
  6. // terms of the GNU General Public License as published by the
  7. // Free Software Foundation; either version 3, or (at your option)
  8. // any later version.
  9. // This library is distributed in the hope that it will be useful,
  10. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. // GNU General Public License for more details.
  13. // Under Section 7 of GPL version 3, you are granted additional
  14. // permissions described in the GCC Runtime Library Exception, version
  15. // 3.1, as published by the Free Software Foundation.
  16. // You should have received a copy of the GNU General Public License and
  17. // a copy of the GCC Runtime Library Exception along with this program;
  18. // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
  19. // <http://www.gnu.org/licenses/>.
  20. /*
  21. *
  22. * Copyright (c) 1994
  23. * Hewlett-Packard Company
  24. *
  25. * Permission to use, copy, modify, distribute and sell this software
  26. * and its documentation for any purpose is hereby granted without fee,
  27. * provided that the above copyright notice appear in all copies and
  28. * that both that copyright notice and this permission notice appear
  29. * in supporting documentation. Hewlett-Packard Company makes no
  30. * representations about the suitability of this software for any
  31. * purpose. It is provided "as is" without express or implied warranty.
  32. *
  33. *
  34. * Copyright (c) 1996,1997
  35. * Silicon Graphics Computer Systems, Inc.
  36. *
  37. * Permission to use, copy, modify, distribute and sell this software
  38. * and its documentation for any purpose is hereby granted without fee,
  39. * provided that the above copyright notice appear in all copies and
  40. * that both that copyright notice and this permission notice appear
  41. * in supporting documentation. Silicon Graphics makes no
  42. * representations about the suitability of this software for any
  43. * purpose. It is provided "as is" without express or implied warranty.
  44. */
  45. /** @file bits/stl_pair.h
  46. * This is an internal header file, included by other library headers.
  47. * Do not attempt to use it directly. @headername{utility}
  48. */
  49. #ifndef _STL_PAIR_H
  50. #define _STL_PAIR_H 1
  51. #include <bits/move.h> // for std::move / std::forward, and std::swap
  52. #if __cplusplus >= 201103L
  53. # include <type_traits> // for std::__decay_and_strip, std::is_reference_v
  54. #endif
  55. #if __cplusplus > 201703L
  56. # include <compare>
  57. # define __cpp_lib_constexpr_utility 201811L
  58. #endif
  59. namespace std _GLIBCXX_VISIBILITY(default)
  60. {
  61. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  62. /**
  63. * @addtogroup utilities
  64. * @{
  65. */
  66. #if __cplusplus >= 201103L
  67. /// Tag type for piecewise construction of std::pair objects.
  68. struct piecewise_construct_t { explicit piecewise_construct_t() = default; };
  69. /// Tag for piecewise construction of std::pair objects.
  70. _GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct =
  71. piecewise_construct_t();
  72. /// @cond undocumented
  73. // Forward declarations.
  74. template<typename...>
  75. class tuple;
  76. template<std::size_t...>
  77. struct _Index_tuple;
  78. // Concept utility functions, reused in conditionally-explicit
  79. // constructors.
  80. // See PR 70437, don't look at is_constructible or
  81. // is_convertible if the types are the same to
  82. // avoid querying those properties for incomplete types.
  83. template <bool, typename _T1, typename _T2>
  84. struct _PCC
  85. {
  86. template <typename _U1, typename _U2>
  87. static constexpr bool _ConstructiblePair()
  88. {
  89. return __and_<is_constructible<_T1, const _U1&>,
  90. is_constructible<_T2, const _U2&>>::value;
  91. }
  92. template <typename _U1, typename _U2>
  93. static constexpr bool _ImplicitlyConvertiblePair()
  94. {
  95. return __and_<is_convertible<const _U1&, _T1>,
  96. is_convertible<const _U2&, _T2>>::value;
  97. }
  98. template <typename _U1, typename _U2>
  99. static constexpr bool _MoveConstructiblePair()
  100. {
  101. return __and_<is_constructible<_T1, _U1&&>,
  102. is_constructible<_T2, _U2&&>>::value;
  103. }
  104. template <typename _U1, typename _U2>
  105. static constexpr bool _ImplicitlyMoveConvertiblePair()
  106. {
  107. return __and_<is_convertible<_U1&&, _T1>,
  108. is_convertible<_U2&&, _T2>>::value;
  109. }
  110. template <bool __implicit, typename _U1, typename _U2>
  111. static constexpr bool _CopyMovePair()
  112. {
  113. using __do_converts = __and_<is_convertible<const _U1&, _T1>,
  114. is_convertible<_U2&&, _T2>>;
  115. using __converts = typename conditional<__implicit,
  116. __do_converts,
  117. __not_<__do_converts>>::type;
  118. return __and_<is_constructible<_T1, const _U1&>,
  119. is_constructible<_T2, _U2&&>,
  120. __converts
  121. >::value;
  122. }
  123. template <bool __implicit, typename _U1, typename _U2>
  124. static constexpr bool _MoveCopyPair()
  125. {
  126. using __do_converts = __and_<is_convertible<_U1&&, _T1>,
  127. is_convertible<const _U2&, _T2>>;
  128. using __converts = typename conditional<__implicit,
  129. __do_converts,
  130. __not_<__do_converts>>::type;
  131. return __and_<is_constructible<_T1, _U1&&>,
  132. is_constructible<_T2, const _U2&&>,
  133. __converts
  134. >::value;
  135. }
  136. };
  137. template <typename _T1, typename _T2>
  138. struct _PCC<false, _T1, _T2>
  139. {
  140. template <typename _U1, typename _U2>
  141. static constexpr bool _ConstructiblePair()
  142. {
  143. return false;
  144. }
  145. template <typename _U1, typename _U2>
  146. static constexpr bool _ImplicitlyConvertiblePair()
  147. {
  148. return false;
  149. }
  150. template <typename _U1, typename _U2>
  151. static constexpr bool _MoveConstructiblePair()
  152. {
  153. return false;
  154. }
  155. template <typename _U1, typename _U2>
  156. static constexpr bool _ImplicitlyMoveConvertiblePair()
  157. {
  158. return false;
  159. }
  160. };
  161. #endif // C++11
  162. template<typename _U1, typename _U2> class __pair_base
  163. {
  164. #if __cplusplus >= 201103L
  165. template<typename _T1, typename _T2> friend struct pair;
  166. __pair_base() = default;
  167. ~__pair_base() = default;
  168. __pair_base(const __pair_base&) = default;
  169. __pair_base& operator=(const __pair_base&) = delete;
  170. #endif // C++11
  171. };
  172. /// @endcond
  173. /**
  174. * @brief Struct holding two objects of arbitrary type.
  175. *
  176. * @tparam _T1 Type of first object.
  177. * @tparam _T2 Type of second object.
  178. *
  179. * <https://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
  180. */
  181. template<typename _T1, typename _T2>
  182. struct pair
  183. : private __pair_base<_T1, _T2>
  184. {
  185. typedef _T1 first_type; ///< The type of the `first` member
  186. typedef _T2 second_type; ///< The type of the `second` member
  187. _T1 first; ///< The first member
  188. _T2 second; ///< The second member
  189. // _GLIBCXX_RESOLVE_LIB_DEFECTS
  190. // 265. std::pair::pair() effects overly restrictive
  191. /** The default constructor creates @c first and @c second using their
  192. * respective default constructors. */
  193. #if __cplusplus >= 201103L
  194. template <typename _U1 = _T1,
  195. typename _U2 = _T2,
  196. typename enable_if<__and_<
  197. __is_implicitly_default_constructible<_U1>,
  198. __is_implicitly_default_constructible<_U2>>
  199. ::value, bool>::type = true>
  200. #endif
  201. _GLIBCXX_CONSTEXPR pair()
  202. : first(), second() { }
  203. #if __cplusplus >= 201103L
  204. template <typename _U1 = _T1,
  205. typename _U2 = _T2,
  206. typename enable_if<__and_<
  207. is_default_constructible<_U1>,
  208. is_default_constructible<_U2>,
  209. __not_<
  210. __and_<__is_implicitly_default_constructible<_U1>,
  211. __is_implicitly_default_constructible<_U2>>>>
  212. ::value, bool>::type = false>
  213. explicit constexpr pair()
  214. : first(), second() { }
  215. #endif
  216. #if __cplusplus < 201103L
  217. /// Two objects may be passed to a @c pair constructor to be copied.
  218. pair(const _T1& __a, const _T2& __b)
  219. : first(__a), second(__b) { }
  220. #else
  221. // Shortcut for constraining the templates that don't take pairs.
  222. /// @cond undocumented
  223. using _PCCP = _PCC<true, _T1, _T2>;
  224. /// @endcond
  225. /// Construct from two const lvalues, allowing implicit conversions.
  226. template<typename _U1 = _T1, typename _U2=_T2, typename
  227. enable_if<_PCCP::template
  228. _ConstructiblePair<_U1, _U2>()
  229. && _PCCP::template
  230. _ImplicitlyConvertiblePair<_U1, _U2>(),
  231. bool>::type=true>
  232. constexpr pair(const _T1& __a, const _T2& __b)
  233. : first(__a), second(__b) { }
  234. /// Construct from two const lvalues, disallowing implicit conversions.
  235. template<typename _U1 = _T1, typename _U2=_T2, typename
  236. enable_if<_PCCP::template
  237. _ConstructiblePair<_U1, _U2>()
  238. && !_PCCP::template
  239. _ImplicitlyConvertiblePair<_U1, _U2>(),
  240. bool>::type=false>
  241. explicit constexpr pair(const _T1& __a, const _T2& __b)
  242. : first(__a), second(__b) { }
  243. #endif
  244. #if __cplusplus < 201103L
  245. /// There is also a templated constructor to convert from other pairs.
  246. template<typename _U1, typename _U2>
  247. pair(const pair<_U1, _U2>& __p)
  248. : first(__p.first), second(__p.second) { }
  249. #else
  250. // Shortcut for constraining the templates that take pairs.
  251. /// @cond undocumented
  252. template <typename _U1, typename _U2>
  253. using _PCCFP = _PCC<!is_same<_T1, _U1>::value
  254. || !is_same<_T2, _U2>::value,
  255. _T1, _T2>;
  256. /// @endcond
  257. template<typename _U1, typename _U2, typename
  258. enable_if<_PCCFP<_U1, _U2>::template
  259. _ConstructiblePair<_U1, _U2>()
  260. && _PCCFP<_U1, _U2>::template
  261. _ImplicitlyConvertiblePair<_U1, _U2>(),
  262. bool>::type=true>
  263. constexpr pair(const pair<_U1, _U2>& __p)
  264. : first(__p.first), second(__p.second) { }
  265. template<typename _U1, typename _U2, typename
  266. enable_if<_PCCFP<_U1, _U2>::template
  267. _ConstructiblePair<_U1, _U2>()
  268. && !_PCCFP<_U1, _U2>::template
  269. _ImplicitlyConvertiblePair<_U1, _U2>(),
  270. bool>::type=false>
  271. explicit constexpr pair(const pair<_U1, _U2>& __p)
  272. : first(__p.first), second(__p.second) { }
  273. #endif
  274. #if __cplusplus >= 201103L
  275. constexpr pair(const pair&) = default; ///< Copy constructor
  276. constexpr pair(pair&&) = default; ///< Move constructor
  277. // DR 811.
  278. template<typename _U1, typename
  279. enable_if<_PCCP::template
  280. _MoveCopyPair<true, _U1, _T2>(),
  281. bool>::type=true>
  282. constexpr pair(_U1&& __x, const _T2& __y)
  283. : first(std::forward<_U1>(__x)), second(__y) { }
  284. template<typename _U1, typename
  285. enable_if<_PCCP::template
  286. _MoveCopyPair<false, _U1, _T2>(),
  287. bool>::type=false>
  288. explicit constexpr pair(_U1&& __x, const _T2& __y)
  289. : first(std::forward<_U1>(__x)), second(__y) { }
  290. template<typename _U2, typename
  291. enable_if<_PCCP::template
  292. _CopyMovePair<true, _T1, _U2>(),
  293. bool>::type=true>
  294. constexpr pair(const _T1& __x, _U2&& __y)
  295. : first(__x), second(std::forward<_U2>(__y)) { }
  296. template<typename _U2, typename
  297. enable_if<_PCCP::template
  298. _CopyMovePair<false, _T1, _U2>(),
  299. bool>::type=false>
  300. explicit pair(const _T1& __x, _U2&& __y)
  301. : first(__x), second(std::forward<_U2>(__y)) { }
  302. template<typename _U1, typename _U2, typename
  303. enable_if<_PCCP::template
  304. _MoveConstructiblePair<_U1, _U2>()
  305. && _PCCP::template
  306. _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
  307. bool>::type=true>
  308. constexpr pair(_U1&& __x, _U2&& __y)
  309. : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
  310. template<typename _U1, typename _U2, typename
  311. enable_if<_PCCP::template
  312. _MoveConstructiblePair<_U1, _U2>()
  313. && !_PCCP::template
  314. _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
  315. bool>::type=false>
  316. explicit constexpr pair(_U1&& __x, _U2&& __y)
  317. : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
  318. template<typename _U1, typename _U2, typename
  319. enable_if<_PCCFP<_U1, _U2>::template
  320. _MoveConstructiblePair<_U1, _U2>()
  321. && _PCCFP<_U1, _U2>::template
  322. _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
  323. bool>::type=true>
  324. constexpr pair(pair<_U1, _U2>&& __p)
  325. : first(std::forward<_U1>(__p.first)),
  326. second(std::forward<_U2>(__p.second)) { }
  327. template<typename _U1, typename _U2, typename
  328. enable_if<_PCCFP<_U1, _U2>::template
  329. _MoveConstructiblePair<_U1, _U2>()
  330. && !_PCCFP<_U1, _U2>::template
  331. _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
  332. bool>::type=false>
  333. explicit constexpr pair(pair<_U1, _U2>&& __p)
  334. : first(std::forward<_U1>(__p.first)),
  335. second(std::forward<_U2>(__p.second)) { }
  336. template<typename... _Args1, typename... _Args2>
  337. _GLIBCXX20_CONSTEXPR
  338. pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
  339. _GLIBCXX20_CONSTEXPR pair&
  340. operator=(typename conditional<
  341. __and_<is_copy_assignable<_T1>,
  342. is_copy_assignable<_T2>>::value,
  343. const pair&, const __nonesuch&>::type __p)
  344. {
  345. first = __p.first;
  346. second = __p.second;
  347. return *this;
  348. }
  349. _GLIBCXX20_CONSTEXPR pair&
  350. operator=(typename conditional<
  351. __and_<is_move_assignable<_T1>,
  352. is_move_assignable<_T2>>::value,
  353. pair&&, __nonesuch&&>::type __p)
  354. noexcept(__and_<is_nothrow_move_assignable<_T1>,
  355. is_nothrow_move_assignable<_T2>>::value)
  356. {
  357. first = std::forward<first_type>(__p.first);
  358. second = std::forward<second_type>(__p.second);
  359. return *this;
  360. }
  361. template<typename _U1, typename _U2>
  362. _GLIBCXX20_CONSTEXPR
  363. typename enable_if<__and_<is_assignable<_T1&, const _U1&>,
  364. is_assignable<_T2&, const _U2&>>::value,
  365. pair&>::type
  366. operator=(const pair<_U1, _U2>& __p)
  367. {
  368. first = __p.first;
  369. second = __p.second;
  370. return *this;
  371. }
  372. template<typename _U1, typename _U2>
  373. _GLIBCXX20_CONSTEXPR
  374. typename enable_if<__and_<is_assignable<_T1&, _U1&&>,
  375. is_assignable<_T2&, _U2&&>>::value,
  376. pair&>::type
  377. operator=(pair<_U1, _U2>&& __p)
  378. {
  379. first = std::forward<_U1>(__p.first);
  380. second = std::forward<_U2>(__p.second);
  381. return *this;
  382. }
  383. /// Swap the first members and then the second members.
  384. _GLIBCXX20_CONSTEXPR void
  385. swap(pair& __p)
  386. noexcept(__and_<__is_nothrow_swappable<_T1>,
  387. __is_nothrow_swappable<_T2>>::value)
  388. {
  389. using std::swap;
  390. swap(first, __p.first);
  391. swap(second, __p.second);
  392. }
  393. private:
  394. template<typename... _Args1, std::size_t... _Indexes1,
  395. typename... _Args2, std::size_t... _Indexes2>
  396. _GLIBCXX20_CONSTEXPR
  397. pair(tuple<_Args1...>&, tuple<_Args2...>&,
  398. _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
  399. #endif // C++11
  400. };
  401. /// @relates pair @{
  402. #if __cpp_deduction_guides >= 201606
  403. template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>;
  404. #endif
  405. /// Two pairs of the same type are equal iff their members are equal.
  406. template<typename _T1, typename _T2>
  407. inline _GLIBCXX_CONSTEXPR bool
  408. operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
  409. { return __x.first == __y.first && __x.second == __y.second; }
  410. #if __cpp_lib_three_way_comparison && __cpp_lib_concepts
  411. template<typename _T1, typename _T2>
  412. constexpr common_comparison_category_t<__detail::__synth3way_t<_T1>,
  413. __detail::__synth3way_t<_T2>>
  414. operator<=>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
  415. {
  416. if (auto __c = __detail::__synth3way(__x.first, __y.first); __c != 0)
  417. return __c;
  418. return __detail::__synth3way(__x.second, __y.second);
  419. }
  420. #else
  421. /** Defines a lexicographical order for pairs.
  422. *
  423. * For two pairs of the same type, `P` is ordered before `Q` if
  424. * `P.first` is less than `Q.first`, or if `P.first` and `Q.first`
  425. * are equivalent (neither is less than the other) and `P.second` is less
  426. * than `Q.second`.
  427. */
  428. template<typename _T1, typename _T2>
  429. inline _GLIBCXX_CONSTEXPR bool
  430. operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
  431. { return __x.first < __y.first
  432. || (!(__y.first < __x.first) && __x.second < __y.second); }
  433. /// Uses @c operator== to find the result.
  434. template<typename _T1, typename _T2>
  435. inline _GLIBCXX_CONSTEXPR bool
  436. operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
  437. { return !(__x == __y); }
  438. /// Uses @c operator< to find the result.
  439. template<typename _T1, typename _T2>
  440. inline _GLIBCXX_CONSTEXPR bool
  441. operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
  442. { return __y < __x; }
  443. /// Uses @c operator< to find the result.
  444. template<typename _T1, typename _T2>
  445. inline _GLIBCXX_CONSTEXPR bool
  446. operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
  447. { return !(__y < __x); }
  448. /// Uses @c operator< to find the result.
  449. template<typename _T1, typename _T2>
  450. inline _GLIBCXX_CONSTEXPR bool
  451. operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
  452. { return !(__x < __y); }
  453. #endif // !(three_way_comparison && concepts)
  454. #if __cplusplus >= 201103L
  455. /** Swap overload for pairs. Calls std::pair::swap().
  456. *
  457. * @note This std::swap overload is not declared in C++03 mode,
  458. * which has performance implications, e.g. see https://gcc.gnu.org/PR38466
  459. */
  460. template<typename _T1, typename _T2>
  461. _GLIBCXX20_CONSTEXPR inline
  462. #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
  463. // Constrained free swap overload, see p0185r1
  464. typename enable_if<__and_<__is_swappable<_T1>,
  465. __is_swappable<_T2>>::value>::type
  466. #else
  467. void
  468. #endif
  469. swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
  470. noexcept(noexcept(__x.swap(__y)))
  471. { __x.swap(__y); }
  472. #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
  473. template<typename _T1, typename _T2>
  474. typename enable_if<!__and_<__is_swappable<_T1>,
  475. __is_swappable<_T2>>::value>::type
  476. swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
  477. #endif
  478. #endif // __cplusplus >= 201103L
  479. // @} relates pair
  480. /**
  481. * @brief A convenience wrapper for creating a pair from two objects.
  482. * @param __x The first object.
  483. * @param __y The second object.
  484. * @return A newly-constructed pair<> object of the appropriate type.
  485. *
  486. * The C++98 standard says the objects are passed by reference-to-const,
  487. * but C++03 says they are passed by value (this was LWG issue #181).
  488. *
  489. * Since C++11 they have been passed by forwarding reference and then
  490. * forwarded to the new members of the pair. To create a pair with a
  491. * member of reference type, pass a `reference_wrapper` to this function.
  492. */
  493. // _GLIBCXX_RESOLVE_LIB_DEFECTS
  494. // 181. make_pair() unintended behavior
  495. #if __cplusplus >= 201103L
  496. // NB: DR 706.
  497. template<typename _T1, typename _T2>
  498. constexpr pair<typename __decay_and_strip<_T1>::__type,
  499. typename __decay_and_strip<_T2>::__type>
  500. make_pair(_T1&& __x, _T2&& __y)
  501. {
  502. typedef typename __decay_and_strip<_T1>::__type __ds_type1;
  503. typedef typename __decay_and_strip<_T2>::__type __ds_type2;
  504. typedef pair<__ds_type1, __ds_type2> __pair_type;
  505. return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
  506. }
  507. #else
  508. template<typename _T1, typename _T2>
  509. inline pair<_T1, _T2>
  510. make_pair(_T1 __x, _T2 __y)
  511. { return pair<_T1, _T2>(__x, __y); }
  512. #endif
  513. /// @}
  514. _GLIBCXX_END_NAMESPACE_VERSION
  515. } // namespace std
  516. #endif /* _STL_PAIR_H */